Mar 18 In-Class Exercise .
Please post your solutions to the March 18 In-Class Exercise to this thread.
Best,
Chris
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: 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) |
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)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)
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)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