-- Mar 18 In-Class Exercise

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

-- Mar 18 In-Class Exercise

* S -> SS|(S)|a * S0 -> SA1 * A1 -> SB1 * B1 -> (SC1 * C1 -> )a

-- Mar 18 In-Class Exercise

We want to convert the context-free grammar S -> SS | (S) | a into Chomsky Normal Form. First, we add a new start variable S_0. The context-free grammar now looks like this. S_0 -> S, S -> SS | (S) | a. Second, we take care of all epsilon-rules. This context-free grammar has none, so we move onward! Third, we handle all unit rules. Again, this language does not have any, so we move forward. Fourth, we convert all remaining rules to Chomsky Normal Form, except for the rules S -> a, and S -> SS, because those are already in the correct forms for Chomsky Normal Form. Let's convert the rule S -> (S). This yields the rules S -> (A_1 and A_1 -> S). Now, we want to "clean up" the rules S -> (A_1 and A_1 -> S) so that they are in the correct form for Chomsky Normal Form. To do this, we replace the terminal symbols in the previous two, newly created rules with new variables and create two more rules like so: S -> P_1 A_ 1 and A_1 -> SP_2. We also want to add rules P_1 -> ( and P_2 -> ). After combining all of these new rules, which I have grouped together below for your convenience, and removing all the rules that are not in the correct form for Chomsky Normal Form, i.e., the rules S -> (S), S -> (A_1, and A_1 -> S), we can say that we have converted the original context-free grammar S -> SS | (S) | a into Chomsky Normal Form. S_0 -> S S -> SS S -> P_1 A_1 A_1 -> SP_2 S -> a P_1 -> ( P_2 -> ).

-- Mar 18 In-Class Exercise

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

-- Mar 18 In-Class Exercise

((resource:IMG_2604.jpg|Resource Description for IMG_2604.jpg))

-- Mar 18 In-Class Exercise

((resource:WechatIMG305.jpeg|Resource Description for WechatIMG305.jpeg))

-- Mar 18 In-Class Exercise

S→SS|(S)|a 1. Add new variable. S_0 -> S, S -> SS|(S)|a 2. Remove epsilon rules. (None, so grammar stays the same) S_0 -> S, S -> SS|(S)|a 3. Remove unit rules. S_0 -> SS|(S)|a S -> SS|(S)|a 4. Split up rules with RHS of length longer than 2. S_0 -> SS S_0 -> (B, B -> S) S_0 -> a S -> SS S -> (D, D -> S) S -> a 5. Put each rule with RHS of length 2 into correct format. S_0 -> SS S_0 -> AB, A -> (, B -> SB_1, B_1 -> ) S_0 -> E, E -> a S -> SS S -> CD, C -> (, D -> SD_1, D_1 -> ) S -> F, F -> a

-- Mar 18 In-Class Exercise

((resource:WechatIMG1444.jpeg|Resource Description for WechatIMG1444.jpeg))

-- Mar 18 In-Class Exercise

S -> SS | (S) | a Add new start var + rule S0 -> S Remove e-rules: N/A Handle unit rules A -> B: S0 -> SS | (S) | a S -> SS | (S) | a Convert remaining rules to proper form if length of RHS >= 3 length of (S) = 3 S -> (S): S1 -> (S2 S2 -> SS3 S3 -> ) Final form: S0 -> SS | A1 | a A1 -> (A2 A2 -> SA3 A3 -> ) S -> SS | B1 | a B1 -> (B2 B2 -> SB3 B3 -> )

-- Mar 18 In-Class Exercise

((resource:IMG_0239.jpeg|Resource Description for IMG_0239.jpeg))