Question: With sigma = {a, b, c}, design a context-free grammar G such that L(G) equals the complement of {a^n b^n c^n: n greaterthanorequalto 0}. Here

With sigma = {a, b, c}, design a context-free grammar G such that L(G) equals the complement of {a^n b^n c^n: n greaterthanorequalto 0}. Here is an effective recipe for building G: First design a DFA M such that L(M) = a* b* c*. Then complement the DFA to get M' such that L(M) = ~ a* b* c*. Next, allocate a variable A_q for each state q. Then convert arcs (p, c, q) into rules A_p rightarrow cA_q, plus A_p rightarrow c if q is a final state of M'. This is not in the text-for a pictorial example, see pages 10 and 11 of these notes (click here); the process should also remind you of part 2(b) on Assignment 2. Call the new grammar G". Now use G" as an option from the start symbol S of G to handle strings not of the form a* b* c*. Now on the other "fork" you need to handle strings that do have this form but don't have their numbers of a's, b's, and c's all equal. Write those inequalities as further disjunctions of > and and
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
