Finite Automata

Deterministic Finite Automaton (DFA)

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

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

Computation

1. Start in state $q_0$
2. Read input symbol by symbol
3. Transition according to $\delta$
4. Accept if end in a state in $F$; otherwise reject

State Diagrams

Visual representation:

• Circles = states
• Double circles = accept states
• Arrow into state = start state
• Labeled arrows = transitions

Example: Strings ending in "1"

     0          1          0
→(q0)──→(q0)  (q0)──→((q1))  ((q1))──→(q0)
                              1
                        ((q1))──→((q1))

$Q = \{q_0, q_1\}$, $\Sigma = \{0, 1\}$, $q_0$ = start, $F = \{q_1\}$

$\delta$	0	1
$q_0$	$q_0$	$q_1$
$q_1$	$q_0$	$q_1$

Language of a DFA

The language $L(M)$ of DFA $M$ is the set of all strings $M$ accepts: $L(M) = \{w \in \Sigma^* \mid M \text{ accepts } w\}$

A language is regular if some DFA recognizes it.

Extended Transition Function

$\hat{\delta}: Q \times \Sigma^* \to Q$ processes entire strings:

$\hat{\delta}(q, \epsilon) = q$ $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$

Then: $L(M) = \{w \mid \hat{\delta}(q_0, w) \in F\}$

Nondeterministic Finite Automaton (NFA)

An NFA allows:

• Multiple transitions for same symbol
• Epsilon ($\epsilon$) transitions (no input consumed)
• Missing transitions (implicit rejection)

$N = (Q, \Sigma, \delta, q_0, F)$ where:

• $\delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q)$

Acceptance

NFA accepts if any computation path leads to accept state.

Example: Strings containing "01"

     0,1        0          1
→(q0)──→(q0)──→(q1)──→((q2))
                        0,1
                   ((q2))──→((q2))

NFA vs DFA

Power

NFAs and DFAs recognize exactly the same languages (regular languages).

Conversion: NFA to DFA (Subset Construction)

DFA states = subsets of NFA states

For NFA with $n$ states, equivalent DFA may have up to $2^n$ states.

Why Use NFAs?

• Often smaller/simpler to design
• Easier to compose (union, concatenation)
• Can convert to DFA when needed

Epsilon Closure

For state $q$, the epsilon closure $E(q)$ is the set of states reachable from $q$ using only $\epsilon$-transitions.

For set $S$: $E(S) = \bigcup_{q \in S} E(q)$

Regular Languages

Closure Properties

Regular languages are closed under:

• Union: $L_1 \cup L_2$
• Intersection: $L_1 \cap L_2$
• Concatenation: $L_1 L_2$
• Kleene star: $L^*$
• Complement: $\overline{L}$
• Difference: $L_1 - L_2$

Constructing DFAs

Union: Product construction, accept if either accepts. Intersection: Product construction, accept if both accept. Complement: Swap accept and non-accept states.

DFA Minimization

Goal

Find equivalent DFA with minimum number of states.

Algorithm (Table-Filling)

1. Mark pairs $(p, q)$ where one is accept, other is not
2. Mark $(p, q)$ if for some $a$, $(\delta(p,a), \delta(q,a))$ is marked
3. Repeat until no new marks
4. Unmarked pairs are equivalent; merge them

Theorem

The minimal DFA for a regular language is unique (up to isomorphism).

Examples of Regular Languages

Language	Description
Binary strings divisible by 3	DFA with 3 states
Strings with even 0s	2 states
Strings with "11" substring	3 states
Strings not containing "101"	4 states

Limitations

DFAs cannot recognize:

• $\{a^n b^n \mid n \geq 0\}$ (equal a's and b's)
• $\{ww \mid w \in \{a,b\}^*\}$ (repeated strings)
• $\{a^{n^2} \mid n \geq 0\}$ (perfect square lengths)

These require more powerful models (pushdown automata, Turing machines).