1
$\begingroup$

A singly capacitated regular language is such that exists a deterministic finite automaton (DFA) which has a single accepting state. For example an empty language (whose alphabet is an empty set) is singly capacitated regular language and here's a DFA demonstrating this: enter image description here

I don't understand why this is a legal DFA. It is not connected and the same input $\big(\sum\big)$ causes a dead-end (the part on the left) while the same input can also result in accepting state (the part on the right).

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You seem to confuse several things

(1) The empty language can be defined on any alphabet, empty or not.

(2) A DFA is not necessarily minimal and not necessarily connected.

(3) A word is accepted if it is the label of a successful path, that is, a path starting in the initial state and ending in some final state.

If you read carefully this definition, you will conclude that the DFA represented in your picture accepts the empty language.

$\endgroup$
4
  • $\begingroup$ But how can this be that the same input can result in accepting state and non-accepting state at the same time? $\endgroup$
    – user123429842
    Nov 2, 2018 at 17:54
  • 1
    $\begingroup$ The input has to start from the initial state. $\endgroup$
    – J.-E. Pin
    Nov 2, 2018 at 22:04
  • $\begingroup$ But what does it mean that you start somewhere and then there's no connection to the next state? $\endgroup$
    – user123429842
    Nov 3, 2018 at 8:09
  • 1
    $\begingroup$ In your case, there is a connection to the next state for every word. The point is that you stay in the initial state and never reach the final state. Thus there is no successful path and the language recognized by the DFA is empty. $\endgroup$
    – J.-E. Pin
    Nov 3, 2018 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.