Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?

"Construct CFG that generates all strings having equal number of a's
and b's"

My attempt:

X = 1 + aXa + aaX +Xaa + bXb + Xbb +bbX +YY
Y = 1 + (a+b)Y

looks too complicated for such concise problem statement. Any shorter
solution?
.

Relevant Pages

  • Re: Regex - Ensure 0,1 occurrences from a list of possibilities
    ... 21 characters shorter with Jesse's suggestion ... You could make that much shorter by making permutations like ... matching strings with a 1 time use program. ... D-11 (repeated digit) ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: reordering elements of a list
    ... greenflame wrote: ... elements and another list (which is may shorter, ... Also by the way the main list is always going to be a list of strings ... But you can also do it with list comprehension pretty easily, so this is probably just a shameless plug for NumPy :-) ...
    (comp.lang.python)
  • Re: Regex - Ensure 0,1 occurrences from a list of possibilities
    ... 21 characters shorter with Jesse's suggestion (and even less pretty ... Shorter is always better;). ... the matching strings with a 1 time use program. ... D-11 (repeated digit) ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Nylon string question
    ... I know) a 25 1/2 scale on nylon strings even though there are shorter ... To play any given note on a longer scale lengths requires higher tension ...
    (uk.music.guitar)
  • Re: Substring matching in lots of strings
    ... one character but shorter than 64). ... the user can start typing one or more words, ... So if I have these strings: ... If the input is "a b c" will the words containing these letters need to be ...
    (comp.programming)