1. **Problem statement:** Construct DFAs recognizing languages over alphabet $\{0,1\}$: (a) Strings that begin with $1$ and end with $0$. (b) Strings that contain at least three $1$s. (c) Strings containing substring $0101$. (d) Strings with length at least 3 and third symbol $0$. 2. **Part (a)**: DFA for $\{w \mid w \text{ begins with } 1 \text{ and ends with } 0\}$. - States: - $q_0$: start; no input yet. - $q_1$: saw first symbol = 1. - $q_2$: strings beginning 1, last symbol read is 0 (accept). - $q_3$: strings beginning 1, last symbol read is 1. - $q_{dead}$: dead state if first symbol not 1. - Transitions: - From $q_0$: - on $1 \to q_1$ - on $0 \to q_{dead}$ - From $q_1$: - on $0 \to q_2$ - on $1 \to q_3$ - From $q_2$: - on $0 \to q_2$ - on $1 \to q_3$ - From $q_3$: - on $0 \to q_2$ - on $1 \to q_3$ - From $q_{dead}$: - stays in $q_{dead}$ on all inputs. - Accept states: $q_2$ (string begins with 1 and ends with 0). 3. **Part (b)**: DFA for $\{w \mid w \text{ contains at least three } 1\}$. Count 1s up to 3. - States: $q_0$ (0 ones), $q_1$ (1 one), $q_2$ (2 ones), $q_3$ (3 or more ones, accept). - Transitions: - On input $1$, move to next count state. - On input $0$, stay in same state. - Accept state: $q_3$. 4. **Part (c)**: DFA for $\{w \mid w \text{ contains substring } 0101\}$. - States represent how much of $0101$ matched: - $q_0$: no match. - $q_1$: matched $0$. - $q_2$: matched $01$. - $q_3$: matched $010$. - $q_4$: matched $0101$ (accept). - Transitions: - From $q_0$: - on $0 \to q_1$ - on $1 \to q_0$ - From $q_1$: - on $0 \to q_1$ - on $1 \to q_2$ - From $q_2$: - on $0 \to q_3$ - on $1 \to q_0$ - From $q_3$: - on $0 \to q_1$ - on $1 \to q_4$ - From $q_4$: - loops on all inputs. - Accept state: $q_4$. 5. **Part (d)**: DFA for $\{w \mid |w| \ge 3 \text{ and third symbol } = 0\}$. - States track position and third symbol: - $q_0$: start, no input. - $q_1$: read 1 symbol. - $q_2$: read 2 symbols. - $q_3$: read 3 symbols, third symbol was $0$ (accept) - $q_4$: read 3 symbols, third symbol was not $0$. - $q_5$: read more than 3 symbols after accepting. - $q_6$: read more than 3 symbols after rejecting. - Transitions: - $q_0 \xrightarrow{0,1} q_1$ - $q_1 \xrightarrow{0,1} q_2$ - $q_2 \xrightarrow{0} q_3$ (accept), $q_2 \xrightarrow{1} q_4$ - $q_3 \xrightarrow{0,1} q_5$ - $q_4 \xrightarrow{0,1} q_6$ - $q_5 \xrightarrow{0,1} q_5$ - $q_6 \xrightarrow{0,1} q_6$ - Accept states: $q_3, q_5$. 6. The above descriptions clarify the state names, transitions, and accept states.