Question

The diagram given below refers to a non-deterministic finite state automaton that accepts the language having

• A. All words that contain the repetition of \(ab\) and end with \(a\)
• B. All words that contain the substring \(ba\) and end with \(a\)
• C. All words that end with \(a\)
• D. All words that end with \(b\)

Hint:

If an NFA/DFA reaches a final state only through a transition labeled \(a\), and that final state has no outgoing transitions, then accepted strings typically end with \(a\). Always inspect the final transition leading to the accepting state.

Answer 1

The Correct Option is C

Concept: A Finite Automaton accepts a string if, after reading the complete input string, it reaches a final (accepting) state. In the given NFA:
• \(q_0\) is the start state.
• \(q_1\) is the accepting state.
• There is a self-loop on \(q_0\) labeled \(a,b\).
• There is a transition from \(q_0\) to \(q_1\) labeled \(a\). The automaton can stay in \(q_0\) while reading any sequence of \(a\)'s and \(b\)'s and move to \(q_1\) only when it reads the final \(a\).

Step 1: Analyze the loop at \(q_0\).
The self-loop is labeled \[ a,b \] which means the automaton may remain in \(q_0\) after reading either symbol. Therefore, any prefix consisting of \(a\)'s and \(b\)'s can be processed while staying at \(q_0\).

Step 2: Analyze the transition to the final state.
There is a transition \[ q_0 \xrightarrow{a} q_1. \] This means that the automaton can enter the accepting state only when an \(a\) is read.

Step 3: Determine which strings are accepted.
For a string to be accepted, the automaton must finish in the final state \(q_1\). Since the transition into \(q_1\) is labeled \(a\), the last symbol of the accepted string must be \[ a. \] Examples of accepted strings: \[ a,\quad ba,\quad aba,\quad bbba,\quad aabaa. \]

Step 4: Check the options.
The automaton does not require the substring \(ba\). It does not require repeated \(ab\). It simply requires that the last symbol be \(a\). Hence the language is \[ \boxed{\text{All strings ending with } a} \]

Step 5: Write the final answer.
Therefore, the correct option is \[ \boxed{\text{(C) All words that end with } a} \]