Post your solutions to the Mar 25 In-Class Exercise to this thread.

Best,

Chris

initial CFG

S -> SS | (S) | a

changes

S -> (S) => S -> (SB

where B -> )

S -> a is fine

S -> SS => S -> (SBS | aS

final Greibach Normal Form

S -> (SBS | aS | (SB | a

B -> )

S -> SS | (S) | a

Step 1: S -> SS | (ST | a T -> )

Step 2: S -> (STR | aR | a R -> (STR | aR | a T -> )

First introduce U -> )

and replace S -> (SU

then for S-> SS note that S->a. Add the following rules:

S->aC

C->S

C->SC

Now we remove unit productions for C->S, add:

C->(SU|a

Fix C-> SC by substituting S productions for S:

C->aCC|(SUC|aC

This gives us the following rules:

S->aC|(SU|a

C->aCC|(SU|(SUC|aC|a

U->)

S -> SS | (S) | a S -> SS needs to change to S -> SA, A -> S S -> (S) needs to change to S -> (SB, B -> ) S -> a

Intital Grammar: S->SS | (S) | a

Step1: S->SS | (SA | a, A->)

Step2: S->aB | (SA | a, A->), B->S | SB

Step3: S->aB | (SA | a, A->), B->aS | aSB

S -> SS | (S) | a

Step 1: S -> SS | (SP | a P -> )

Step 2: S -> SS S -> aC C -> a | aS

Final: S -> aC | (SP | a C -> a | aS P -> )

Convert S -> SS | (S) | a to GNF

Converting S -> (S):

S -> SS

S -> (SP

P -> )

S -> a

Converting S -> SS

S -> aB

B -> aBS

S -> (SPC

C -> (SPCS

S -> (SP

P -> )

S -> a

Convert to GNF Given: S->SS|(S)|a

Convert S->(S): S->(SP P->)

Introduce new variable A with rule A->S S->SA|(SP|a P->)

S -> SS | (S) | a

Step 1 : S -> SS | (SB | a B-> )

Step 2 : S -> aC | (SB | a C -> S | aS | (SBCS Final : S -> aC | (SB | a C -> a | aS | (SBCS B -> )