Question

In a deterministic finite automaton, the behaviour of transitions is strictly defined for every input symbol at each state. Identify the statement that correctly describes this property.

• A. DFA can have $\epsilon$ (epsilon) transitions.
• B. DFA can recognize all context-free languages.
• C. DFA has exactly one transition for each symbol from every state.
• D. DFA can have multiple start states.

Hint:

If you are drawing a DFA for an alphabet $\{0, 1\}$, every single state you draw MUST have exactly one arrow leaving it labeled '0' and exactly one arrow labeled '1'.

Answer 1

The Correct Option is C

Concept: The word "Deterministic" in DFA is the key. It means that for any given state and input, the next state is uniquely determined.
• Determinism: No ambiguity and no choices.
• Completeness: Every possible input must have a defined path.

Step 1: Defining the transition function $\delta$.
Mathematically, for a DFA, $\delta: Q \times \Sigma \rightarrow Q$. This means for every state in $Q$ and every alphabet in $\Sigma$, there is exactly one result.

Step 2: Contrast with NFA.
An NFA can have zero, one, or many transitions for a symbol. An NFA can also have $\epsilon$-transitions (moving without input). A DFA strictly forbids both of these.

Step 3: Evaluating the options.
Option (C) is the formal definition of determinism and completeness. Options (A), (B), and (D) describe properties that belong to NFA or more complex machines.