Finite Automata

Finite Automata (FA): A finite automaton is a mathematical model of computation consisting of:

• A finite set of states
• An input alphabet
• A transition function
• A start state
• A set of accepting states

FA reads input symbol by symbol and changes state according to transition function. If it ends in an accepting state, the string is accepted.

Limitations:

1. Finite Memory: Can only remember current state, not history
2. Cannot Count: Cannot count unbounded occurrences (e.g., aⁿbⁿ)
3. No Stack: Cannot handle nested structures
4. Limited Language Class: Can only recognize regular languages
5. Cannot Compare: Cannot compare arbitrary substrings

Aspect	DFA	NFA
Definition	δ: Q × Σ → Q	δ: Q × Σ → P(Q)
Transitions	Exactly one per symbol	Zero, one, or many
ε-transitions	Not allowed	Allowed
Acceptance	Single path to final state	Any path to final state
Implementation	Easier (direct simulation)	Harder (backtracking/subset)
Design	More complex	Often simpler
Power	Equivalent (recognize same languages)

Aspect	Moore Machine	Mealy Machine
Output function	λ: Q → Δ	λ: Q × Σ → Δ
Output depends on	Current state only	Current state AND input
Output associated with	States	Transitions
Output length	n + 1 for input length n	n for input length n
States required	Generally more	Generally fewer
Output timing	Synchronous (after state change)	Asynchronous (during transition)

Diagram representation:

• Moore: Output written inside state circle (e.g., q₀/0)
• Mealy: Output written on transition (e.g., a/0)

Logic:

• Use 5 states for remainders 0, 1, 2, 3, 4
• Transition rule: new_remainder = (2 × current + input) mod 5
• Handle leading zeros specially

States:

• q₀: Start state (remainder 0, also handles "0" case)
• q₁: Remainder 1
• q₂: Remainder 2
• q₃: Remainder 3
• q₄: Remainder 4
• qₑ: Dead state for invalid leading zeros

Transitions (for valid numbers):

State	0	1
q₀	q₀	q₁
q₁	q₂	q₃
q₂	q₄	q₀
q₃	q₁	q₂
q₄	q₃	q₄

Final State: q₀ (remainder 0 = divisible by 5)

For excluding leading zeros:

Add dead state qₑ where "0" at start goes to qₑ, and qₑ is a trap.

The string "0" can be accepted as special case (0 is divisible by 5).

Verification:

• 101 (5): q₀ →¹ q₁ →⁰ q₂ →¹ q₀ ✓
• 1010 (10): q₀ →¹ q₁ →⁰ q₂ →¹ q₀ →⁰ q₀ ✓
• 1111 (15): q₀ →¹ q₁ →¹ q₃ →¹ q₂ →¹ q₀ ✓

NFA Design:

States: q₀ (start), q₁, q₂, q₃, q₄, q₅, q₆ (final)

Transitions:

• q₀: Self-loop on 0,1 (waiting)
• Path for "000": q₀ →⁰ q₁ →⁰ q₂ →⁰ q₆
• Path for "010": q₀ →⁰ q₃ →¹ q₄ →⁰ q₆
• q₆: Self-loop on 0,1 (stay in final)

Subset Construction:

DFA State	NFA States	0	1
→A	{q₀}	B	A
B	{q₀,q₁,q₃}	C	D
C	{q₀,q₁,q₂,q₃}	E	D
D	{q₀,q₄}	F	A
*E	{q₀,q₁,q₂,q₃,q₆}	E	G
*F	{q₀,q₁,q₃,q₆}	E	G
*G	{q₀,q₄,q₆}	F	H
*H	{q₀,q₆}	F	H

Final states: E, F, G, H (all contain q₆)

Strategy:

1. Track consecutive 'a's seen
2. Output 'a' or 'b' normally until "aaa" pattern
3. When third 'a' seen, output 'b' and reset

States:

• q₀: No consecutive a's
• q₁: One 'a' seen
• q₂: Two 'a's seen

Mealy Machine:

State	a (next/out)	b (next/out)
q₀	q₁/a	q₀/b
q₁	q₂/a	q₀/b
q₂	q₀/b (replacement!)	q₀/b

Trace for "aaaab":

a: q₀→q₁, out=a

a: q₁→q₂, out=a

a: q₂→q₀, out=b

a: q₀→q₁, out=a

b: q₁→q₀, out=b

Output: "aabab"

Moore Machine:

Need to split states based on output. States become: q₀(a), q₀(b), q₁(a), q₁(b), q₂(a), q₂(b)

Or simpler: use states to encode both position AND pending output.

This is from May 2025 paper - complex vowel problem!

Alphabet: Σ = {a, e, i, o, u}

Rule: Output each vowel as-is, except when 'i' follows 'e', output 'u' instead

States:

• q₀: Start/normal state, output nothing initially
• qₐ: Just saw 'a', output 'a'
• qₑ: Just saw 'e', output 'e' (CRITICAL - watch for 'i')
• qᵢ: Just saw 'i' (not after 'e'), output 'i'
• qₒ: Just saw 'o', output 'o'
• qᵤ: Just saw 'u', output 'u'
• qₑᵢ: Just saw 'i' after 'e', output 'u' (REPLACEMENT)

Key Transitions:

• From qₑ on input 'i' → go to qₑᵢ (output 'u')
• From qₑ on any other vowel → go to appropriate state
• From all other states on 'i' → go to qᵢ (output 'i')

Trace for "aeiou":

• a: q₀→qₐ, Moore outputs: a
• e: qₐ→qₑ, Moore outputs: e
• i: qₑ→qₑᵢ, Moore outputs: u
• o: qₑᵢ→qₒ, Moore outputs: o
• u: qₒ→qᵤ, Moore outputs: u

Final output: "aeuou"