logo

Hotovo automaticky

  • K rozpoznání vzorů se používají konečné automaty.
  • Vezme řetězec symbolů jako vstup a podle toho změní jeho stav. Když je nalezen požadovaný symbol, dojde k přechodu.
  • V době přechodu se mohou automaty buď přesunout do dalšího stavu, nebo ve stejném stavu zůstat.
  • Konečné automaty mají dva stavy, Přijmout stav nebo Odmítnout stát . Když je vstupní řetězec úspěšně zpracován a automaty dosáhnou konečného stavu, přijme je.

Formální definice FA

Konečný automat je soubor 5-ti n-tic (Q, ∑, δ, q0, F), kde:

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Model konečných automatů:

Konečné automaty mohou být reprezentovány vstupní páskou a konečným řízením.

Vstupní páska: Je to lineární páska s určitým počtem buněk. Každý vstupní symbol je umístěn v každé buňce.

Konečné ovládání: Konečné řízení rozhoduje o dalším stavu při příjmu konkrétního vstupu ze vstupní pásky. Čtečka pásky čte buňky jednu po druhé zleva doprava a současně se čte pouze jeden vstupní symbol.

Hotovo automaticky

Typy automatů:

Existují dva typy konečných automatů:

  1. DFA (deterministické konečné automaty)
  2. NFA (nedeterministické konečné automaty)
Hotovo automaticky

1. DFA

DFA označuje deterministické konečné automaty. Deterministický odkazuje na jedinečnost výpočtu. V DFA přejde stroj do jednoho stavu pouze pro určitý vstupní znak. DFA nepřijímá nulový přesun.

2. NFA

NFA je zkratka pro nedeterministické konečné automaty. Používá se k přenosu libovolného počtu stavů pro konkrétní vstup. Může přijmout nulový tah.

Některé důležité body o DFA a NFA:

  1. Každé DFA je NFA, ale NFA není DFA.
  2. V NFA i DFA může existovat více konečných stavů.
  3. DFA se používá v Lexikální analýze v kompilátoru.
  4. NFA je spíše teoretický koncept.