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

Grammar and its types in Automata

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 Grammar in Automata

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.

Context sensitive Grammar in Automata

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.

Unrestricted Grammar in Automata

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.