Design context-free grammars for the following languages. Using your grammar, gi

Question

Design context-free grammars for the following languages. Using your grammar, give derivations for the example strings: 1. L = {wl w is the set of strings over 0,1 that are of the form on 12n for n>=01 example: 001111, 011. a. (w w is the set of strings over a,b that has equal numbers of a's and b's in any order) example: baab abab, ba, ?. b. L c. L = {w| w is the set of strings over 0,1 that are of the form 0n1mOn for mene0 L = {w| w is the set of strings over ab with odd length and contain exactly 2 b) example: bba, aababaa, d.

Explanation / Answer

Q1
a) L={w|w is the set of strings over 0,1 that are of the form 0^n1^2n for n>=0}
so the context free grammer will be
S->0S11
S->?

so for example
001111

S-> 0S11
S->00S1111 S->0S11
S->001111 S->?

b)
L={w|w is the set of strings over a,b that has equal number of a's and b's in any order}

S->aSbS
S->bSaS
S->?

for example
string abbbaa

S-> aSbS -> abS -> abbSaS->abbbSaSaS -> abbbaSaS -> abbbaaS -> abbbaa

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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