Non-deterministic Finite State Automata (NFA)

Introduction to Non-determinism

• Non-determinism: In the context of computation theory, non-determinism refers to the ability of an automaton to have multiple possible next states from a given state and input symbol.
• Determinism: In contrast, determinism in automata implies a single possible state transition for each state and input combination.

Non-deterministic Finite Automaton (NFA)

• Definition: An NFA is defined as a 5-tuple:
  1. Q: A finite set of states
  2. Σ: A finite set of input symbols (alphabet)
  3. δ: Transition function (may lead to multiple states)
  4. q₀: Start state
  5. F: Set of accepting states
• Transition Function: Unlike deterministic finite automata (DFA), NFAs can have zero, one, or multiple transitions for each symbol.
• Empty Transitions: NFAs can include transitions that do not consume an input symbol, denoted by ε.

Computation Process

• Parallel Paths: An NFA can simultaneously explore multiple computation paths for the same input.
• Acceptance: An input is accepted if at least one computation path ends in an accepting state.

Formal Description of Computation

• Given an NFA, M, and a string, w, acceptance follows:
  1. w can be split as w₁w₂...wₙ where each wᵢ is a symbol in the alphabet.
  2. There exists a sequence of states q₀, q₁, ..., qₙ satisfying:
     • q₀ is the start state
     • δ(qᵢ, wᵢ) includes qᵢ₊₁ for each i
     • qₙ is an accepting state

NFA vs DFA

• DFA: Each state has exactly one outgoing transition per symbol.
• NFA: States may have multiple transitions, including ε-transitions.
• Design Complexity: NFAs can be more complex to design but offer flexibility in recognizing patterns.

Pictorial Representation

• NFAs can be represented using state diagrams, similar to DFAs.
• Example: A simple NFA might accept strings containing only 'b' ending in 'a', or those with an odd number of 'b's ending in 'a'.

Example and Exercise

• A provided NFA accepts specific patterns based on its transition rules.
• Exercise: Determine which strings are accepted by the NFA.
  • E.g., the string "ba" is rejected due to no accepting computation ending in the accepting state.

This summary captures the core concepts and operational principles of non-deterministic finite automata as discussed in the lecture.