retagged by
480 views
3 votes
3 votes
Let $L$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{L}$ on the set $\Sigma^{\ast }$ of finite strings over $\Sigma$ is defined by $u \sim_{L} v$ if and only if for all $w \in \Sigma^{\ast }$ it is the case that $u w \in L$ if and only if $v w \in L$.
Suppose that $\Sigma=\{a, b\}$ and $L$ is the language determined by the regular expression $a ^\ast b(a \mid b)$. Number of $\sim_{L}$-equivalence classes for this $L$ is ________
retagged by

1 Answer

4 votes
4 votes
The given equivalence relation is actually the Myhill-Neord relation. And we know that a language is regular if and only if the number of equivalence classes in the myhill nerode relation are finite. So, both statements are true.

Also, the number of equivalence classes in myhil neord relation are equal to the number of states in the minimal DFA.

The minimal DFA accepting the language $a ^\ast b(a+b)$ has 4 states. So, answer $4 .$

Reference: https://www.youtube.com/channel/UCyvbBJhLJ-5YqwPA884vj0Q
edited by
Answer:

Related questions

341
views
2 answers
2 votes
GO Classes asked Jun 9, 2022
341 views
For the deterministic finite automaton $M$ with state set $\{0,1,2\}$, alphabet of input symbols $\{a, b\}$, initial state $0 ,$ accepting states 1 and 2 , and next-state ... None of the above
581
views
2 answers
4 votes
GO Classes asked Jun 9, 2022
581 views
Let $L$ be the language accepted by the following non-deterministic finite automaton with $\epsilon$-transitions:The number of states in the minimal DFA that accepts the ... is recognized by the above NFA over alphabet $\{a\},$ is ________
290
views
1 answers
3 votes
GO Classes asked Jun 9, 2022
290 views
Consider the following languages:The language of regular expression $(0+1)^{\ast } 11(0+1)^{\ast }$ ... $1=2$Neither $1$ is subset of $2$, nor $2$ is subset of $1$.
765
views
1 answers
3 votes
GO Classes asked Jun 9, 2022
765 views
Let $L$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{\mathrm{L}}$ on the set $\Sigma^{\ast }$ of finite strings over $\Sigma$ ... $1$Only $2$BothNone