Yioop - PHP Search Engine

Mar 25 In-Class Exercise.

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

Best,

Chris

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

-- Mar 25 In-Class Exercise

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 -> )

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 -> )

-- Mar 25 In-Class Exercise

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

(Edited: 2020-03-25)

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

-- Mar 25 In-Class Exercise

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->)

(Edited: 2020-03-25)

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->)

-- Mar 25 In-Class Exercise

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

(Edited: 2020-03-25)

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

-- Mar 25 In-Class Exercise

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

(Edited: 2020-03-25)

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

-- Mar 25 In-Class Exercise

 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 -> )

(Edited: 2020-03-25)

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 -> )

-- Mar 25 In-Class Exercise

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

(Edited: 2020-03-25)

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

-- Mar 25 In-Class Exercise

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->)

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->)

-- Mar 25 In-Class Exercise

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 -> )

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 -> )