Are the following languages context-fiee or not? If yes, specify a context-free

Question

Are the following languages context-fiee or not? If yes, specify a context-free grammar in BNF notation that generates the language. If not, give an informal argument. 2. {anync" l m>n20,o>0} , with alphabet ={a, b, c} 3. { anne, I n > 0} , with alphabet = {a, b, c} 4, { OP'l3n I n 0 }, with alphabet {0, 1} 5, {uu,a IwErand u,a is w in reverse ), with alphabet ={a, b} 6, { anynend" I n 0, m 0 }, with allhalet = {a, b, c, d} 7. { anyy4?" I n 2 0, m 0 }, with allhalet = {a, b, c, d} 8. { annend" I 112 0, m > 0 }, with allhalet = {a, b, c, d} 9. { ananWW, I n > 0 }, with alphabet -(a, b} 10. {wlwhas more than 3 symbols), with alphabet ={a, b} Which of the languages are also regular languages, i.e., can be expressed by a regular expression? Prove it by giving the regular expression that specifies the language.

Explanation / Answer

1) S -> aS1
S1 -> aS1 | B |
B -> bB | cC
C -> cC |

2) S -> aS1
S1 -> aS1b | aS1 | cC
C -> cC |

3) This example is not context-free. An informal arguement would be, it will be impossible to keep track of three variable at once for a CFG. It can only keep track of two variables.

4) S -> 00S111 |

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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