Question

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

Answer 1

Solution:

Given grammar,

S -> ASB

A -> aAS | a | $\lambda$

B -> SbS | A | bb

(a)

Explanation:

=>Epsilon productions are production rules which contains epsilon($\lambda$).

=>Epsion production = A -> $\lambda$

Removing epsilon production:

=>Place the combination with and without epsilon to remove epsilon production.

S -> ASB | SB

A -> aAS | a | aS

B -> SbS | A | bb

(b)

Explanation:

=>Unit productions are of type X -> Y where X can be set of non terminals and Y is single non terminal.

=>Unit productions = B -> A

Removing unit production:

=>Replace the value of A in place of A to remove unit production.

S -> ASB | SB

A -> aAS | a | aS

B -> SbS | aAS| a | aS | bb

(c)

Explanation:

Converting into Chomsky normal form(CNF):

Step 1:

=>As start symbol S appears at the right hand side of production so addig a new production rule S1 -> S

S1 -> S

S -> ASB | SB

A -> aAS | a | aS

B -> SbS | aAS| a | aS | bb

Step 2:

=>Removing unit production S1 -> S

S1 -> ASB | SB

S -> ASB | SB

A -> aAS | a | aS

B -> SbS | aAS| a | aS | bb

Step 3:

=>Converting into the fors X -> YZ, T -> a

S1 -> PB | SB

S -> PB | SB

A -> TS | a | QS

B -> US | TS | a | QS | RR

P -> AS

Q -> a

R -> b

T -> QS

U -> SR

I have explained each and every part with the help of statements attached to it.