Yioop - PHP Search Engine

Mar 18 In-Class Exercise.

Please post your solutions to the March 18 In-Class Exercise to this thread.

Best,

Chris

Please post your solutions to the March 18 In-Class Exercise to this thread. Best, Chris

-- Mar 18 In-Class Exercise

Step 1:

 S0 -> S
 S -> SS|(S)|a

Step 2:

 No e rules.

Step 3:

 S0 -> SS|(S)|a
 S -> SS|(S)|a

Step 4:

 S0 -> SS|(S1|a
 S -> SS|(S2|a
 S1 -> S)
 S2 -> S)

Step 5:

 S0 -> SS|P1S1|a
 S -> SS|P2S2|a
 S1 -> SP3
 S2 -> SP4
 P1 -> (
 P2 -> (
 P3 -> )
 P4 -> )

(Edited: 2020-03-18)

Step 1: S0 -> S S -> SS|(S)|a Step 2: No e rules. Step 3: S0 -> SS|(S)|a S -> SS|(S)|a Step 4: S0 -> SS|(S1|a S -> SS|(S2|a S1 -> S) S2 -> S) Step 5: S0 -> SS|P1S1|a S -> SS|P2S2|a S1 -> SP3 S2 -> SP4 P1 -> ( P2 -> ( P3 -> ) P4 -> )

-- Mar 18 In-Class Exercise

Step 1: Add new start variable to get: S0 -> S, S -> SS|(S)|a Step 2: Remove ε rules. In this case, there aren't any so we still S0 -> S, S -> SS|(S)|a Step 3: Remove unit rules. We only have one involving

 S0 -> SS|(S)|a, S -> SS|(S)|a

Step 4: Split up rules with RHS of length longer than 2

 S0 -> SS|( A1| a
 S -> SS|( B1|a
 A1 -> S)
 B1 -> S)

