0

I'm having trouble to find context free grammars which generate following languages a* (ba* ba*)*

* means zero to infinite

My solution is : S--> aS | bS | ε

Is that right?

Accroding to the comment I modify my solution

S → AbAbA | ε

A → aA | ε

or

S → aS | SbSbS | ε

Do both of them are correct ?

user9976577
  • 3

1 Answers1

0

Your grammar generates every possible string over the alphabet $\{a,b\}$. For instance, it generates $aabaa$ as follows:

$$S\to aS\to aaS\to aabS\to aabaS\to aabaaS\to aabaa$$

The regular expression $a^*(ba^*ba^*)^*$, on the other hand, generates only strings with an even number of $b$s. Specifically, it generates strings of the form $a^k(ba^\ell ba^m)^n$ for non-negative integers $k,\ell,m$, and $n$, and it’s easy to see that there $b$ occurs $2n$ times in such a string. (In fact the regular expression generates all of the words with an even number of $b$s, though it takes a little more work to verify that.)

Brian M. Scott
  • 616,228
  • then , it should be

    S → aS | SbSbS | ε

    right?

     – user9976577 Apr 07 '20 at 20:27
  • 1
    @user9976577: That appears to work, but the most straightforward CFG corresponding to the regular expression has productions $S\to AX$, $A\to aA\mid\varepsilon$, and $X\to bAbAX\mid\varepsilon$. Here $A$ corresponds to the initial $a^$ in the reg. exp., and $X$ corresponds to the $(ba^ba^)^$. – Brian M. Scott Apr 07 '20 at 20:34