# 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