Bot: Automatski unos stranica |
m bnz |
||
| Redak 1: | Redak 1: | ||
{| align="center" valign="bottom" border="0" cellpadding="2" cellspacing="0" class="toccolours" | |||
|- | |- | ||
! colspan="4" style="background:#ddd;" | [[Teorija automata]]: [[Formalni jezik|formalni jezici]] i [[Formalna gramatika|formalne gramatike]] | ! colspan="4" style="background:#ddd;" | [[Teorija automata]]: [[Formalni jezik|formalni jezici]] i [[Formalna gramatika|formalne gramatike]] | ||
Posljednja izmjena od 2. travanj 2022. u 22:44
| Teorija automata: formalni jezici i formalne gramatike | |||
|---|---|---|---|
| Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
| Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingov stroj |
| n/a | (nema uobičajenog imena) | Rekurzivni | Odlučitelj |
| Tip 1 | Kontekstno ovisna | Kontekstno ovisni | Linearno ograničen |
| n/a | Indeksirana | Indeksirani | Ugniježđenog stoga |
| Tip 2 | Kontekstno neovisna | Kontekstno neovisni | Nedeterministički potisni |
| n/a | Deterministička kontekstno neovisna | Deterministički kontekstno neovisni | Deterministički potisni |
| Tip 3 | Regularna | Regularni | Konačni |
| Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije. | |||