GNFAs

See the section on simulating a regular expression .

To insert a sample GNFA into your document, select

Insert⟶ Structure⟶GNFA.

from the editor.

A GNFA is a type of finite automaton that is used in the process of converting a DFA into an equivalent regular expression. A GNFA consists of 5 components∶

Description

Math notation

Grafstate code

Set of states Q

Q={s,a,q1,q2}.

Q={s,a,q1,q2}

Input alphabet Σ

Σ={0,1}.

S={0,1}

Starting state )

q₀=q_s.

q0=qs

Set of final states (F)

F={q_f}.

F={q_f}

Transition

q1⟶q2∶0(1⋃ε)*

q1->q2:0(1\u\e)*

The transition function for a GNFA is defined using the Grafstate State-to-State Notation.

State-to-State Notation for GNFAs

The transition function δ∶Q Q⟶RE_Σ maps a pair of states (q_i,q_j) to some regular expression R over Σ. In other words, in the standard function notation, the transition function δ takes 2 input parameters (a current state q_i and a destination state q_j) and produces a regular expression over Σ.

The Grafstate State-to-State Notation separates the part of the transition that defines the current and destination states (the state-to-state part) from the instruction part of the transition that makes a decision based on the input. The state-to-state part of a transition is expressed as qi->qj , where q_i is the source state and q_j is the destination state. For a GNFA, the instruction part is the regular expression. The two parts of the instruction are separated by a colon. Thus, a transition in a GNFA has the following form∶

qi->qj:R ,

where qi is the source state, qj is the destination state and, and R is the resulting regular expression.

The state-to-state part of a loop from state q back to state q can be abbreviated as q: . In other words, a loop from q to q on a regular expression R can be written as∶

q: R

Syntax constraints for a GNFA

Each line of a GNFA 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 the state qs , which must be defined as an element of Q .

F must contain exactly one state that is called qf , and qf must be defined in Q ).

The source state and destination state for each transition must be defined in Q .

Given any two states q_i and q_j, there can be at most one transition from q_i to q_j.

qs cannot have an incoming transition.

qf cannot have an outgoing transition.

The instruction part of each transition must be a valid regular expression over the alphabet S .

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

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

Example

Below is Grafstate code for a GNFA∶

Code
`:+ gnfa G1` `Q={qs,qf,q2}` `S={0,1}` `q0=qs` `F={qf}` `qs->q2:01` `q2:001\u1` `q2->qf:\e` `done.`

The preceding Grafstate code produces the following GNFA∶

GNFA

Grafstate does not simulate GNFAs.