1
$\begingroup$

In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon, in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2,
section "Equivalence of NFAs and DFAs"

discusses the upper bound of a NFA's configurations number.

Here

  • NFA stands for Nondeterministic Finite Automata
  • DFA stands for Deterministic Finite Automata

NFA is a is a five-tuple $(S, \Sigma, \delta, s_0 , S_A)$, where

  • $S$ is the finite set of states in the recognizer, along with an error state $s_e$.
  • $\Sigma$ is the finite alphabet used by the FA. Typically, $\Sigma$ is the union of the edge labels in the transition diagram.
  • $\delta(s,c)$ is the FA's transition function. It maps each state $s ∈ S$ and each character $c \in \Sigma$ into some next state. In state $s_i$ with input character $c$, the FA takes the transition $s_i \xrightarrow{\text{c}}\delta(s_i ,c)$.
  • $s_0 \in S$ is the designated start state.
  • $S_A$ is the set of accepting states, $S_A \subseteq S$.

A configuration of a NFA is defined as follows

Each time the NFA must make a nondeterministic choice, the NFA clones itself to pursue each possible transition. Thus, for a given input character, the NFA is in a specific set of states, taken across all of its clones.

In this model, the NFA pursues all paths concurrently. At any point, we call the specific set of states in which the NFA is active its configuration.

When the NFA reaches a configuration in which it has exhausted the input and one or more of the clones has reached an accepting state, the NFA accepts the string.

Given the definitions above, the books states

Consider the state of an NFA when it has reached some point in the input string. [...] the NFA has some finite set of operating clones.

The number of these configurations can be bounded;

for each state, the configuration either includes one or more clones in that state or it does not. Thus, an NFA with $n$ states produces at most $\lvert\Sigma\rvert^n$ configurations.

My question.

Please explain in as much details as possible, how $\lvert\Sigma\rvert^n$ is derived.

I need help, because while trying to follow the book's reasoning, I get lost right after this sentence

for each state, the configuration either includes one or more clones in that state or it does not.

This sounds like the upper bound on the number of configurations should be $2^n$, but instead the book gives $\lvert\Sigma\rvert^n$ bringing in $\Sigma$ seemingly out of the blue.

$\endgroup$
  • 3
    $\begingroup$ You're right; the book's wrong. $\endgroup$ – Rick Decker Aug 24 '17 at 13:25
  • 1
    $\begingroup$ @RickDecker Thanks for the comment. Maybe post it as an answer? So I can accept it. $\endgroup$ – Nik Aug 25 '17 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.