Consider the regular grammar below S → bS | aA | ϵ A → aS | bA The…
2006
Consider the regular grammar below
S → bS | aA | ϵ
A → aS | bA
The Myhill-Nerode equivalence classes for the language generated by the grammar are
- 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)*}
Attempted by 19 students.
Show answer & explanation
Correct answer: A
Answer: The Myhill-Nerode equivalence classes are the set of strings with an even number of a's and the set of strings with an odd number of a's.
Key insight: only the parity of the number of a's matters; b's do not affect acceptance.
From the grammar, S is an accepting nonterminal (S → ε), while A is not accepting directly.
A production on symbol a toggles between S and A (S → aA and A → aS), so each a changes parity of the count of a's.
A production on symbol b keeps the current nonterminal (S → bS and A → bA), so b does not change parity.
Therefore, any two strings that have the same parity of a's are indistinguishable by extensions: they lead to the same nonterminal (S for even parity, A for odd parity) and hence behave the same with respect to membership in the language.
To show these two classes are distinct, note that the empty extension distinguishes them: a string with an even number of a's can be extended by the empty string to produce a string in the language, while a string with an odd number of a's cannot be extended by the empty string to produce a string in the language (it would require one more a to become even).
Thus the minimal set of Myhill-Nerode equivalence classes is exactly two: strings with an even number of a's, and strings with an odd number of a's.
