DFA starts or ends with 01

Significance of finite automata

• They are the simplest model of computation (a machine with finite memory) and define the regular languages.
• They are used in lexical analysers (tokenisers), text search and pattern matching, network protocols, hardware controllers and vending/traffic controllers.
• They are the base for studying more powerful machines (pushdown automata, Turing machines) and show what can be done with a fixed amount of memory.

DFA: strings that start with 01 or end with 01

Idea. After reading a prefix 01, accept everything (a final trap state F). Otherwise keep track of the "ends with 01" condition using three states:

• N: the last symbol is 1 (or nothing relevant yet),
• Z: the last symbol is 0,
• E: the last two symbols are 01 (final).

States: q0 (start), a (read "0" first), F (prefix 01 seen), N, Z, E.

M = ({q0, a, F, N, Z, E}, {0,1}, δ, q0, {F, E})

 q0 ─0─► a ─1─► ((F)) ↻0,1
 │       └0─► Z
 └1─► N ─0─► Z ─1─► ((E))
      ↻1      ↻0        │0 -> Z
                        │1 -> N
 (N -1-> N, N -0-> Z, Z -0-> Z, Z -1-> E)

Edges: q0 –0→ a, q0 –1→ N, a –0→ Z, a –1→ F, N –0→ Z, N –1→ N, Z –0→ Z, Z –1→ E, E –0→ Z, E –1→ N, F loops.

Testing

• "01110" (starts with 01): q0 →0 a →1 F →1 F →1 F →0 F. Accepted.
• "1101" (ends with 01): q0 →1 N →1 N →0 Z →1 E. Accepted.
• "1100" (neither): q0 → N → N → Z → Z. Z is not final. Rejected.