Teória automatov
Z Wikipédie
Teória automatov je časť infomatiky zaoberajúca sa strojmi s konečným počtom stavov. Skúma ich matematickou reprezentáciou (automat, Turingov stroj).
| Formálne jazyky, automaty a gramatiky | |||
|---|---|---|---|
| Chomského hierarchia |
Gramatiky | Jazyky | 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 o počítačoch a súvisiacich veciach je zatiaľ príliš krátky (tzv. "výhonok"). Môžeš pomôcť Wikipédii rozšíriť ho tak, že hore klikneš na záložku "úprava" (alebo alternatívne sem) a dopíšeš alebo zmeníš text. |
