Grammar, Language and their Acceptors in Automata
In Theory of Automata, Grammar generates a language which is either accepted or rejected by a machine called Automaton or Automata Machine. Let explain major types of Grammars, languages and their accepters
Types of Grammars
There are four major types of grammars in theory of Automata.
- Regular Grammar
- Context Free Grammar
- Context Sensitive Grammar
- Unrestricted Grammar
Let explain all above types of grammars in detail.
1. Regular Grammar (RL)
Regular Grammar generates the Regular Languages and all regular languages are accepted by Finite Automata Machine. Regular Grammar is also called Type-3 grammar
Regular languages are of two types
- Finite Regular Languages
- Infinite Regular Languages
Finite Automata Machine is also of two types
- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NDFA)
All regular languages either finite or infinite are accepted by NDFA. But all regular languages and some infinite language are accepted by DFA. |
2. Context Free Grammar (CFG)
Context free Grammar generates the Context free Languages and all context free languages are accepted by Pushdown Automata Machine. Context Free Grammar is also called Type-2 grammar
Context Free languages are of two types
- Deterministic Context Free Languages
- Non Deterministic Context Free Languages
Pushdown Automata Machine is also of two types
- Deterministic Pushdown Automata (DPDA)
- Non-Deterministic Pushdown Automata (NPDA)
All Deterministic Context Free languages are accepted by Deterministic Pushdown Automata (DPDA). But all Non-Deterministic Context Free languages are accepted by Non-Deterministic Pushdown Automata (NPDA). |
3. Context Sensitive Grammar (CSG)
Context Sensitive Grammar generates the Context sensitive Languages and all context sensitive languages are accepted by Linear Bound Automata Machine. Context Free Grammar is also called Type-1 grammar.
Note: Context Sensitive languages and their machines are not Deterministic and Non-Deterministic.
4. Unrestricted Grammar
Unrestricted Grammar generates the Recursive enumerable Languages and all Recursive enumerable languages are accepted by Turing Machine. Unrestricted Grammar is also called Type-0 grammar.
Important: Type-0 Accepter is the Highest Power and Type-3 accepter has lowest Power. It means type -3 accepter which is Turing Machine can accept all languages either they are regular, context free or context sensitive. But Type-3 accepter which is Finite Automata can accept only regular languages. |
Chomsky Hierarchy
Explanation of all above four types of grammar is known as chomsky hierarchy. Diagram of chomsky hierarchy is given below