Yioop - PHP Search Engine

-- Mar 25 In-Class Exercise

Initial CFG: S-> SS|(S)|a to GNF Change S-> SS to S -> SA, where A -> S Change S -> (S) to S -> (SB, where B -> )

S -> SA | (SB | a

Initial CFG: S-> SS|(S)|a to GNF Change S-> SS to S -> SA, where A -> S Change S -> (S) to S -> (SB, where B -> ) S -> SA | (SB | a

-- Mar 25 In-Class Exercise

(Edited: 2020-03-25)

((resource:Snapchat-1889897191.jpg|Resource Description for Snapchat-1889897191.jpg))

-- Mar 25 In-Class Exercise

Convert GNF: S -> SS | (S) | a Step 1: Get rid of S -> SS

	S -> aB, B -> S | SB
	S -> (S) | a

Step 2: Get rid of B -> S

	S -> aB, B -> a | aB | (S)
	S -> (S) | a

Step 3: Get rid of B -> (S)

	S -> aB, B -> a | aB | (SC, C -> )
	S -> (S) | a

Step 4: Get rid of S -> (S)

	S -> aB, B -> a | aB | (SC, C -> )
        S -> (SD | a, D -> )

Convert GNF: S -> SS | (S) | a Step 1: Get rid of S -> SS S -> aB, B -> S | SB S -> (S) | a Step 2: Get rid of B -> S S -> aB, B -> a | aB | (S) S -> (S) | a Step 3: Get rid of B -> (S) S -> aB, B -> a | aB | (SC, C -> ) S -> (S) | a Step 4: Get rid of S -> (S) S -> aB, B -> a | aB | (SC, C -> ) S -> (SD | a, D -> )

-- Mar 25 In-Class Exercise

Beginning: S -> SS | (S) | a

Converting S -> (S) S -> SS | (SA | a A -> ) Converting S -> SS S -> SS

 S -> aB
 B -> a | aS

Final result with C -> a S -> aB | (SA | C

 B -> C | CS
 A -> )

C -> a

Beginning: S -> SS | (S) | a Converting S -> (S) S -> SS | (SA | a A -> ) Converting S -> SS S -> SS S -> aB B -> a | aS Final result with C -> a S -> aB | (SA | C B -> C | CS A -> ) C -> a

-- Mar 25 In-Class Exercise

(Edited: 2020-03-25)

((resource:image0 (9).jpeg|Resource Description for image0 (9).jpeg))

-- Mar 25 In-Class Exercise

Given the grammar: S -> SS|(S)|a

Step 1:

             S -> SS|(SA|a
             A -> )

Step 2:

             S -> SS
             S -> aB
             B -> a | aS

Step 3:

             S -> aB | (SA | a
             B -> a | aS
             A -> )

Given the grammar: S -> SS|(S)|a Step 1: S -> SS|(SA|a A -> ) Step 2: S -> SS S -> aB B -> a | aS Step 3: S -> aB | (SA | a B -> a | aS A -> )

-- Mar 25 In-Class Exercise

S -> SS | (S) | a

Step 1 : S -> SS | (SA | a

              A-> )

Step 2 : S -> aC | (SA | a

               C -> S | aS | (SACS

Final : S -> aC | (SA | a

                C -> a | aS | (SACS
                A -> )

S -> SS | (S) | a Step 1 : S -> SS | (SA | a A-> ) Step 2 : S -> aC | (SA | a C -> S | aS | (SACS Final : S -> aC | (SA | a C -> a | aS | (SACS A -> )

-- Mar 25 In-Class Exercise

S->SS|(S)|a Step 1: Introduce new variables

 B -> )

The grammar S -> (SB S-> SS note that S->a. Step 2: S -> SS S -> aC C -> aS|a Final step 3 S -> aC | (SB | a S -> aS| a B -> )

(Edited: 2020-03-26)

S->SS|(S)|a Step 1: Introduce new variables B -> ) The grammar S -> (SB S-> SS note that S->a. Step 2: S -> SS S -> aC C -> aS|a Final step 3 S -> aC | (SB | a S -> aS| a B -> )

-- Mar 25 In-Class Exercise

S -> SS|(S)|a

Eliminate S -> (S):

      S -> SS|(SB|a 
      B -> )

Eliminate S -> SS:

      S -> aC|(SB|a 
      B -> )
      C -> S|SC

Eliminate C -> S:

      S -> aC|(SB|a 
      B -> )
      C -> aC|(SB|a|SC

Eliminate C -> SC:

      S -> aC|(SB|a 
      B -> )
      C -> aC|(SB|a|aCC|(SBC|aC

(Edited: 2020-03-27)

S -> SS|(S)|a '''Eliminate S -> (S): ''' S -> SS|(SB|a B -> ) '''Eliminate S -> SS:''' S -> aC|(SB|a B -> ) C -> S|SC '''Eliminate C -> S:''' S -> aC|(SB|a B -> ) C -> aC|(SB|a|SC '''Eliminate C -> SC:''' S -> aC|(SB|a B -> ) C -> aC|(SB|a|aCC|(SBC|aC

-- Mar 25 In-Class Exercise

initial CFG S -> SS | (S) | a changes S -> (S) => S -> (SA where A-> ) S -> SS => S -> (SAS | aS final Greibach Normal Form S -> (SA | aS | (SA | a A -> )