The Chomsky Hierarchy Flashcards
1
Q
The Chomsky Hierarchy
A
Classes of language
- Regular
- Context-Free
- Context-Sensitive
- Turing Machine
2
Q
Regular Grammar
A
The class of languages such that there exists any finite state automaton that recognizes them
3
Q
Context-Free Grammar
A
The class of languages that can be generated by context-free grammar
a^n b^n | N > 0 is context-free but not regular
4
Q
Context-Sensitive Grammar
A
Cannot be generated by a context-free grammar
a^n b^n c^n | N > 0
5
Q
Turing Machine
A
Unrestricted grammar
Infinite tape, can go forwards and backwards, read and write
6
Q
Human language
A
Human language is recursive
Mildly context sensitive
