Search code examples
theorycontext-free-grammarcontext-free-language

Design a context free grammar language where length of a = double length of b


I would like to know if someone can help me designing a context free grammar

for a language where { w | |w|a=2|w|b }

for example w=aab , aaaabb , aaaaaabbb ,baa , aba , aabbaaaba ...

S-> aab | baa | aba | SS | abSa | baSa | aaSb | bSaa would not generate aaabba.

So my next question is , isn't it too ambiguous to have a grammar that looks like this ->

**

S-> aab | baa | aba | aSab | aSba | aaSb |abSa |aabS | abaS | Saab | Saba | Sbaa | SS | bSaa | baSa | baaS ?

**

Thank you in advance


Solution

  • None of the grammars you posted can product aaabba, you need something like this:

    S-> HaSa | aHSa | aSHa | aSaH | HSaa | SHaa | SaHa | SaaH | HaaS | aHaS | aaHS | aaSH | epsilon

    H -> b

    It can probably be done with a shorter grammar, but I think this will do.