What:

A model used to represent and control the execution flow in a system with a finite number of states.

Components:

  1. States (): The finite set of states the automaton (system) can even be in
  2. Alphabet (): The finite set of input symbols
  3. Transition Function (): A function that defines how the state changes based on inputs it’s gotten.
  4. Start State (): The initial state the automaton begins.
  5. Accept States (): A set of states that determine when an input is accepted.

Example:

Let’s say we want an automaton that accepts the string "ab".

  • States: {q₀, q₁, q₂}
  • Alphabet: {a, b}
  • Transitions:
    • q₀ → a → q₁
    • q₁ → b → q₂
    • q₂ is the accepting state.

If we input "ab", we reach q₂, so it’s accepted. If we input "aa", it gets stuck and is rejected.

It Gets Harder:

  1. Deterministic Finite Automaton (DFA):
    • For each state and input symbol, there’s exactly one possible transition.
    • There are no -transitions.
  2. Non-Deterministic Finite Automaton (NFA):
    • A state may have multiple transitions for the same input.
    • Some transitions may occur without input (-transitions)
  3. Probabilistic Finite Automaton (PFA):
    • Each transition has a probability rather than being deterministic.
  4. Pushdown Automaton (PDA):

Converting from Regular Expressions to DFA:

Overview:

  1. Convert from RE to NFA: We do this because RE has implicit non-determinism (-transition).
  2. Convert the NFA to DFA: We’ll be left with some left-over states after this.
  3. Simplify the DFA: Remove the unnecessary left-over states.

1. Convert RE to NFA

RECorresponding NFA
aSingle-state transition: q0 → a → q1
AB (Concatenation)Connect final state of A to start state of B using an ε-transition.
A|B (Union)Use ε-transitions to branch into A or B.
A* (Kleene Star)Create a loop using ε-transitions to allow repetition or skipping A.
A+ (Kleene Plus)Similar to A*, but requires at least one occurrence of A.
A? (Optional)Use an ε-transition to optionally skip A.
Example: Convert a* to NFA

For a* (zero or more occurrences of a):

  1. Create a new start and accepting state.
  2. Add ε-transitions to allow:
    • Skipping "a" (direct ε-transition from start to accept).
    • Repeating "a" by looping back to itself.

NFA Diagram for a*:

(q0) --ε--> (q1) --a--> (q2) --ε--> (q1)
(q1) --ε--> (q3)   (q3 is the final state)

2: Convert NFA → DFA (Subset Construction)

Subset Construction Algorithm

  1. Compute ε-closures:
    • The ε-closure of a state is the set of all states reachable via ε-transitions.
  2. Define the initial DFA state as the ε-closure of the NFA’s start state.
  3. Process each DFA state:
    • Compute transitions for each input symbol.
    • The new state is the ε-closure of the set of NFA states reached.
  4. Mark final states:
    • If any state in the DFA contains an accepting NFA state, it becomes an accepting DFA state.
  5. Repeat until no new states are generated.

Example: Convert NFA (for a*) to DFA

NFA for a* (from Step 1):

(q0) --ε--> (q1) --a--> (q2) --ε--> (q1)
(q1) --ε--> (q3)  (q3 is accepting)

Subset Construction

NFA State SetInput aResulting DFA State
{q0, q1, q3}a{q2, q1, q3}
{q2, q1, q3}a{q2, q1, q3}

Since {q1, q3} contains the accepting state (q3), the corresponding DFA state is also accepting.

Thus, the DFA for a* is:

(q0) --a--> (q1)
(q1) --a--> (q1) (loops)
(q1 is accepting)

Step 3: Minimise the DFA

Once we have the DFA, we can minimise it by:

  1. Removing unreachable states.
  2. Merging equivalent states (states that behave identically).

Minimisation Algorithm

  1. Partition states into two groups:
    • Accepting states.
    • Non-accepting states.
  2. Refine partitions:
    • Two states are equivalent if they transition to the same group for all inputs.
    • Merge equivalent states.
  3. Construct the minimised DFA.

Example: Minimising a DFA

Consider this DFA:

(q0) --a--> (q1) --a--> (q1)
(q1) --a--> (q1)
(q1 is accepting)

Since q1 is the only useful state, the minimized DFA is simply:

(q0) --a--> (q1)
(q1) --a--> (q1) (loops)

NFA for a(b|c)*:

is the set of all w possible states reachable from , given an input .