| Chomsky hierarchy | Grammars | Languages | Minimal automaton |
| Type-0 | (unrestricted) | Recursively enumerable | Turing machine |
| (unrestricted) | Recursive | Decider | |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| Type-2 | Context-free | Context-free | Pushdown |
| Type-3 | Regular | Regular | Finite |
No comments:
Post a Comment