1 / 9
Finite State Machines & Regular Languages
Learn about deterministic and non-deterministic finite state machines (DFAs/NFAs), regular expressions, and the relationship between FSMs and regular languages.
📚 Learning Steps
💡 Study Tips
- • Read through at your own pace
- • Try the interactive simulators hands-on
- • Study the pseudocode — it appears in exams
- • Quiz yourself before moving on
Step 1: What is a Finite State Machine?
📖 TheoryA finite state machine (FSM) is an abstract model of computation that can be in exactly ONE state at any given time. It reads input symbols one at a time and transitions between states based on rules.
FSMs are everywhere in computing:
•Traffic light controllers — cycle through red, amber, green states
•Vending machines — track how much money has been inserted
•Network protocols — manage connection states (listening, connected, closed)
•Compilers — recognise valid tokens (keywords, numbers, identifiers)
Formally, an FSM is defined by a 5-tuple: (Q, Σ, δ, q₀, F) where:
•Q = finite set of states
•Σ = input alphabet (set of symbols it can read)
•δ = transition function (rules for moving between states)
•q₀ = start state
•F = set of accept states (final/accepting states)
🎯 Key Points
- •An FSM can be in exactly ONE state at any time
- •It reads input symbols one at a time and transitions between states
- •Formal definition: (Q, Σ, δ, q₀, F) — states, alphabet, transitions, start, accept states
- •FSMs are used in compilers, network protocols, hardware design, and many more areas
- •The machine either ACCEPTS or REJECTS an input string
0/9 steps completed