Consider the given regular grammar what are the Myhill-Nerode equivalence classes for the language generated by the grammar?

Question

S → bS | aA | ϵ
A → aS | bA

A) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #a(w) is odd}

B) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #b(w) is odd}

C){w ∊ (a + b)* | #a(w) = #b(w) and {w ∊ (a + b)* | #a(w) ≠ #b(w)}

D) {ϵ}, {wa | w ∊ (a + b)* and {wb | w ∊ (a + b)*}

I am getting strings which are ending with a or ending with b , as well as I am getting strings which have even no of a's so I am getting both A and D option as correct , although I converted the given right linear grammar into DFA and got even no of a's but through derivation tree I am getting even strings which are ending with a or ending with b , so why only option A is correct ?

Answer 1

You have this grammar:

$$\begin{align*} &S\to bS\mid aA\mid\epsilon\\ &A\to aS\mid bA \end{align*}$$

Let’s see what a derivation must look like. You can start by applying the production $S\to bS$ any non-negative number of times, say $k$ times. After that you can end the derivation with $S\to\epsilon$, or you can apply $S\to aA$; let’s look at the latter possibility first. At this point you have the derivation

$$S\Rightarrow^kb^kS\Rightarrow b^kaA\;.$$

Now you can apply the production $A\to bA$ any non-negative number of times, say $\ell$ times, before applying $A\to aS$; at this point you have the derivation

$$S\Rightarrow^kb^kS\Rightarrow b^kaA\Rightarrow^\ell b^kab^\ell A\Rightarrow b^kab^\ell aS\;,$$

and in terms of the available productions you’re back where you started. In terms of regular expressions, we’ve shown that we can derive $b^*ab^*aS$ from $S$. Clearly we can repeat this any number of times, so we can actually derive $(b^*ab^*a)^*S$ from $S$. Any derivation of a terminal string, however, must end with an application of the production $S\to\epsilon$, and it can clearly be preceded by any number of applications of $S\to bS$, so a terminal derivation must look like

$$S\Rightarrow^*(b^*ab^*a)^*S\Rightarrow^*(b^*ab^*a)^*b^*S\Rightarrow(b^*ab^*a)^*b^*\;.$$

In other words, the grammar generates the language corresponding to the regular expression $(b^*ab^*a)^*b^*$.

If you stare at this for a bit, you should see that it describes the set of words over the alphabet $\{a,b\}$ having an even number of $a$s: the language is

$$\left\{w\in(a+b)^*:\#a(w)\text{ is even}\right\}\;.$$

If $u,v\in(a+b)^*$, there are three possibilities.

• If one of $\#a(u)$ and $\#a(v)$ is odd and the other is even, $a$ is a distinguishing extension for $u$ and $v$. (Why?)
• If $\#a(u)$ and $\#a(v)$ are both even, then $u$ and $v$ have no distinguishing extension: for any $w\in(a+b)^*$, $\#a(uw)$ and $\#a(vw)$ are either both even or both odd, depending on whether $\#a(w)$ is even or odd.
• If $\#a(u)$ and $\#a(v)$ are both even, then $u$ and $v$ again have no distinguishing extension; I’ll leave the very similar argument to you.

Thus, the Myhill-Nerode classes are those given in (A).