Question

Consider the regular grammer below:

$S\to bS\mid aA\mid ϵ$

$A\to aS\mid bA$

The Myhill- Nerode equivalence classes for the language generated by the grammer are

Answer 1

The given right- linear grammer can be converted to the following DFA.







The machine accepts all strings over the alphabet {a, b} which have an even number of a's. It is a minimal DFA.

So Myhill-Nerode equivalnce classes for the languages is nothing but the set of strings reaching S and A respectively.

S = $\left(w\in {(a+b)}^{\ast }\#\right\}$_a(w) is even

A = $\left(w\in {(a+b)}^{\ast }\#\right\}$_a(w) is odd