in Theory of Computation retagged by
464 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 ________
in Theory of Computation retagged by
464 views

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

4 Comments

@GO Classes / @Lakshman Patel RJIT

I feel following is the minimal DFA and hence shouldn't the answer be 3 ? Please correct me if I am wrong

0
0

@sk91

What you have created it NOT DFA.

0
0

@Deepak Poonia

Thanks for the clarification. Can you tell why this is not a DFA ? What is wrong here ? It will help me. I am not able to understand. 

0
0
In a DFA, Every state on Every alphabet symbol must have transition to exactly one state.

In your FA, the last state doesn’t have transition on input symbols.
4
4
Answer:

Related questions