V dnešní technologické době došlo v oblasti hardwaru i softwaru k obrovskému rozvoji. Jednou z hlavních oblastí vývoje byla metoda hardwarových návrhů. S rostoucí technologie bylo možné implementovat koncept hardwarového a softwarového co-designu. Jsou vyvíjeny různé metody, kterými pomocí softwaru lze plně navrhnout a simulovat hardwarové systémy. Jednou z takových metod je teorie automatů. Teorie automatů je obor počítačová věda která se zabývá návrhem abstraktního modelu výpočetních zařízení, která automaticky sledují předem stanovený sled kroků. Tento článek popisuje stručné informace o výuce automatů.
Co je teorie automatů?
Slovo Automata je odvozeno z řečtiny, což znamená „samočinný“. Automat je matematický model stroje. Automat se skládá ze stavů a přechodů. Jakmile je vstup zadán automatu, provede přechod do dalšího stavu v závislosti na přechodové funkci. Vstupy do funkce přechodu jsou aktuální stav a poslední symboly. Pokud má Automat konečný počet stavů, je známý jako Konečné automaty nebo Konečný státní stroj . Konečné automaty jsou reprezentovány 5 n-ticí (Q, ∑, δ, qo, F)
Kde,
Q = konečná množina stavů.
∑ = konečná sada symbolů nazývaná také Abeceda automatů.
δ = přechodová funkce.
qo = počáteční stav vstupu.
F = množina konečných stavů Q.
Základní terminologie teorie automatů
Některé základní terminologie teorie automatů jsou -
1 . Abeceda : Jakákoli konečná sada symbolů v teorii automatů je známá jako abeceda. Reprezentovaná písmenem∑ se množina {a, b, c, d, e,} nazývá Abecední sada, zatímco písmena množiny 'a', 'b', 'c', 'd', 'e' se nazývají symboly.
dva . Tětiva : V automatech je řetězec konečnou posloupností symbolů převzatých z abecední sady ∑. Například řetězec S = ‚adeaddadc 'je platný pro abecední sadu∑ = {a, b, c, d, e,}.
3 . Délka řetězce : Počet symbolů přítomných v řetězci je znám jako Délka řetězce. Pro řetězec S = ‚adaada 'je délka řetězce | S | = 6. Pokud je délka řetězce 0, pak se nazývá prázdný řetězec.
4 . Kleen Star : Je to unární operátor na sadě symbolů Σ, který dává nekonečnou množinu všech možných řetězců, včetně λ, všech možných délek přes množinu Σ. Představovalo to. Například pro množinu Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen uzavření : Je to nekonečná množina všech možných řetězců abecední sady kromě λ. Označuje to. Pro množinu Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Jazyk : Jazyk je podmnožinou hvězdné sady Kleene∑ * pro některou abecední sadu Σ. Jazyk může být konečný nebo nekonečný. Například pokud jazyk převezme všechny možné řetězce délky 2 přes množinu Σ = {a, d}, pak L = {aa, ad, da, dd}.
Formální jazyky a automaty
V teorii automatů je formální jazyk sada řetězců, kde je každý řetězec složený ze symbolů patřící do konečné abecední sady Σ. Uvažujme o kočičím jazyce, který může obsahovat jakékoli řetězce z níže uvedené nekonečné množiny…
pelichání!
meww!
mewww !! ……
Abeceda nastavená pro jazyk koček je Σ = {m, e, w,!}. Nechte tuto sadu použít pro model konečných stavových automatů-m. Potom je formální jazyk charakterizovaný modelem m označen
L (m)
L (m) = {„mew!“, „Meww!“, „Mewww“, ……}
Automat je užitečný pro definování jazyka, protože dokáže vyjádřit nekonečnou množinu v uzavřené formě. Formální jazyky nejsou stejné jako přirozené jazyky, kterými mluvíme v každodenním životě. Formální jazyk může na rozdíl od našich běžných jazyků označovat různé stavy stroje. Formální jazyk se používá k modelování části přirozeného jazyka, například syntaxe atd. Formální jazyky jsou definovány automaty konečného stavu. Existují dva hlavní pohledy na automaty konečných stavů - akceptory, které dokáží zjistit, zda je řetězec v jazyce a druhý je generátor, který produkuje pouze řetězce v jazyce.
Deterministické konečné automaty
V deterministickém typu automatů, když je zadán vstup, můžeme vždy určit, do kterého stavu by přechod byl. Jelikož se jedná o konečný automat, nazývá se to Deterministické konečné automaty.
Grafické znázornění
Stavový diagram jsou digrafy používané pro grafické znázornění deterministických konečných automatů. Rozumíme tomu na příkladu. Nechť jsou deterministické konečné automaty…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} a přechodová funkce je
Tabulková forma grafického znázornění
Stavový diagram
Stavový diagram deterministických automatů konečných stavů
Ze stavového diagramu
- Stavy jsou reprezentovány vrcholy.
- Přechody jsou reprezentovány obloukem označeným vstupní abecedou.
- Prázdný jednotlivý příchozí oblouk představuje počáteční stav.
- Stav s dvojitými kruhy je konečný stav.
Nedeterministické konečné automaty
Automaty, u kterých nelze určit stav výstupu pro daný vstup, se nazývají nedeterministické automaty. Nazývá se také nedeterministické konečné automaty, protože má konečný počet stavů. Nedeterministické konečné automaty jsou reprezentovány jako množina 5 -tuple kde (Q, ∑, δ, qo, F)
Q = konečná množina stavů.
∑ = Abeceda sada.
δ = přechodová funkce
kde : 
qo = Počáteční stav.
Grafické znázornění
Nedeterministické konečné automaty jsou reprezentovány pomocí stavového diagramu. Nechte nedeterministické konečné automaty
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Přechody jsou
Tabulková forma grafického znázornění
Stavový diagram
Stavový diagram nedeterministických konečných automatů
Aplikace teorie automatů
Aplikace teorie automatů zahrnout následující.
- Teorie automatů je velmi užitečná v oblastech teorie výpočtu, produkce kompilátorů, AI atd.
- U kompilátorů pro zpracování textu a návrhů hardwaru hrají hlavní roli konečné automaty.
- Pro aplikace v AI a v programovací jazyky „Bezkontextová gramatika je velmi užitečná.
- V oblasti biologie jsou celulární automaty užitečné.
- V teorii konečných polí také můžeme najít aplikaci automatů.
V tomto článku jsme se naučili krátký úvod do jazyků a výpočtů teorie automatů. Automaty existují už od pravěku. S vynálezem nových technologií je v této oblasti vidět mnoho nového vývoje. S jakým typem automatů jste se setkali?
