edited by
9,748 views
40 votes
40 votes

Consider the regular grammar below

$S \rightarrow bS \mid aA \mid \epsilon $
$A \rightarrow aS \mid bA$ 

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

  1. $\{w \in (a + b)^* \mid \#a(w) \text{ is even) and} \{w \in (a + b)^* \mid \#a(w) \text{ is odd}\}$
  2. $\{w \in (a + b)^* \mid \#a(w) \text{ is even) and} \{w \in (a + b)^* \mid \#b(w) \text{ is odd}\}$
  3. $\{w \in (a + b)^* \mid \#a(w) = \#b(w) \text{and }\{w \in (a + b)^* \mid \#a(w) \neq \#b(w)\}$
  4. $\{\epsilon\},\{wa \mid w \in (a + b)^* \text{and} \{wb \mid w \in (a + b)^*\}$
edited by

2 Answers

Best answer
142 votes
142 votes

Option A is the correct answer.

Before doing this question we should know the following points.

  1. Number of equivalence classes = Number of states in Minimal FA (MFA)
     
  2. In MFA, we get some language at each and every stage. These languages are mutually exclusive and are called equivalence classes.


So to solve this question, first convert the given Right Linear Regular Grammar into DFA.

There are two states named $S$ and $A$.

The language at state $S$ represents one Equivalence Class. $\Bigl \{ w \in (a + b)^*  \mid \text{ #a(w) is even} \Bigr \}$

The language at State $A$ represents another Equivalence Class.  $\Bigl \{ w \in (a + b)^*  \mid \text{ #a(w) is odd} \Bigr \}$

selected by
29 votes
29 votes

Option A is correct.

The given grammar generates all string over the alphabet $\{a,b\}$ which have an even number of $a$'s.

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

edited by
Answer:

Related questions

45 votes
45 votes
4 answers
3