Question

Given the following Grammar G, S->ASB A-> AS a B-> Sbs Albb (a) Identify and remove the A-productions. (b) Identify and remove unit-productions from the result of (a). (c) Convert it to Chomsky Normal Form.

Answer 1

S0 -> S
S -> ASB
A -> aAS | a | epsilon
B -> SbS | A | bb

a)

Removed A -> epsilon

S0 -> S
S -> ASB | SB
A -> aAS | a | aS
B -> SbS | A | bb | epsilon

Removed B -> epsilon

S0 -> S
S -> ASB | SB | S
A -> aAS | a | aS
B -> SbS | A | bb

b)

S0 -> ASB | SB
S -> ASB | SB
A -> aAS | a | aS
B -> SbS | aAS | a | aS | bb

c)

Remove mixed productions

S0 -> ASB | SB
S -> ASB | SB
A -> CAS | a | CS
B -> SDS | CAS | a | CS | DD
C -> a
D -> b

Change to CNF

S0 -> EB | SB
S -> EB | SB
A -> FS | a | CS
B -> GS | FS | a | CS | DD
C -> a
D -> b
E -> AS
F -> CA
G -> SD

PLEASE UP VOTE