Yioop - PHP Search Engine

-- Mar 25 In-Class Exercise

Given: S → SS | (S) | a Step 1: Introduce rule P → ) and replace in S → (S)

	S → SS | (SP | a
	P → )

Step 2: Replace S → SS by adding new rules with variable C

	S → (SAC
	C → S
	C → SC

Step 3: Same as Step 2 but using new variable D

	S → aD
	D → S
	D → SD

Final:

	S → SS | (SP | a | (SAC | aD	C → S | SC
	P → )				D → S | SD

Given: S → SS | (S) | a Step 1: Introduce rule P → ) and replace in S → (S) S → SS | (SP | a P → ) Step 2: Replace S → SS by adding new rules with variable C S → (SAC C → S C → SC Step 3: Same as Step 2 but using new variable D S → aD D → S D → SD Final: S → SS | (SP | a | (SAC | aD C → S | SC P → ) D → S | SD

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

-- Mar 25 In-Class Exercise

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

Step 1:

S -> aC | (S) | a C-> S

Step 2:

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

Step 3:

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

(Edited: 2020-03-30)

CFG: S -> SS | (S) | a Step 1: S -> aC | (S) | a C-> S Step 2: S -> aC | (SB | a C-> S B -> ) Step 3: S -> aC | (SB | a C-> a | aS B -> )

-- Mar 25 In-Class Exercise

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

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

-- Mar 25 In-Class Exercise

Hamir here.

Here is how I would convert the context-free grammar S -> SS | (S) | a into Greibach Normal Form.

We add a new variable N and add the rules S -> (S)N, N -> S, and N -> SN.

We also add a new variable O and add the rules S -> aO, O -> S, and O -> SO.

The context-free grammar now appears as follows: S -> (S) | a | (S)N | aO N -> S | SN O -> S | SO.

And, I'm not sure where I should go from here. What should I do next?

Hamir here. Here is how I would convert the context-free grammar S -> SS | (S) | a into Greibach Normal Form. We add a new variable N and add the rules S -> (S)N, N -> S, and N -> SN. We also add a new variable O and add the rules S -> aO, O -> S, and O -> SO. The context-free grammar now appears as follows: S -> (S) | a | (S)N | aO N -> S | SN O -> S | SO. And, I'm not sure where I should go from here. What should I do next?

-- Mar 25 In-Class Exercise

S -> SS | (S) | a

1. S -> SS | (SB | a

    B -> )

2. S -> aC | (SB | a

    C -> S | aS | (SBCS

3. S -> aC | (SB | a

    C -> a | aS | (SBCS
    B -> )

(Edited: 2020-04-03)

S -> SS | (S) | a 1. S -> SS | (SB | a B -> ) 2. S -> aC | (SB | a C -> S | aS | (SBCS 3. S -> aC | (SB | a C -> a | aS | (SBCS B -> )

-- Mar 25 In-Class Exercise

1 : S -> SS | (SA | a A-> ) 2 : S -> aC | (SA | a. C -> S | aS | (SACS Greibach Normal Form Final:

                S -> aC |(SA| 
                C -> a |aS| (SACS
                A -> )

1 : S -> SS | (SA | a A-> ) 2 : S -> aC | (SA | a. C -> S | aS | (SACS Greibach Normal Form Final: S -> aC |(SA| C -> a |aS| (SACS A -> )

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

Step 3:

     S -> aC | (SB | a
     C -> a | aS | (SBCS
     B -> )

(Edited: 2020-04-05)

'''S -> SS | (S) | a''' '''Step 1: ''' S -> SS | (SB | a B -> ) '''Step 2:''' S -> aC | (SB | a C -> S | aS | (SBCS '''Step 3:''' S -> aC | (SB | a C -> a | aS | (SBCS B -> )

-- Mar 25 In-Class Exercise

S -> SS | (S) | a 1.

 S -> SS | (SC | a
 C -> )

2. S -> SS | aC D -> a | aS 3. S -> aD | SC | a D -> a | aS C -> )

S -> SS | (S) | a 1. S -> SS | (SC | a C -> ) 2. S -> SS | aC D -> a | aS 3. S -> aD | SC | a D -> a | aS C -> )

-- Mar 25 In-Class Exercise

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

        A -> )

Step 2: S -> SS

        S -> aB
        B -> aS|a

Step 3: S -> aB|(Sa|a

        B -> aS|a
        A -> )

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