Step 4: Split up rules with RHS of length longer than 2

 S0 -> SS|A2, A2 ->( A1| a, A1 -> S)

 S -> SS|( B1|a, B2 ->( B1|a, B1 -> S)
 ----------------------------------------------------

S0 -> SS|A2, A2 -> ( A3, A3 -> A1| a, A1 -> S) S -> SS|( B1|a, B2 ->( B3, B3 -> B1|a B1 -> S)

(Edited: 2020-03-21)

Step 1: Add new start variable to get: S0 -> S, S -> SS|(S)|a Step 2: Remove ε rules. In this case, there aren't any so we still S0 -> S, S -> SS|(S)|a Step 3: Remove unit rules. We only have one involving S0 -> SS|(S)|a, S -> SS|(S)|a Step 4: Split up rules with RHS of length longer than 2 S0 -> SS|( A1| a S -> SS|( B1|a A1 -> S) B1 -> S) Step 4: Split up rules with RHS of length longer than 2 S0 -> SS|A2, A2 ->( A1| a, A1 -> S) S -> SS|( B1|a, B2 ->( B1|a, B1 -> S) ---------------------------------------------------- S0 -> SS|A2, A2 -> ( A3, A3 -> A1| a, A1 -> S) S -> SS|( B1|a, B2 ->( B3, B3 -> B1|a B1 -> S)

-- Mar 18 In-Class Exercise

S -> SS | (S) | a

add start variable

S0 -> S

S -> SS | (S) | a

remove e rules

S0 -> S

S -> SS | (S) | a

remove unit rules

S0 -> SS | (S) | a

S -> SS | (S) | a

split up rules w/ > 2 things on RHS

S0 -> SS | AB | a

A -> (

B -> S)

S -> SS | CD | a

C -> (

D -> S)

put all rules into correct format

S0 -> SS | AB | a

A -> (

B -> SB2

B2 -> )

S -> SS | CD | a

C -> (

D -> SD2

D2 -> )

(Edited: 2020-03-18)

S -> SS | (S) | a add start variable S0 -> S S -> SS | (S) | a remove e rules S0 -> S S -> SS | (S) | a remove unit rules S0 -> SS | (S) | a S -> SS | (S) | a split up rules w/ > 2 things on RHS S0 -> SS | AB | a A -> ( B -> S) S -> SS | CD | a C -> ( D -> S) put all rules into correct format S0 -> SS | AB | a A -> ( B -> SB2 B2 -> ) S -> SS | CD | a C -> ( D -> SD2 D2 -> )

-- Mar 18 In-Class Exercise

my new line characters aren't working starting language: S→SS|(S)|a

add start variable S0→S no epsilon transitions, no unit productions except S0

now convert to normal form S→(S) k >= 3 S→(A1 A1→S)

Replace Terminals

S→P0A1 P0→( A1→SP1 P1→)

(Edited: 2020-03-18)

my new line characters aren't working starting language: S→SS|(S)|a add start variable S0→S no epsilon transitions, no unit productions except S0 now convert to normal form S→(S) k >= 3 S→(A1 A1→S) Replace Terminals S→P0A1 P0→( A1→SP1 P1→)

-- Mar 18 In-Class Exercise

(Edited: 2020-03-18)

((resource:03-18-2020_Formal Languages.png|Resource Description for 03-18-2020_Formal Languages.png))

-- Mar 18 In-Class Exercise

(Edited: 2020-03-18)

((resource:Screen Shot 2020-03-18 at 4.18.36 PM.png|Resource Description for Screen Shot 2020-03-18 at 4.18.36 PM.png))

-- Mar 18 In-Class Exercise

S -> SS|(S)|a

step 1 to add S0

 S0 -> S

 S -> SS|(S)|a

step 2 remove e rules, but there's none so skip

Step 3 remove unit rules

S0 -> SS|(S)|a

 S -> SS|(S)|a

Step 4: Split up rules with RHS of length longer than 2:

S0 -> SS | A1A2 | a

A1 -> (

A2 -> S)

S -> SS | B1B2 | a

B1 -> (

B2 -> S)

Step 5: Put each rule with RHS of length 2 into the correct format:

S0 -> SS | A1A2 | a

A1 -> (

A2 -> SA3

A3 -> )

S -> SS | B1B2 | a

B1 -> (

B2 -> SB3

B3 -> )

(Edited: 2020-03-18)

S -> SS|(S)|a step 1 to add S0 S0 -> S S -> SS|(S)|a step 2 remove e rules, but there's none so skip Step 3 remove unit rules S0 -> SS|(S)|a S -> SS|(S)|a Step 4: Split up rules with RHS of length longer than 2: S0 -> SS | A1A2 | a A1 -> ( A2 -> S) S -> SS | B1B2 | a B1 -> ( B2 -> S) Step 5: Put each rule with RHS of length 2 into the correct format: S0 -> SS | A1A2 | a A1 -> ( A2 -> SA3 A3 -> ) S -> SS | B1B2 | a B1 -> ( B2 -> SB3 B3 -> )

-- Mar 18 In-Class Exercise

Step 1: Add new S0

		S0 →  S
		S → SS
		S → (S)
		S → a

Step 2: Get rid of e rules

		Nothing, so keep the same set

Step 3: Get rid of unit rules

		S0 →  SS
		S0 →  (S)
		S0 →  a
		S → SS
		S → (S)
		S → a

Step 4: Get rid of length > 2

		S0 →  SS
		S0 →  (A1
		A1 → S)
		S0 →  a
		S → SS
		S → (A2
		A2 → S)
		S → a

Step 5: Convert to acceptable form

		S0 →  SS
		S0 →  B1A1
		B1 → (
                A1 → SB2
		B2 → )	
                S0 →  a
		
                S → SS
		S → B3A2
		B3 → (	
                A2 → SB4
                B4 → )
		S → a

Step 1: Add new S0 S0 → S S → SS S → (S) S → a Step 2: Get rid of e rules Nothing, so keep the same set Step 3: Get rid of unit rules S0 → SS S0 → (S) S0 → a S → SS S → (S) S → a Step 4: Get rid of length > 2 S0 → SS S0 → (A1 A1 → S) S0 → a S → SS S → (A2 A2 → S) S → a Step 5: Convert to acceptable form S0 → SS S0 → B1A1 B1 → ( A1 → SB2 B2 → ) S0 → a S → SS S → B3A2 B3 → ( A2 → SB4 B4 → ) S → a

-- Mar 18 In-Class Exercise

(Edited: 2020-03-18)

((resource:20200318_162836.jpg|Resource Description for 20200318_162836.jpg))