Теорија аутомата: Терминологије и примене

У данашњој технолошкој ери и хардверско и софтверско поље забележили су изузетан развој. Једно од главних подручја развоја видело се у методама дизајна хардвера. Са растућа технологија , концепт хардвера - софтверски ко-дизајн било је могуће применити. Развијају се различите методе којима се, користећи софтвер може се у потпуности дизајнирати и симулирати хардверски систем. Једна од таквих метода је теорија аутомата. Теорија аутомата је грана информатика која се бави дизајнирањем апстрактног модела рачунарских уређаја који аутоматски прате унапред одређени редослед корака. Овај чланак говори о кратким информацијама о упутству за аутомате.

Шта је теорија аутомата?

Реч Аутомата изведена је из грчког, што значи „самоактиван“. Аутомат је математички модел машине. Аутомат се састоји од стања и прелаза. Како се улаз даје аутомату, он прелази у следеће стање, у зависности од функције преласка. Улази у функцију преласка су тренутно стање и недавни симболи. Ако Аутомат има коначан број стања, познат је као Коначни аутомати или Коначна државна машина . Коначни аутомати су представљени петокраком (К, ∑, δ, ко, Ф)

Где,

К = Коначни скуп стања.

∑ = коначни скуп симбола који се називају и абецеда аутомата.

δ = прелазна функција.

ко = почетно стање улаза.

Ф = скуп коначних стања К.

Основне терминологије теорије аутомата

Неке од основних терминологија теорије аутомата су

1 . Абецеда : Било који коначни скуп симбола у теорији аутомата познат је као абецеда. Представљен словом∑ скуп {а, б, ц, д, е,} назива се Алпхабет сет, док се слова скупа 'а', 'б', 'ц', 'д', 'е' називају симболи.

два . Низ : У аутоматима је низ коначан низ симбола преузет из абецедног низа ∑, На пример, низ С = ‘адеаддадц’ важи за абецедни скуп∑ = {а, б, ц, д, е,}.

3 . Дужина низа : Број присутних симбола у низу познат је под називом Дужина низа. За низ С = ’адаада’ дужина низа је | С | = 6. Ако је дужина низа 0, тада се назива празним низом.

4 . Клеен Стар : Унарни је оператор на скупу симбола Σ, који даје бесконачни скуп свих могућих низова, укључујући λ, свих могућих дужина над скупом Σ. Представљала је. На пример, за скуп Σ = {ц, д}, ∑ * = {λ, ц, д, цд, дц, цц, дд, ……}.

5 . Затварање Клеен : То је бесконачни скуп свих могућих низова абецеде, искључујући λ. Означава се са. За скуп Σ = {а, д}, ∑ + = {а, д, ад, да, аа, дд, ... ..}.

6 . Језик : Језик је подскуп Клеенеовог звезданог скупа∑ * за неки Абецедни скуп Σ. Језик може бити коначан или бесконачан. На пример, ако језик заузме све могуће низове дужине 2 преко скупа Σ = {а, д}, тада је Л = {аа, ад, да, дд}.

Формални језици и аутомати

У теорији аутомата, формални језик је скуп жица, где је сваки низ састављен од симбола припада коначном абецедном скупу Σ. Размотримо мачји језик који може садржати било који низ из доњег бесконачног скупа ...
мев!
мевв!
меввв !! ……

Абецеда постављена за језик мачака је Σ = {м, е, в,!}. Нека се овај скуп користи за модел аутомата коначног стања-м. Тада се формални језик који карактерише модел м означава са

Л (м)
Л (м) = {„јао!“, „Јао!“, „Јао“, ……}

Аутомат је користан за дефинисање језика јер може да изрази бесконачни скуп у затвореној форми. Формални језици нису исто што и природни језици којима говоримо у свакодневном животу. Формални језик може означавати различита стања машине, за разлику од наших редовних језика. Формални језик се користи за моделирање дела природног језика као што је синтакса итд ... Формални језици су дефинисани аутоматима коначних стања. Постоје две главне перспективе аутомата коначних стања - акцепти који могу да утврде да ли је низ у језику, а други је генератор који производи само низове у језику.

Детерминистички коначни аутомати

У детерминистичком типу аутомата, када се даје улаз, увек можемо одредити у које стање би био прелаз. Како је ово коначни аутомат, назива се детерминистички коначни аутомат.

Графички приказ

Дијаграм стања је диграф који се користи за графички приказ детерминистичких коначних аутомата. Да разумемо на примеру. Нека су детерминистички коначни аутомати ...
К = {а, б, ц, д}.
Σ = {0, 1}
= {а}
Ф = {д} а прелазна функција бити

Графички приказ Табеларни облик

Дијаграм стања

Дијаграм стања детерминистичких коначних аутомата

Из дијаграма стања

• Државе су представљене темена.
• Прелази су представљени луком означеним улазном абецедом.
• Празни појединачни долазни лук представља почетно стање.
• Држава са двоструким круговима је коначно стање.

Недетерминистички коначни аутомати

Аутомати код којих се не може одредити излазно стање за дати улаз називају се не-детерминистички аутомати. Такође се називају и недетерминистички коначни аутомати, јер има коначан број стања. Недетерминистички коначни аутомати представљени су као скуп од 5 - парова где (К, ∑, δ, ко, Ф)

К = коначан скуп држава.
∑ = Сет абецеда.
δ = функција прелаза

где : ко = Почетно стање.

Графички приказ

Недетерминистички коначни аутомати представљени су уз помоћ дијаграма стања. Нека недетерминистички коначни аутомати постану

К = {а, б, ц, д}
Σ = {0,1}
ко = {а}
Ф = {д}

Прелази су

Графички приказ Табеларни облик

Дијаграм стања

Дијаграм стања недетерминистичких коначних аутомата

Примене теорије аутомата

Примене теорија аутомата укључи следеће.

• Теорија аутомата је веома корисна у областима Теорије рачунања, израде компајлера, АИ итд.
• За компајлере за обраду текста и дизајне хардвера, коначни аутомати играју главну улогу.
• За апликације у АИ и на програмски језици , Граматика без контекста је веома корисна.
• У пољу биологије корисни су ћелијски аутомати.
• У теорији коначних поља такође можемо наћи примену Аутомата.

У овом чланку смо научили кратак увод у језике теорије аутомата и рачунање. Аутомати постоје од праисторије. Изумом нових технологија на овом пољу се виде многи нови развоји. На коју врсту аутомата сте наишли?