Chomsky Classification of Grammars - Automata Theory

What is Chomsky Classification of Grammars?

As per the Noam Chomosky, four types of grammars are there including − Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other −

Grammar Type Grammar Accepted Language Accepted Automaton

Type 0 Unrestricted grammar Recursively enumerable language Turing Machine
Type 1 Context-sensitive grammar Context-sensitive language Linear-bounded automaton
Type 2 Context-free grammar Context-free language Pushdown automaton
Type 3 Regular grammar Regular language Finite state automaton

Let’s take a look at the following diagram. It shows the scope of each type of grammar −

containment_of_type3_type2_type1_type0.

Type - 3 Grammar

Type-3 grammars usually create regular languages. Type-3 grammars should have a single non-terminal on the left-hand side and a right-hand side which includes a single terminal or single terminal followed by a single non-terminal.

Make sure that the productions must be in the form X → a or X → aY

where X, Y ∈ N (Non terminal)

and a ∈ T (Terminal)

The rule S → ε is allowed if S does not appear on the right side of any rule.

Example

Type - 2 Grammar

Type-2 grammars usually create context-free languages.

Make sure that the productions must be in the form A → γ

where A ∈ N (Non terminal)

and γ ∈ (T ∪ N)* (String of terminals and non-terminals).

However these languages generated by these grammars are mostly recognized by a non-deterministic pushdown automaton.

Example

Type - 1 Grammar

While, Type-1 grammars create context-sensitive languages. Make sure that the productions must be in the form

α A β → α γ β

where A ∈ N (Non-terminal)

and α, β, γ ∈ (T ∪ N)* (Strings of terminals and non-terminals)

The strings α and β might be null, but γ must be non-empty.

The rule S → ε is accepted when S does not appear on the right side of any rule. The languages created by these grammars are found by a linear bounded automaton.

Example

Type - 0 Grammar

Type-0 grammars create recursively enumerable languages. Here there are no restrictions for the productions. They are many phase structure grammar available for all formal grammars.

Usually they generate the languages that are recognized by a Turing machine.

Let’s assume that all the productions must be in the form of α → β where α is a string of terminals and non-terminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals.

Example

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics