Finite Automata

Finite Automata

1. What It Is

A finite automaton (FA) is an abstract machine with finite states and transitions on input symbols that decides if a string belongs to a regular language. The scanner is built as an FA.

5-tuple: states Q, alphabet $Σ$, transition function $δ$, start state $q₀$, final states F.

2. DFA vs NFA

	DFA	NFA
Moves per symbol	exactly 1	0, 1 or many (may have ε-moves)
Implementation	direct code/table	simulate via subset
Use	actual scanner	easy to build from regex

Both accept exactly the regular languages.

3. Example — identifiers

states: q0 start, q1 final (identifier)
q0 --letter--> q1
q1 --letter丨digit--> q1 (loop)
q0, q1 --other--> dead

Transition table:

      letter  digit  other
q0     q1     dead   dead
q1*    q1     q1     dead(return token)
* = accepting

Trace a1: q0 →a→ q1 →1→ q1 (accept). Trace 9a: q0 →9→ dead (reject → not identifier).

4. Acceptance

String accepted iff starting at $q₀$ and following $δ$ ends in a final state after consuming all input. Longest match rule: keep going while transitions exist.

5. Exam Points

• Define FA 5-tuple, DFA vs NFA — 5 marks, very frequent.
• Draw transition diagram + table for identifier / number / keyword — 5-7 marks, very frequent.
• Trace accept/reject of given strings — 3 marks, frequent.