I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$

where $|vu|_a$ is number of $a$ in $vu$.

I came up with these rules:

$\sigma \rightarrow aa\sigma | ab\xi$

$\xi \rightarrow aa\xi | \epsilon$

This generates words in form: $(aa)^iab(aa)^j\epsilon$, but not all words in $L$ look like this.

How do I make sure that $b$s can be put anywhere in between $a$s in $v$ and $u$.

Edit: I think I found a solution.

$\sigma \rightarrow b\sigma$ | $a\alpha$ | $ab\gamma$

$\alpha \rightarrow b\alpha$ | $a\sigma$ | $ab\eta$

$\gamma \rightarrow b\gamma$ | $a\eta$ | $\epsilon$

$\eta \rightarrow b\eta$ | $a\gamma$


"How do I make sure that $b$'s can be put anywhere in between $a$'s in v and u?" Hint, you may need another non-terminal.

Here is a hint about the higher-level approach to the question although you did not ask for it, since it looks like you are not in the reasonably correct way to move forward. I would also encourage you to go forward with your approach as far as possible, if only to experience and see why it does not work (it may work in the end).

Let us define two simpler languages, $$E=\{w | w\in \{a,b\}^*, |w|_a = 0(\text{mod } 2)\}$$ and $$O=\{w | w\in \{a,b\}^*, |w|_a = 1(\text{mod } 2)\}.$$

Can you write regular grammar for $E$ and $O$ ? Can you piece together some E's and O's to form $L$?

Once you have done the problem, you might be able to see a general strategy on how to generate regular grammars for these "simple" languages.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.