Question 46

The DFA has two states $q_0$ (start state) and $q_1$ (accepting state):

• From $q_0$: on 0 remains at $q_0$; on 1 transitions to $q_1$.
• From $q_1$: on 0 transitions to $q_0$; on 1 remains at $q_1$.

Notice that:

• Any transition on 1 leads to or stays in the accepting state $q_1$.
• Any transition on 0 leads to or stays in the non-accepting state $q_0$.
  Therefore, the DFA accepts precisely all strings over $\{0, 1\}$ that end with '1'.

Now test each regular expression:

• (I) $0^* 1(1 + 00^* 1)^*$:
  Begins with $0^* 1$ (first occurrence of 1), followed by any number of blocks that each end with 1 ($1$ or $00^* 1$). Every string generated ends with 1, and any string ending with 1 can be decomposed into such blocks. Thus I represents the DFA.

• (II) $0^* 1^* 1 + 1 1^* 0^* 1$:
  The first term generates strings of the form $0^m 1^n$ ($n \ge 1$).
  The second term generates strings of the form $1^m 0^n 1$ ($m \ge 1$).
  Consider the string $0101$, which ends with 1 and is accepted by the DFA. It cannot be generated by $0^* 1^* 1$ (has an alternating 0 after 1) nor by $11^* 0^* 1$ (starts with 0). Thus II does not represent the DFA.

• (III) $(0 + 1)^* 1$:
  This is the canonical regular expression for all strings ending with 1. Thus III represents the DFA.

Therefore, I and III only represent the DFA (Option B).