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

Grammar and its types in Automata

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

Regular languages are of two types.

  1. Finite Regular Languages
  2. Infinite Regular Languages

Finite Automata Machine is also of two types

  1. Deterministic Finite Automata (DFA)
  2. 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 Grammar in Automata

Context Free languages are of two types

  1. Deterministic Context-Free Languages
  2. Deterministic Context-Free Languages

Pushdown Automata Machine is also of two types

  1. Deterministic Pushdown Automata (DPDA)
  2. 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.

Context sensitive Grammar in Automata

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.

Unrestricted Grammar in Automata

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.

chomsky hierarchy