Automat (teória automatov)
Automat je matematický model správania sa systému uskutočňujúceho zobrazenie informácie. Ak je táto informácia číslicová, hovoríme o číslicovom alebo diskrétnom automate. Pôvodná informácia sa privádza na vstup automatu, transformovaná informácia sa objavuje na jeho výstupe. Činnosť číslicového automatu prebieha v nespojitých časových úsekoch, ktorých veľkosť nemusí byť zhodná. V tychto časových úsekoch sa na vstup automatu privádzajú vstupné symboly, ktoré automat transformuje na výstupné symboly.
Externé odkazy[upraviť | upraviť zdroj]
- FILIT – zdroj, z ktorého pôvodne čerpal tento článok.
| 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. | |||