V dnešnej technologickej dobe zaznamenala oblasť hardvéru aj softvéru obrovský rozvoj. Jedna z hlavných oblastí vývoja bola v metódach návrhov hardvéru. Vďaka pestovateľská technológia bolo možné implementovať koncept hardvéru - softvérového spolusprojektu. Vyvíjajú sa rôzne metódy, pomocou ktorých, pomocou softvéru je možné plne navrhnúť a simulovať hardvérové systémy. Jednou z takýchto metód je teória automatov. Teória automatov je odvetvím počítačová veda ktorá sa zaoberá návrhom abstraktného modelu výpočtových zariadení, ktoré automaticky sledujú vopred stanovenú postupnosť krokov. Tento článok pojednáva o krátkych informáciách o výučbe automatov.
Čo je teória automatov?
Slovo Automata je odvodené z gréčtiny, čo znamená „samostatne pôsobiaci“. Automat je matematický model stroja. Automat sa skladá zo stavov a prechodov. Keď je vstup daný automatu, vykoná prechod do ďalšieho stavu v závislosti od funkcie prechodu. Vstupmi do funkcie prechodu sú súčasný stav a posledné symboly. Ak má automat konečný počet stavov, je známy ako Finite Automata alebo Konečný štátny stroj . Konečné automaty sú reprezentované 5-tinou (Q, ∑, δ, qo, F)
Kde,
Q = konečná množina stavov.
∑ = konečná sada symbolov nazývaná aj Abeceda automatov.
δ = prechodová funkcia.
qo = počiatočný stav vstupu.
F = množina konečných stavov Q.
Základné terminológie teórie automatov
Niektoré zo základných terminológií z teórie automatov sú:
1 . Abeceda : Akákoľvek konečná sada symbolov v teórii automatov je známa ako Abeceda. Množina {a, b, c, d, e,}, ktorá je reprezentovaná písmenom is, sa nazýva Abecedná sada, zatiaľ čo písmená množiny „a“, „b“, „c“, „d“, „e“ sa nazývajú symboly.
dva . String : V automatoch je reťazec konečnou postupnosťou symbolov prevzatých z abecednej množiny ∑. Napríklad reťazec S = ‘adeaddadc’ platí pre abecednú množinu∑ = {a, b, c, d, e,}.
3 . Dĺžka šnúrky : Počet symbolov prítomných v reťazci je známy ako Dĺžka reťazca. Pre reťazec S = ‘adaada’ je dĺžka reťazca | S | = 6. Ak je dĺžka reťazca 0, potom sa nazýva prázdny reťazec.
4 . Kleen Star : Je to unárny operátor na množine symbolov Σ, ktorý dáva nekonečnú množinu všetkých možných reťazcov vrátane λ všetkých možných dĺžok cez množinu Σ. Predstavovalo to. Napríklad pre množinu Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen uzáver : Je to nekonečná množina všetkých možných reťazcov abecednej sady okrem λ. Označuje to. Pre množinu Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Jazyk : Jazyk je podmnožinou sady hviezd Kleeneene * pre niektoré abecedy Σ. Jazyk môže byť konečný alebo nekonečný. Napríklad ak jazyk prevezme všetky možné reťazce dĺžky 2 cez množinu Σ = {a, d}, potom L = {aa, ad, da, dd}.
Formálne jazyky a automaty
V teórii automatov je formálny jazyk sada reťazcov, kde je každý reťazec zložený zo symbolov patriace do konečnej abecedy Σ. Zvážme mačací jazyk, ktorý môže obsahovať akékoľvek reťazce z nižšie uvedenej nekonečnej množiny ...
mew!
meww!
mewww !! ……
Abeceda nastavená pre jazyk mačiek je Σ = {m, e, w,!}. Nech je táto množina použitá pre model Automata s konečným stavom-m. Potom je formálny jazyk charakterizovaný modelom m označený
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ...…}
Automat je užitočný na definovanie jazyka, pretože dokáže vyjadriť nekonečnú množinu v uzavretej podobe. Formálne jazyky nie sú to isté ako prirodzené jazyky, ktorými hovoríme v každodennom živote. Formálny jazyk môže na rozdiel od našich bežných jazykov označovať rôzne stavy prístroja. Formálny jazyk sa používa na modelovanie časti prirodzeného jazyka, ako je syntax atď. Formálne jazyky sú definované automatmi konečného stavu. Existujú dva hlavné pohľady na automaty konečných stavov - akceptory, ktoré dokážu zistiť, či je reťazec v jazyku a druhý je generátor, ktorý produkuje iba reťazce v jazyku.
Deterministické konečné automaty
V deterministickom type automatov, keď je daný vstup, môžeme vždy určiť, do akého stavu by prechod prebehol. Pretože sa jedná o konečný automat, nazýva sa to Deterministické konečné automaty.
Grafické znázornenie
Stavový diagram sú digrafy používané na grafické znázornenie deterministických konečných automatov. Poďme to pochopiť na príklade. Nech sú deterministické konečné automaty…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} a prechodová funkcia je
Tabuľkové grafické znázornenie
Štátny diagram
Stavový diagram deterministických automatov konečného stavu
Zo štátneho diagramu
- Štáty sú reprezentované vrcholmi.
- Prechody sú reprezentované oblúkom označeným vstupnou abecedou.
- Prázdny jednotlivý prichádzajúci oblúk predstavuje počiatočný stav.
- Stav s dvojitými kruhmi je konečný stav.
Nedeterministické konečné automaty
Automaty, kde nie je možné určiť stav výstupu pre daný vstup, sa nazývajú nedeterministické automaty. Nazýva sa tiež nedeterministické konečné automaty, pretože má konečný počet stavov. Nedeterministické konečné automaty sú reprezentované ako množina 5-tíc, kde (Q, ∑, δ, qo, F)
Q = konečná množina stavov.
∑ = Abeceda.
δ = prechodová funkcia
kde : 
qo = Počiatočný stav.
Grafické znázornenie
Nedeterministické konečné automaty sú reprezentované pomocou stavového diagramu. Nechajte nedeterministické konečné automaty
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Prechody sú
Tabuľkové grafické znázornenie
Štátny diagram
Stavový diagram nedeterministických konečných automatov
Aplikácie teórie automatov
Aplikácie teória automatov zahrňte nasledujúce.
- Teória automatov je veľmi užitočná v oblasti teórie výpočtu, produkcie kompilátorov, AI atď.
- Pri kompilátoroch na spracovanie textu a dizajnoch hardvéru zohrávajú hlavnú úlohu konečné automaty.
- Pre aplikácie v AI a v programovacie jazyky , Bezkontextová gramatika je veľmi užitočná.
- V oblasti biológie sú užitočné bunkové automaty.
- V teórii konečných polí tiež nájdeme aplikáciu automatov.
V tomto článku sme sa naučili krátky úvod do jazykov a výpočtov teórie automatov. Automaty sú tu už od praveku. Vďaka vynájdeniu nových technológií je v tejto oblasti vidieť veľa nového. S akým typom automatov ste sa stretli?
