Skip to main content
2 of 6
Nothing about regular languages in this Q
rici
  • 12.1k
  • 22
  • 39

Context Free Grammar - Starting with x Number of Chars and Ending with n != x Number of Chars

I am trying to create a context free grammar in [Extended Backus–Naur form][1], which starts with a non-empty sequence of A's and is followed by a non-empty sequence of B's. With the special condition that the number of B's has to be unequal to the number of A's.

Thus, the grammar should generate words like:

  • AAAABBB
  • AAABB
  • ABBB

So basically I could do something like this:

$\ G=(N,T,P,Sequence)$

$\ N = \{Sequence\}$

$\ T = \{A,B\}$

$\ P = \{Sequence=AA(Sequence|\epsilon)B\}$

But then the words would always have $\ 2n$ A's and n B's:

  • AAB
  • AAAABB
  • AAAAAABBB

So how is it possible to make the number of A's uncorrelated of the number of B's, without being equal? [1]: https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form