Teória automatov
Teória automatov je časť informatiky zaoberajúca sa strojmi s konečným počtom stavov. Skúma ich matematickou reprezentáciou (automat, Turingov stroj).
Konečný automat je definovaný množinou stavov, počiatočným a konečným stavom, prechodovou funkciou a abecedou. Ku každému konečnému automatu existuje gramatika (vytvára slová). Gramatika je jednoznačne definovaná neterminálmi, terminálmi, pravidlami a počiatočným neterminálom. Automat sa dá zapísať tabuľkou, graficky alebo matematickou funkciou. Príklad na gramatiku (napíše slovo abababab...)
- S→aB|ε (prázdna množina)
- B→bC|b
- C→aB
príklad na gramatiku (napíše nepárne číslo v binárnej sústave)
- S→1B|1
- B→0B|1B|1
| Formálne jazyky, automaty a gramatiky | |||
|---|---|---|---|
| Chomského hierarchia |
Gramatika | Jazyk | Minimálny automat |
| Typ-0 | Frázová | Rekurzívne vyčísliteľný | Turingov stroj |
| Rekurzívny | Vždy zastavujúci Turingov stroj | ||
| Typ-1 | Kontextová | Kontextový | (Nedeterministický) lineárne ohraničený |
| Typ-2 | Bezkontextová | Bezkontextový | (Nedeterministický) zásobníkový |
| Typ-3 | Regulárna | Regulárny | Konečný |
| Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou. | |||
|
Tento článok týkajúci sa počítačov je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš. |