Nondeterministic finite automata (NFAs)

To insert a sample NFA into your document, select from the editor

Insert⟶ Structure⟶NFA.

An nondeterministic finite automaton (NFA) is a state machine consisting of 5 components∶

Component

Math notation (example)

Grafstate code

Set of states (Q)

Q={q₁,q₂,q₃}

Q={q1,q2,q3}

Input alphabet (Σ)

Σ={0,1}

S={0,1}

Transition function (δ)

δ(q₁,0)={q₁,q₂}
d(q₁,ε)={q₃}

d(q1,0)={q1,q2}
d(q1,\e)={q3}

Starting state (q₀)

q₀=q₁

q0=q1

Set of final states (F)

F={q₂}

F={q2}

An NFA may have a transition from state q_i to q_j on the empty string ε. Such a transition is called an epsilon transition (or an ε-transition). The Grafstate for ε is \e .

The use of ε-transitions is one of the things that distinguishes NFAs from DFAs .

To begin the creation of an NFA, enter the command :+ nfa name. The syntax for the NFA code is as follows∶

Syntax constraints for an NFA

Each line of an NFA is checked against the following constraints. If a line violates a constraint, then you will receive an error message.

Q and S must be nonempty sets.

q0 must be defined as state in Q .

F must be a subset of Q .

Each transition ( d ) has two input parameters. The first parameter is a state (in Q ) and the second parameter can be either an input symbol (in S ) or \e .

The output of each transition must be a set of states (i.e., a subset of Q ). The empty set can be used as the output of a transition and can be expressed by \0 or {} . A transition whose output is ∅ may be omitted from the Grafstate code altogether. Such a transition is not shown in the state diagram.

Q , S , q0 , and F must be defined exactly once.

You may give an NFA an optional title to be displayed on the state diagram using the title instruction. title place a title here .

Example

Below is the Grafstate code for an NFA that recognizes the language of strings that end with b or consist of zero or more a 's∶

Code
`:+ nfa N` `title example NFA` `Q={q1,q2,q3}` `S={a,b}` `d(q1,\e)={q2}` `d(q1,a)={q1,q2}` `d(q2,b)={q3}` `q0=q1` `F={q3}` `done.`

The preceding Grafstate code produces the following NFA∶

Nondeterministic finite automaton

Simulating an NFA

The Grafstate Simulator will show all steps of the computation performed by an NFA N when reading an input string w that you supply. The steps are visualized as a nondeterminism tree. The NFA computes all branches of the nondeterminism tree independently and at the same time. A string w is accepted by N if at least one of the branches terminates of the nondeterminism tree in a final state q_f (belonging to F), drawn inside a solid diamond (i.e., @{ < q_f > }). A string w is rejected by N if every branch of the nondeterminism tree terminate in a non-final state q (not in F) inside a dotted diamond (i.e., @{. < q > }).

You can simulate an NFA with the command.

Code
`:sim N aaab : >< w=40`

The command above produces the following nondeterminism tree∶

Simulation
Input `aaab`
Result ACCEPTED
Explanation The following nondeterminism tree shows all steps of the computation∶

Nondeterministic finite automaton∶ N

To simulate an NFA from the menus, right-click on the state diagram and select Simulate.