HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Find a regular grammar that generates words with even number of a's

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
generatesnumberwithwordsregulargrammarthatfindeven

Problem

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$

Solution

"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.

Context

StackExchange Computer Science Q#98260, answer score: 5

Revisions (0)

No revisions yet.