CODEWITHSUNDEEP
context-free-grammar
user751173
user751173

Reputation:

Creating a context-free grammar for a given language

I am given the language

{b a^m1 ba^m2 ba^m3 .... ba^mn | n >= 2, m1,...,mn >= 0, and mi != mj for some i.j}

That is, it strings with beginning with a b and at least 2 b's and somewhere a different number of a's between them. E.g., "bab", "bba", "bbba", "babbab",... but not "bb", "baba", "babaaba",...

How can I create a CFG for this language.

I already have something the following but I can't seem to make it complete it for more than 2 b's; I'm also not so sure if my general approach is correct.

 S -> bAbaA | baAbA.
 A -> aaA  | ε.

Upvotes: 0

Views: 412

Answers (1)

Charlie Martin
Charlie Martin

Reputation: 112404

The first thing to do is apply the pumping lemma for CFGs and make sure that is a CFG. First glance looks like it may not be.

Upvotes: 1

Related Questions