in Theory of Computation
239 views
0 votes
0 votes

There is one and only one finite language that can be accepted by a 1-state DFA. True or False? Explain.

in Theory of Computation
239 views

1 Answer

3 votes
3 votes

Single State DFA can recognize either $\phi$  OR  $\Sigma^*$. 
Since the question is asking for "finite language" accepted by 1-state DFA, So, answer will be $L = \phi$. That's why the given statement is True.
NOTE that, 1-state DFA can recognize either $\phi$ OR $\Sigma^*$.


$L = \{ \epsilon \} $ is NOT the empty language. 
$L = \{ \} $ is the empty language. 
For $L = \{  \} $, the minimal DFA has 1 state. 
For $L = \{ \epsilon \} $, the minimal DFA has 2 states.  

Related questions