3
$\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
1
$\begingroup$

Remember that:
We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time.

I have a guess that in your eyes:
$2^n$ for both, one directs itself and one directs others and at most every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at most $\mid\Sigma\mid^n$ configurations.

Here are more details: http://www.cse.msu.edu/~torng/360Book/NFA/

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Could you expand a bit your answer? I cannot get how you derive the last step, and that is the crux of the question, to state it simply. $\endgroup$ – Evil Oct 13 '19 at 22:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.