= { a, b, c }, design a context-free grammar G such that L(G) equals the complem

Question

= { a, b, c }, design a context-free grammar G such that L(G) equals the complement of { an bn cn : n 0 }

To do this we can: 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 Aq for each state q. Then convert arcs (p, c, q) into rules Ap cAq, plus Ap c if q is a final state of M' . Call the new grammar G' and use G' as an option from the start symbol S of G to handle strings not of the form a b c . Now 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 a or c cases.

Explain why this shows that the class of context-free languages is not closed under complementation.

Explanation / Answer

To show that the context - free languages is not closed under complementation , Consider that L1 and L2 are context free languages , then Let L1 = {am bm cn : m, n 0} and let L2 = {am bn cn : m, n 0}, the intersection of two languages is not context free given by L1 L2 .

By complementing   L1 L2 we get as, ~(~L1 ~L2), L1 is the complement of ~L1 , Therefore if context free langauge was closed under complement then it would have closed under intersection , Since they are not closed under intersection they are not slosed under complementation.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.