Lis 12
S konečnými automaty můžeme pracovat obdobně jako s množinami. Můžeme na ně aplikovat různé operace jako sjednocení, průnik, zřetězení, iterace, doplněk, zrcadlový obraz, kvocient, atd. Na úvod je zapotřebí si definovat třídu všech jazyků rozpoznatelných konečným automatem F.
Lis 10
Zobecněný nedeterministický konečný automat lze převést přímo na deterministický konečný automat pomocí následujícího algoritmu. Je obdobný stromovému algoritmu převodu NKA na DKA. Nejprve si ale musíme vysvětlit, co je to E-funkce.
Lis 09
Představíme-li si automat takový, že dokáže přecházet mezi jednotlivými stavy, aniž by načetl jakýkoliv vstupní symbol, hovoříme o zobecněném nedeterministickém konečném automatu, a tyto speciální stavy se nazývají ε-přechody.
Lis 08
Přestože dva konečné automaty obsahují rozdílný počet stavů, rozdílný počet a tvar přechodových funkcí, mohou být ekvivalentní. Definice 1: Konečný automat A a konečný automat B jsou ekvivalentní, pokud oba rozpoznávají jeden společný jazyk, tedy L(A) = L(B). Abychom mohli velice jednoduše ověřit, zdali dva konečné automaty jsou ekvivalentní, je zapotřebí nejprve definovat dosažitelnost a …
Lis 07
Všechny nedeterministické konečné automaty se dají pomocí jednoduchého algoritmu převést na deterministické konečné automaty. Je zapotřebí pouze sjednotit vstupní stavy do jednoho deterministického vstupu a definovat nové vnitřní stavy, které budou odpovídat všem variacím z nedeterministické množiny.
Lis 06
Každý konečný automat můžeme reprezentovat různými způsoby zápisu. Lze použít výčet jednotlivých prvků automatu, tedy stavů a přechodových funkcí, dále lze použít reprezentaci pomocí tabulky, stavového diagramu či stavového stromu. Reprezentace výčtem prvků
Lis 03
Úvodní kapitola teorie konečných automatů vymezí základní pojmy, se kterými se budeme dále setkávat. Gramatika – soubor všech symbolů, znaků a pravidel, které je zapotřebí k vytváření vět. Jazyk – obsahuje všechny věty, které lze vytvořit pomocí gramatiky. Jazyk tedy nemůže obsahovat nic, co není obsaženo v gramatice daného jazyka. Automat – algoritmus, pomocí kterého …
Své připomínky a náměty mi můžete psát na info@michaluvweb.cz.
Přihlaste se k odběru novinek.