Non-Deterministic Finite Automata (NFA)

Introduction to Non-Deterministic Finite Automata

• Non-Deterministic Finite Automata (NFAs) refer to machines that can exist in multiple states at the same time.
• An NFA is defined as a 5-tuple: $\{Q, \Sigma, q_0, F, f\}$.
  • $Q$: A finite set called the states.
  • $\Sigma$: A finite set called the alphabet (input symbols).
  • $f$: $Q \times \Sigma$: The transition function.
  • $q_0 \in Q$: The initial or start state.
  • $F \subseteq Q$: The set of final or accept state(s).
• A defining characteristic of the NFA is its ability to be in several states at once, as transitions can be non-deterministic.

Characteristics and Differences from DFA

• Initial State: Like a Deterministic Finite Automata (DFA), an NFA starts in exactly one initial state.
• Transition Flexibility: Each state in an NFA can have zero, one, or more outgoing transitions labeled with the same input symbol.
• Next State Choices: A primary difference between an NFA and a DFA is that the transition function in an NFA can lead to several states. This implies that several choices may exist for the next state at any given point during processing.
• Execution and Aborting: If an NFA is in a state where there is no transition defined for a specific input symbol, that branch of the computation aborts.
• Acceptance Criterion: If, at the end of the input sequence, at least one of the active states is a member of the set of final states ($F$), the NFA accepts the input string.

Detailed Example 1: NFA Tracing

• NFA Specification: Construct an NFA over $\Sigma = \{0, 1\}$ that accepts strings ending in "001".
• Trace of Input String "101001":
  1. Initial State: Processing starts with $q_1$ as the initial state. At this point, $q_1$ is the only active state.
  2. First Input Symbol (1): Upon reading '1' while in state $q_1$, the machine remains in $q_1$. The active state is still $q_1$.
  3. Second Input Symbol (0): Upon reading '0' while in state $q_1$, the machine can either remain at $q_1$ or transition to $q_2$. The active states now become the set $\phi = \{q_1, q_2\}$.
  4. Third Input Symbol (1):
     • Upon reading '1' from active state $q_1$, it remains at $q_1$.
     • Upon reading '1' from active state $q_2$, the NFA aborts because there is no defined transition for '1' at $q_2$.
     • The remaining active state is $q_1$.
  5. Fourth Input Symbol (0): Upon reading '0' from active state $q_1$, the machine can either remain at $q_1$ or transition to $q_2$. The active states are now $\phi = \{q_1, q_2\}$.
  6. Fifth Input Symbol (0):
     • Upon reading '0' from active state $q_1$, it either remains at $q_1$ or transitions to $q_2$.
     • Upon reading '0' from active state $q_2$, it transitions to $q_3$.
     • The active states are now $\phi = \{q_1, q_2, q_3\}$.
  7. Sixth Input Symbol (1):
     • Upon reading '1' from active state $q_1$, it remains at $q_1$.
     • Upon reading '1' from active state $q_2$, that branch aborts.
     • Upon reading '1' from active state $q_3$, it transitions to $q_4$.
     • The active states are now $\phi = \{q_1, q_4\}$.
• Conclusion: Since $q_4$ is the final state and is included in the set of active states at the end of the input string, the string "101001" is accepted.

Example 2: NFA Transition Table

• Note: The symbol $\rightarrow$ denotes the initial state.

Example 3: NFA Transition Table

NFAs with $\epsilon$-Transitions

• Definition of $\epsilon$-Transition: This is a transition from one state to another state without consuming any additional input symbols from the string.
• $\epsilon$-NFAs: These are defined as NFAs that contain at least one explicit $\epsilon$-transition.
• Application: In specific configurations, an $\epsilon$-NFA can transition from an initial state to a final state without reading any symbol from the input string at all.

Questions & Discussion

• Prompts for String Generation:
  • Can you give at least five (5) strings for the given NFA in Example 2?
  • Can you give at least five (5) strings for the given NFA in Example 3?