[go: up one dir, main page]
Scribd
Upload
524 views3 pages

Chomsky Classification of Grammars

dv

Uploaded by

PratikRoy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
524 views3 pages

Chomsky Classification of Grammars

dv

Uploaded by

PratikRoy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

3/25/2019 Chomsky Classification of Grammars

CHOMSKY CLASSIFICATION OF GRAMMARS


https://www.tutorialspoint.com/automata_theory/chomsky_classification_of_grammars.htm Copyright © tutorialspoint.com

Advertisements

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

Grammar Grammar Accepted Language Accepted Automaton


Type

Type 0 Unrestricted grammar Recursively enumerable Turing Machine


language

Type 1 Context-sensitive Context-sensitive language Linear-bounded


grammar automaton

Type 2 Context-free grammar Context-free language Pushdown automaton

Type 3 Regular grammar Regular language Finite state automaton

Take a look at the following illustration. It shows the scope of each type of grammar −

Type - 3 Grammar
Type-3 grammars generate regular languages. Type-3 grammars must have a single non-terminal on the
left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-

https://www.tutorialspoint.com/cgi-bin/printpage.cgi 1/3
3/25/2019 Chomsky Classification of Grammars

terminal.

The productions must be in the form X → a or X → aY

where X, Y ∈ N N onterminal

and a ∈ T T erminal

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

Example

X → ε
X → a | aY
Y → b

Type - 2 Grammar
Type-2 grammars generate context-free languages.

The productions must be in the form A → γ

where A ∈ N N onterminal

and γ∈T ∪ N * S tringof terminalsandnon − terminals .

These languages generated by these grammars are be recognized by a non-deterministic pushdown


automaton.

Example

S → X a
X → a
X → aX
X → abc
X → ε

Type - 1 Grammar
Type-1 grammars generate context-sensitive languages. The productions must be in the form

αAβ→αγβ

where A ∈ N N on − terminal

and α, β, γ ∈ T ∪ N * S tringsof terminalsandnon − terminals

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

The rule S → ε is allowed if S does not appear on the right side of any rule. The languages generated by these
grammars are recognized by a linear bounded automaton.

Example

AB → AbBc
A → bcA
B → b

https://www.tutorialspoint.com/cgi-bin/printpage.cgi 2/3
3/25/2019 Chomsky Classification of Grammars

Type - 0 Grammar
Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They
are any phase structure grammar including all formal grammars.

They generate the languages that are recognized by a Turing machine.

The productions can be in the form of α → β where α is a string of terminals and nonterminals with at least
one non-terminal and α cannot be null. β is a string of terminals and non-terminals.

Example

S → ACaB
Bc → acB
CB → DB
aD → Db

https://www.tutorialspoint.com/cgi-bin/printpage.cgi 3/3

You might also like