academic project
Automata and Their Applications
A report introducing automata theory and showing how finite-state models support technologies such as spell checking and secure bank transfers.
Basic explanation
An automaton is a mathematical machine with a finite set of states and a transition rule that, given the current state and an input symbol, determines the next state. The state is a compressed memory: it stores only what the machine still needs in order to behave correctly on future input.
A classic teaching example is a turnstile with states Locked and Unlocked. A coin transitions Locked → Unlocked; a push in Unlocked admits one person and returns to Locked. The same pattern - finite memory plus local rules - scales to recognising patterns in text, validating protocols, and rejecting illegal sequences of actions.
Formal view
Deterministic finite automata (DFAs) accept a string if reading it ends in an accepting state. Nondeterministic variants allow several possible next states; they recognise the same class of regular languages but often give more compact descriptions. Closure properties (union, concatenation, star) and the Myhill-Nerode characterisation explain why some languages need infinitely many distinguishable prefixes and therefore cannot be regular.
Applications in the report
The report connects those abstractions to concrete systems:
- Spell checking / lexical analysis - token patterns and dictionary lookup framed as recognition problems on strings;
- Protocol and transaction validation - sequences of operations that must stay inside a safe state graph (for example, steps of a transfer that may not be reordered arbitrarily);
- UI and device control - interfaces whose legal actions depend on mode, analogous to the turnstile’s locked/unlocked discipline.
Aim
The goal was clarity with formal backbone: introduce the definitions carefully enough that applications read as instances of the same model, not as unrelated engineering anecdotes. That habit of naming states, alphabets, and transitions explicitly is the same discipline used later in verified or safety-critical software design.