# Grammar, Language and their Acceptors in Automata

In the Theory of Automata, Grammar generates a language that is either accepted or rejected by a machine called an Automaton or Automata Machine. Let’s explain the major types of Grammar, languages, and their acceptors.

**Types of Grammars**

There are four major types of grammars in the theory of Automata.

- Regular Grammar
- Context Free Grammar
- Context Sensitive Grammar
- Unrestricted Grammar

Let’s explain all the above types of Grammar in detail.

**1. Regular Grammar (RL)**

Regular Grammar generates the Regular Languages, and the Finite Automata Machine accepts all regular languages. 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. However, all regular languages and some infinite languages are accepted by DFA. |

**2. Context Free Grammar (CFG)**

Context-free Grammar generates Context-free Languages, and the Pushdown Automata Machine accepts all context-free languages. Context-free Grammar is also called Type-2 grammar.

Context Free languages are of two types

- Deterministic Context-Free Languages
- 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 context-sensitive languages, and linear bound automata machines accept all context-sensitive languages. Context-free Grammar is also called Type-1 grammar.

**Note:** Context-sensitive languages and their machines are not deterministic or non-deterministic.

**4. Unrestricted Grammar**

Unrestricted Grammar generates the Recursive enumerable Languages, and the Turing Machine accepts all Recursive enumerable languages. Unrestricted Grammar is also called Type-0 grammar.

Necessary: Type-0 Accepter has the Highest Power, and Type-3 accepter has the lowest Power. It means type -3 accepted, which means Turing Machine can accept all languages, whether regular, context-free, or context-sensitive. However, the Type-3 accepter, Finite Automata, can accept only regular languages. |

**Chomsky Hierarchy**

An explanation of all four types of Grammar is known as the Chomsky hierarchy. A diagram of Chomsky’s hierarchy is given below.