1. (10 points) (10 pts.) Give a context-free grammar to generate the language of

Question

1. (10 points) (10 pts.) Give a context-free grammar to generate the language of binary strings whose third rightmost symbol is a I 2. (10 pts.) a) Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL that is generated by the CFG G with start state S. Add the new rule S->SS and call the resulting grammar G'. This grammar is supposed to generate A b) Show that the class of context-free languages is closed under the regular operations: union, concatenation, and star. You MUST use CFGs S. 3. cio pts.) Convert to an equivalent PDA the following CFG G=(STU),{0,1},SP where P is the following set of production rules:

Explanation / Answer

1.

S -> 0S|1S|1C

C ->0D|1D

D -> 0 | 1

Here is context free grammer whose third rightmost symbol is 1

Basically this is making sure that when a string's third last charcter is generated its 1 and then it can be either 00,01,10,11 using C and D here

Answered first one as per chegg's policy

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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