Statement#

Construct a deterministic finite automaton (DFA) that accepts the language: $L = \{w \in \{0,1\}^* : w \text{ contains an even number of 1s}\}$

Required Topics#

• Deterministic finite automata (DFA)
• State machines
• Transition functions
• Regular languages
• Accept/reject states

DFA Definition#

A DFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ where:

• $Q$ = finite set of states
• $\Sigma$ = input alphabet
• $\delta: Q \times \Sigma \to Q$ = transition function
• $q_0 \in Q$ = initial state
• $F \subseteq Q$ = set of accept states

What to Provide#

1. State set $Q$: List all states needed
2. Alphabet $\Sigma$: $\{0, 1\}$
3. Transition function $\delta$: Give complete transition table
4. Initial state $q_0$: Specify which state
5. Accept states $F$: Which states are accepting?

Example Format#

States: $Q = \{q_0, q_1\}$

Transition Table:

| State | Input 0 | Input 1 | |-------|---------|---------| | $q_0$ | ? | ? | | $q_1$ | ? | ? |

Verification#

Test your DFA on:

• $\varepsilon$ (empty string) → accept (0 ones is even)
• $1$ → reject (1 one is odd)
• $11$ → accept (2 ones is even)
• $101$ → reject (2 ones... wait, that's even!)

Solution#

Solution coming soon.