06_stavove_automaty

• Lambda přechod zajistí opakování

• Zpracování sekvence

• 1 2   2 4 1   2 4 1   2 4 1   2 4 2

Abeceda

• Množina vstupních znaků
• Konečná množina
• Gramatika

• Terminální znaky
• Neterminální znaky
• Pravidla
• Počáteční terminál (kořen gramatiky)

Příklad - Vyhledávací automat

• Hledáme podřetězec (i více) v podřetězci

• Nedeterministický

• Automat má více větví se stejným vstupem

• Deterministický

• Většinou lze z nedeterministického
• To vede k větší komplexnosti

Příklad - Vyhledávací automat

• Hledáme „ahoj“

• Nedeterministické řešení

• v prvním stavu čekáme na příchod znaku „a“
• po přechodu na další stavy zároveň čekáme na další příchod znaku „a“
• koncový stav zastaví všechny ostatní stavy/započaté vyhledávání

• Hledáme slovo „babka“

• Opakuje se začátek
• Složitější automat

• Hledáme zároveň slovo „jeden“ a „den“

• Spojení větví
• V konečném stavu nevíme, které slovo jsme našli
• Podobně „end“ a „endif“ – u preprocesoru

Konečný automat

• matematický model
• výpočetní stroj s konečnou pamětí
• pokud vstupní slovo je akceptováno

dostáváme se do (některého) konečného stavu

• nemusí existovat jediné řešení
• dostaneme-li se do konečného stavu

sekvence patří mezi akceptovaná slova

• známe cestu

syntaktická analýza
víme přesně „co“ přišlo

Turingův stroj

• obecný model výpočtu (algoritmu)
• snaha zjistit co se dá spočítat

• je to algoritmus?
• má konečném počtu kroků?
• je krok realizovatelný?
• má končený počet stavů?

• v závislosti na načteném znaku a stavu:

• (ne)změní stav
• zapíše znak (zde na místo znaku čteného)
• posune se pro další čtení (zde dopředu nebo dozadu)

Deterministické konečné automaty

• Z každého stavu při daném vstupu vždy jen jeden možný 

přechod

• Základní představitelé

• Moore
• Mealy