[go: up one dir, main page]
Scribd
Upload
221 views6 pages

Chomsky and Greibach Normal Form

Chomsky Normal Form is a restricted form of context-free grammars where productions are limited to one of three forms: A → a, A → BC, or S → ε. An algorithm is provided to convert any context-free grammar into Chomsky Normal Form by removing null/unit productions and ensuring at most two non-terminals on the right-hand side of each production. Greibach Normal Form is a similar restricted form where productions must be of the form A → aB1...Bn or S → ε. The document provides an algorithm to convert grammars to Greibach Normal Form by removing left-recursion and ensuring the proper form. Finally, pushdown automata are introduced as finite state machines

Uploaded by

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

Chomsky and Greibach Normal Form

Chomsky Normal Form is a restricted form of context-free grammars where productions are limited to one of three forms: A → a, A → BC, or S → ε. An algorithm is provided to convert any context-free grammar into Chomsky Normal Form by removing null/unit productions and ensuring at most two non-terminals on the right-hand side of each production. Greibach Normal Form is a similar restricted form where productions must be of the form A → aB1...Bn or S → ε. The document provides an algorithm to convert grammars to Greibach Normal Form by removing left-recursion and ensuring the proper form. Finally, pushdown automata are introduced as finite state machines

Uploaded by

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

Chomsky Normal Form

A CFG is in Chomsky Normal Form if the Productions are in the following forms –

 A→a
 A → BC
 S→ε

where A, B, and C are non-terminals and a is terminal.

Algorithm to Convert into Chomsky Normal Form −

Step 1 − If the start symbol S occurs on some right side, create a new start symbol S’ and a new
production S’→ S.

Step 2 − Remove Null productions. (Using the Null production removal algorithm discussed earlier)

Step 3 − Remove unit productions. (Using the Unit production removal algorithm discussed earlier)

Step 4 − Replace each production A → B1…Bn where n > 2 with A → B1C where C → B2 …Bn. Repeat this
step for all productions having two or more symbols in the right side.

Step 5 − If the right side of any production is in the form A → aB where a is a terminal and A, B are
non-terminal, then the production is replaced by A → XB and X → a. Repeat this step for every
production which is in the form A → aB.

Problem
Convert the following CFG into CNF

S → ASA | aB, A → B | S, B → b | ε

Solution
(1) Since S appears in R.H.S, we add a new state S0 and S0→S is added to the production set and it
becomes −

S0→S, S→ ASA | aB, A → B | S, B → b | ∈

(2) Now we will remove the null productions −

B → ∈ and A → ∈

After removing B → ε, the production set becomes −

1 NIST (auto)
S0→S, S→ ASA | aB | a, A → B | S | ∈, B → b

After removing A → ∈, the production set becomes −

S0→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) Now we will remove the unit productions.

After removing S → S, the production set becomes −

S0→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b

After removing S0→ S, the production set becomes −

S0→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA


A → B | S, B → b

After removing A→ B, the production set becomes −

S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA


A→S|b
B→b

After removing A→ S, the production set becomes −

S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA


A → b |ASA | aB | a | AS | SA, B → b

(4) Now we will find out more than two variables in the R.H.S

Here, S0→ ASA, S → ASA, A→ ASA violates two Non-terminals in R.H.S.

Hence we will apply step 4 and step 5 to get the following final production set which is in CNF −

S0→ AX | aB | a | AS | SA
S→ AX | aB | a | AS | SA
A → b |AX | aB | a | AS | SA
B→b
X → SA

(5) We have to change the productions S0→ aB, S→ aB, A→ aB

And the final production set becomes −

2 NIST (auto)
S0→ AX | YB | a | AS | SA
S→ AX | YB | a | AS | SA
A → b A → b |AX | YB | a | AS | SA
B→b
X → SA
Y→a

3 NIST (auto)
Greibach Normal Form
A CFG is in Greibach Normal Form if the Productions are in the following forms −

A→b
A → bD1…Dn
S→ε

where A, D1,....,Dn are non-terminals and b is a terminal.

Algorithm to Convert a CFG into Greibach Normal Form

Step 1 − If the start symbol S occurs on some right side, create a new start symbol S’ and a new
production S’ → S.

Step 2 − Remove Null productions. (Using the Null production removal algorithm discussed
earlier)

Step 3 − Remove unit productions. (Using the Unit production removal algorithm discussed
earlier)

Step 4 − Remove all direct and indirect left-recursion.

Step 5 − Do proper substitutions of productions to convert it into the proper form of GNF.
Problem

Problem

Convert the following CFG into CNF

S → XY | Xn | p
X → mX | m
Y → Xn | o

Solution

Here, S does not appear on the right side of any production and there are no unit or null productions in
the production rule set. So, we can skip Step 1 to Step 3.

Step 4

Now after replacing X in S → XY | Xo | p with mX | m


we obtain
4 NIST (auto)
S → mXY | mY | mXo | mo | p.

And after replacing X in Y → Xn | o with the right side of X → mX | m

we obtain Y → mXn | mn | o.

Two new productions O → o and P → p are added to the production set and then we came to the final GNF as
the following −

S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O→o
P→p

5 NIST (auto)
Pushdown Automata Introduction
Basic Structure of PDA

A pushdown automaton is a way to implement a context-free grammar in a similar way we design DFA for a
regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite
amount of information.

Basically a pushdown automaton is −

"Finite state machine" + "a stack"

A pushdown automaton has three components −

 an input tape,
 a control unit, and
 a stack with infinite size.

The stack head scans the top symbol of the stack.

A stack does two operations −

 Push − a new symbol is added at the top.


 Pop − the top symbol is read and removed.

A PDA may or may not read an input symbol, but it


has to read the top of the stack in every transition.

A PDA can be formally described as a 7-tuple (Q, ∑,


S, δ, q0, I, F) −

 Q is the finite number of states


 ∑ is input alphabet
 S is stack symbols
 δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*
 q0 is the initial state (q0 ∈ Q)
 I is the initial stack top symbol (I ∈ S)
 F is a set of accepting states (F ∈ Q)

A transition in a PDA from a state q1 to state q2, labeled


as a,b → c

This means at state q1, if we encounter an input string ‘a’ and top symbol of the stack is ‘b’, then we pop ‘b’,
push ‘c’ on top of the stack and move to state q2.

6 NIST (auto)

You might also like