CODEWITHSUNDEEP
theorycontext-free-grammarcontext-free-language
Zok
Zok

Reputation: 365

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

Upvotes: 0

Views: 683

Answers (2)

Psycarlo
Psycarlo

Reputation: 11

Try this one:

S  -> ε | S1 S
S1 -> ε | aaS1bS1 | bS1aaS1 | aS1bS1a

Upvotes: 1

user2268997
user2268997

Reputation: 1391

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.

Upvotes: 1

Related Questions