Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA…

Correct regular expression: 1(0 + 11)*

Reasoning:

• The first symbol must be 1: from the start state, reading 0 goes to a non-accepting sink state, so any string beginning with 0 is rejected.

• From the accepting state, reading 0 loops back to the accepting state, so each 0 after the initial 1 can appear anywhere and keep the string accepted.

• From the accepting state, reading a single 1 moves you to a non-accepting state; a second 1 is required to return to the accepting state. Thus 11 acts as an indivisible block that returns to acceptance.

• Combining these facts gives: the string must start with 1, and the rest is any number (possibly zero) of either a 0 or the pair 11. That is exactly 1(0+11)*.

Examples accepted:

• "1" (initial 1, no further symbols)

• "10" (1 then a 0 loop in accepting state)

• "111" (1 then the pair 11)

• "10011" (1, zeros, then the pair 11)

Examples rejected:

• "" (the empty string is rejected because the DFA requires a leading 1)

• "0" (starts with 0 and goes to the non-accepting sink)

• "11" (after the initial 1 a single 1 moves to a non-accepting state and the string ends there)