JFLAP Manual PDF

JFLAP lu:lDj
Running JFLAP
Download JFLAP and the fles referenced in this book from www . j flap. org to get started.
JFLAP is written in Java to allow it to run on a range of platforms. JFLAP requires that
your computer have Java SE 1. 4 or later installed. JFLAP works with Java 1.5. For the latest
version, visit http://java.sun.com/ . Mac OS X's latest Java release, if not already preinstalled,
is available from http://www.apple. com/j ava/, or from Software Update.
With Java SE 1. 4 or later installed on your computer, you may attempt to run JFLAP. JFLAP
is distributed as an executable .jar (Java ARchive) fle. JFLAP may be run as either an application
or applet. The following table lists how to run the JV. jar executable .jar as an application on
your platform of choice.
Windows Double click on Ji. jar; the fle will appear as Ji if sufx hiding is
on.
Unix & Linux From a shell with the JV. jar fle H the current directory, enter the
command java -jar JV.jar.
Mac OS X The Windows and Unix directions will work on a Mac.
JFLAP Interface Primer
We cover universal elements of the JFLAP interface here. To begin, start JFLAP. When JFLAP
has fnished loading, a window will appear similar to that shown in Figure 1. This window ofers a
choice of major structures if you wish to create a new structure; alternatively, the File menu allows
you to open an existing saved structure or quit JFLAP.
Throughout this book we shall review the creation of these structures. However, right now we
are going to open a JFLAP saved fle of an existing fnite automaton (FA) . From the File menu,
choose Open. JFLAP allows users to save and open fles that contain a single structure. Select
and open the fle exO. 1 a. A new window will appear with an FA.
We refer to all the things you can do to a structure as operators. (It is not necessary to under
stand what the operators are doing at this point; our purpose is to describe JFLAP's interface. )
xvi
xvii
Figure 1: The window that appears when you start JFLAP.
Operators are typically activated through the menu items. Choose th ' t
.
r ht N d
e menu 1 em Test : HIgh-
Ig on
.
eter
.
minism. (This activates an operator that shades nondeterministic states in an
automaton, H thIS case Q and ) N t h
g ql

ex , c oose the menu item Test ' Highlight A T 't
'
(Th' t' t
' - anSI IOns
IS ac Iva es an operator that highlights A-tr ' t '
.
.
.
1 b 1 d
anSI IOns H an automaton, H this case the arc
a e e A. ) We chose these two operators because they require no intervention from the user.
Nondetrmhdsti 5E5 E highlghted.
Figure 2: An illustration of the window for a structure, with three tabs active.
The window for a structure consists of a menu bar that contains operators you may apply t th
structure and a tabb d . t f b
O e
, e zn erJace elow the menu bar. Note that JFLAP k
.
eeps everythzng related
JFLAP STARTUP
XVlll
to a structure in a single window, and uses tabs to manage multiple operators active at the same
time. The results of the two operators we invoked are displayed in tabs, so there are currently three
tabs: Editor, Nondeterminism, and A-Tansitions. In Figure 2, the Nondeterminism tab
is selected, indicating that the interface for the "highlight nondeterminism" operator is currently
active and displayed. To switch to another operator, click on its tab. (Note that you cannot switch
to the Editor tab at this time. This is because the other two currently active operators depend
on the automaton not changing. )
We will now remove the Nondeterminism and A-Tansitions tabs. To get rid of a tab, select
the menu item File : Dismiss Tab. This will remove the currently active tab. When it is gone,
remove the other tab as well. (JFLAP prevents removal of the Editor tab. )
As a last step, peruse the contents of the File menu. Use New when you want to create a new
h N
.
I cted JFLAP will display
.
the window shown in Figure 1 that allows
structure; w en ew is se e ,
you to choose a type of structure to create. The Open, Save, and Save As menu items allow
you to read and write structures to fles like any other application that deals with documents. he
Close item will close the window of the structure. The Print item will print the currently active
tab. Quit will stop JFLAP entirely.
Chapter 1
1Hle ^DlOHulu
A fnite automaton is the frst type of representation for a regular language that we will examine.
In this chapter we will construct a deterministic fnite automaton (DFA) in JFLAP, illustrate
several methods of simulating input on that automaton, discuss nondeterministic fnite automata
(NFAs) in JFLAP, and present simple analyses that JFLAP may apply to automata. We present a
standard defnition of a DFA in Sections 1. 1-1. 4, and show in the optional Section 1. 5 how JFLAP
handles a more general defnition of a DFA with multiple character transitions.
J.J A Simple Finite Automaton
d
Figure 1. 1: A fnite automaton (FA), which recognizes the language of any number of a's followed
by any odd number of b's.
In this section you will learn how to build automata in JFLAP by way of constructing, with
help, the DFA that recognizes the language of strings of any number of a's followed by any odd
number of b's (e. g. , ab, bbb, aabbbbb) . This section will teach the essentials of automaton editing
in JFLAP: creating and deleting states and transitions, moving existing states, editing existing
transitions, and setting states to be initial and fnal. When you are done, you will have a machine
like that pictured in Figure 1. 1!
The frst step is, of course, to start JFLAP. Once JFLAP is running, you begin building an FA
by clicking on the button labeled Finite Automaton. A window will appear with (from top to
bottom) a menu, a tab that says Editor, a tool bar, and a large blank area at the bottom.
1
CHAPTER 1. FINITE AUTOMATA
2
1.1.1 Create States
All automata require a set of states. Before you can create states you must frst activate the State
Creator tool: click on the button below the window's menu bar. This button will now appear
shaded to indicate that tool is active.
The large blank area below the tools, called the canvas, is where the automaton is created and
edited. Now that the State Creator tool is active, click on the canvas to create a state. A state will
appear under the location where you clicked. As you will see, states in JFLAP are yellow circles
with some identifying text inside. Click three more times in three other locations to create three
more states. There will now be four states on the canvas, with the text qo, ql, q2, and q3 to identify
,each of them.
1.1.2 Defne the Initial State and the Final State
All automata require an initial state and a set of fnal states. In this automaton we will make qo
the initial state, and ql the single fnal state. Select the Attribute Editor tool, by clicking the
button. Two of this tool's many functions are to defne an initial state and to defne the set of fnal
states. (This tool's other functions are described in Section 1. 1. 5. )
Now that the Attribute Editor tool is selected, right-click on qo (or, control-click if you are a
Macintosh user with a single mouse button) . A pop-up menu above the state will appear with
several items, including two items Final and Initial. Select the item Initial. The state qo will
now have a white arrowhead appear to its left to indicate it is the initial state. Similarly, right-click
on the state ql, and select the item Final. The state ql will now have a double outline instead of
a single outline, indicating that this state is a member of the set of fnal states.
You may fnd it necessary to set a fnal state as nonfnal. To illustrate how, right-click on ql
once you have marked it as fnal. Notice that the item Final now has a check mark next to it .
Select the item Final again. This will toggle ql out of the set of fnal states. Before you proceed,
you must of course put ql in the set of fnal states again!
1.1.3 Creating Transitions
We will now create transitions. In this machine, three transitions are necessary: three on b from qo
to ql, ql to q2, and back again from q2 to ql, and a loop transition on 0 for state qo

We will create
others for illustrating some special features, and for later illustration of the Deleter tool.
To create these transitions, select the Transition Creator tool, denoted by the . icon. The
frst transition we are going to create is the b transition from qo to ql

Once the Transition Creator
tool is selected, press the mouse cursor down on the qo state, drag the mouse cursor to the ql state,
and release the mouse button. A text feld will appear between the two states. Type "b" and
1.1. A SIMPLE FINITE AUTOMATON 3
press return. A new b transition from qo to ql will appear. By the same method, create the two b
transitions from ql and q2 and from q2 and ql

Tip As an alternative to pressing return, you can stop editing a transition merely by doing
something else like clicking in empty space but not on a state! ) , or creating another
transition by dragging between two other states. If you wish to cancel an edit of a
transition, press Escape.
The next transition is qo's loop transition on 0. Creating loop transitions on a state is just like
other transitions: you press the mouse on the start state and release the mouse on the end state.
However, because the start and end states are the same for a loop transition, this is the same as
clicking on the state. So, click on state qo, and enter "a" and press return, just as you did for the
b transitions.
Lastly, create three transitions from qo to q3, the frst on the terminal 0 another on b, and a
third on C. Notice that JFLAP stacks the transition labels atop each other.
Tip If you are in the process of editing a transition from a state g to a state g and you
wish to create another transition from state g to state g_ without having to use the
mouse, press Shift-Return. This creates a new transition from g to g in addition to
ending your editing of the current transition.
1.1.4 Deleting States and Tansitions
.
You probably noticed that the automaton built requires three states, not four. This fourth state q3
and the transitions going to it are unneccessary and can be removed. Deleting objects has a tool
all its own: click the: button to activate the Deleter tool.
First, we want to remove the transition on b from qo to q3. To delete this transition, click on
the b. The b transition will be gone, leaving the 0 and C transitions. You can also click on the
transition arrow itself to delete a transition: click on the arrow from qo to q3, and notice that the 0
transition disappears. The C transition remains. When you click on the arrow, the transition with
the label closest to the arrow is deleted.
Deleting states is similar. Click on the state q3. The state q3 will disappear, and notice that the
C transition is gone as well. Deleting a state will also delete all transitions coming from or going
to that state. You should now be left only with the other three states and the transitions between
them.
1.1.5 Attribute Editor Tool
ec ion . . , ut it as many other functions We already used the Attribute Editor tool l'n S t' 1 1 2 b
.
h
related to modifcation of attributes of existing states and transitions. Select the Attribute Editor
tool once again as we walk through examples of its use.
4 CHAPTER 1. FINITE AUTOMATA
Setting states as initial or fnal
This tool may set states as initial or fnal states as described in Section 1. 1. 2.
Moving states and transitions
When you initially placed the states for the FA built earlier you may not have arranged them in
a logical order. To move a state, press on the state and drag it to a new location. Dragging a
transition will likewise move its two associated states. Attempt this now by dragging states and
transitions.
Editing existing transitions
To edit an existing transition, simply click on it! Try clicking the transition from qo to ql The
same interface in which you initially defned this transition will appear on the transition and allow
you to edit the input characters read by that transition.
Labels
When you set the state qo as the initial state and the state ql as a fnal state, perhaps you noticed
the menu item Change Label. Right-click on q2 and select Change Label. A dialog box will
appear, asking for a label. When processing input, while the machine is in state q2 , we shall have
processed an even number of b's, so enter "even # of b' s". A box will appear under the state with
this label. By a similar token, label ql "odd # of b' s". To delete an existing label from a state
choose the menu item Clear Label from the same menu. Alternatively, the menu item Clear All
Labels will delete all labels from all states.
If you right-click in empty space, a diferent menu will appear, with the item Display State
Labels. This will initially have a check mark next to it to indicate that it is active. Select it.
The labels will become invisible. Hover the mouse cursor over q2; after a short time, a tool-tip will
appear to display the label even # of b's. Right-click in empty space once more, and reactivate
Display State Labels; the labels will appear again.
Automatic layout
Right-click in empty space again. Notice the menu item Layout Graph. When selected, JFLAP
will apply a graph layout algorithm to the automaton. While usually not useful for automata you
produce yourself, many of JFLAP' s algorithms automatically produce automata, often with large
numbers of states. If you fnd JFLAP' s frst attempt at automatic layout inappropriate, this may
alleviate the tedium of moving those states yourself.
1.2. SIMULATION OF INPUT
J.2
Tip
Figure 1. 2: In the midst of the simulation of aabbb on our FA.

In addition to activating a tool by clicking on its button in the tool bar, there are also
shortcut keys available for quickly switching tools. For example, hover the mouse over
the State Creator tool after a little while a tool-tip will appear with the text (5)tatc
Ctcatot. The parentheses enclosing the 5 indicate that this is the shortcut key for the
State Creator tool. Note that in spite of appearances, shortcut keys are really lower
case, so do not press Shift when typing the shortcut key for a tool!
Simulation of Input
5
I this section we cover three of JFLAP' s methods to simulate input on an automaton: stepping
WIth closure, fast simulation, and multiple simulation. The fourth, stepping by state, is discussed
briefy in Section 1.3.
1.2.1 Stepping Simulation
The stepping simulation option allows you to view every confguration generated by an automaton
in its attempt to process an input string. Figure 1. 2 shows a snapshot of a stepping simulation of
the iput string aabbb on the automaton you built in Section 1. 1, also stored in fle exl. la. The top
portIOn of the window displays the automaton, with the state in the active confguration shaded
darker. The portion below the automaton displays the current confguration. In Figure 1. 2, notice
the confguration is in state qo, and that the frst two characters aa are grayed-out, indicating that
they have been read, while the three characters bbb are not grayed-out, indicating that they remain
to be read.
Try stepping
We shall walk through the process of stepping through input in an automaton. First, select the
menu item Input : Step with Closure. A dialog box will ask for input for the machine: enter
"aabbb" and press Return or click OK.
Your window will now appear similar to Figure 1. 2. The single confguration displayed will be
on the initial state Qg, and have the unprocessed input aabbb.
The tool bar at the bottom is your interface to the simulator. Click Step. The old confguration
on Qg has been replaced with a new confguration, again on the state Qg but with the character
a read. Notice that the frst character a in the input has been lightened a bit to indicate that it
.has been read. Click Step twice more, and it will go from Qg to qg again, and then to Q_ with the
input bb remaining.
Some of the operations in the tool bar below the confguration display act only on selected
confgurations. Click on the confguration; this will select it (or deselect it if it is already selected) .
A selected confguration is drawn shaded. Click Remove. Unfortunately, this deletes the only
confguration! The simulator is useless. Oops! Click the Reset button; this will restart the
simulation, so you can try again.
With the simulation back to its original state, click Step repeatedly (fve times) until all the
input is read. The confguration at this point should be drawn with green background, indicating
that it is an accepting confguration, and that the machine accepts the input. FA confgurations
are accepting confgurations if all the input is read and it is in a fnal state. The confguration's
input is entirely gray, indicating that all the input has been read.
One can Trace a confguration to see its ancestry from the initial confguration. (Do not select
a confguration; press Trace instead. An error message indicates that Trace requires a selected
confguration! ) Now select the single confguration, and click the Trace button. A window will
show the ancestry of this confguration, starting with the initial confguration on top and the
selected confguration on the bottom. When you've had a chance to look over the trace of the
confguration, close this window.
To return to the editor, choose File : Dismiss Tab to dismiss the simulator.
Failure
On the fip side of an accepting confguration is a rejected confguration. A rejected confguration
is one which (1) does not lead to any more confgurations and (2) is not accepting. Run a stepping
simulation again, except this time with the input aabb. Since this has an even number of b's the
machine will not accept it. Click Step repeatedly, and note that eventually the confguration will
turn red. This indicates that it is a rejected confguration.
1.2. SIMULATION OF INPUT
7
Figure 1.3: The result of performing a fast simulation of aabbb on the automaton.
1.2.2 Fast Simulation
Steping thro
.
uh simulation of input is fne, but Fast Run will reveal if the automaton accepts
a strmg and, If It does, the series of confgurations leading to that string's acceptance without the
bother of having to repeatedly step through the machine watching for accepting confgurations.
Choose Input : Fast Run. When prompted for input, enter the same "aabbb" string. The
result after JFLAP determines that the machine accepts this input is shown in Figure 1. 3. The trace
of confgurations from top to b tt (
.
f
. . . 1 .
. .
'
O om 1.e. , rom Imtla to acceptmg confguration) , is displayed.
AlternatlVely, If the machine did not accept this input, JFLAP would report that the string was
not accepted.
Notice te to buttons near the bottom of the dialog box. I'm Done will close the display.
Keep Lookmg IS useful for nondeterministic machines and is covered later in Section 1. 3. 2.
1.2.3 Multiple Simulation
The third method for simulating input on an automaton is Multiple Run. This method allows
oe to peform multiple runs on a machine quickly. Select Input : Multiple Run now. (Your
dIsplay WIll not resemble Figure 1. 4 exactly, but do not worry! ) The automaton is displayed to the
left, and on the right is an empty table where you may enter inputs for multiple runs. One enters
inputs in the Input column. Select the upper-left cell of this table, enter the input "aabbb", then
2
8
Figure 1.4: An example of simulating multiple entries. The second-to-last
input is the empty string, entered with Enter Lambda.
press return. Notice that instead of one row there are now two: the table will grow to accommodate
more entries as you enter them.
Continue entering various inputs you wish to test on the machine; whichever you choose is up
to you. If you wish to make a lambda entry-that is, test to see if the automaton accepts the
empty string-then while entering an input, click the Enter Lambda button near the bottom of
the window, and that input feld will hold the empty string. When you have entered all inputs and
wish JFLAP to simulate all these strings, click Run Inputs. Notice that the Result column is
now full of Accept and Reject entries, indicating whether an input was accepted or not. View
Tace will show the trace of the last confguration generated for each selected run in the table.
Clear will clear the table of all inputs.
Tip For convenience, the multiple run simulator will remember all inputs entered by the
user between machines. For example, suppose you have one automaton, and perform
multiple runs on that machine. If you later perform multiple run simulation on a different
automaton those same inputs will appear.
J. Nondeterminism
In this section we will talk about NFAs in JFLAP, using the automaton pictured in Figure 1. 5 as
our example.
Either of two conditions imply that an FA is nondeterminstic. The frst condition is, if the FA
has two transitions from the same state that read the same symbol, the FA is considered an NFA.
1.3. NONDETERMINISM
Figure 1.5: An NFA that accepts the language of a series of a's followed by a
series of b's, where the number of a's is nonzero and divisible by 2 or 3, and
the number of b's is divisible by 2 or 3.
9
For example, ql of the FA in Figure 1. 5 has two outgoing transitions on a. The second condition
is: if the FA has any transitions that read the empty string for input , the FA is nondeterministic.
1.3.1 Creating Nondeterministic Finite Automata
Creating an NFA is much the same as creating a DFA. Select File : New, and then select Finite
Automaton to get a new window. In this window we will create the automaton shown in Figure 1.5,
that accepts the language anbm, where U ` 0 and is divisible by 2 or 3 and H 2 0 and is divisible
by 2 or 3. The frst step is to create the thirteen states of the automaton, and to make qo the initial
state and make Q and ql1 the fnal states.
Note that JFLAP numbers states in the order that you create them: the frst state is qo , the
second ql , and so on. It is important to respect this order: the following discussion assumes that
you create the states in such an order that they are numbered as they are in Figure 1. 5.
Notice the four transitions in Figure 1. 5 with a A ,the Greek letter lambda, . These A-transitions
are transitions on the empty string. To enter a A-transition, create a transition, but leave the
feld empty. When you fnish editing, a transition with the label A will appear. Create the four
A-transitions from q3 and qg to Q and qn.
Once you have created the A-transitions, create the other transitions on the symbols a or b.
Figure 1.6: Step with closure simulation of aaaabb on our NFA after two steps.
1.3.2 Simulation
D

.
I t
.
ut on a deterministic machine will produce a single path of confgurations, unng Slmu a lOn, lnp
. ,
while input on a nondeterministic machine may produce multiple paths of confguratlOns. JFLAP s
simulators have features to deal with this possibility.
Stepping simulation: Step with Closure
.
I t Step with Closure and input the string "aaaabb", that is, four Select the menu ltem npu .
,
a's followed by two b's. This is a string that will eventually be accepted since the numbr
.
of a s
.
d d

.
bl b 2 and the number of b' s is divisible by 2. After you enter thlS mput, lS nonzero an lV1Sl e y
.
h ld see the familiar step simulator, with a starting confguration on qg with all the mput you s ou
. .
r k
. .
b d cr ck Step once to move this confguratlOn to ql. However, lf you c lC remammg to e processe . 1
Step a second time you will see a rather unfamiliar sight, as shown in Figure 1. 6.
. .
Notice that there are four confgurations in your simulator. This is because your machme lS
d
. .
t
.
Th last confguration was on ql with the unread input aaabb, and ql has a non etermmlS lC. e
.
However, what two confgurations on q6 and qn? These confguratlOns transitions to q2 and qg.
are ue to e A ransl ! . d th \ t
ons When a confguration proceeds to a state qi, Step with Closure

.
t l . but for all states reachable on A-transitions from qi. The set creates confguratlOns no on y lor qz,
1. 3. NONDETERMINISM
11
of states reachable from qi on A-transitions is called the closure of qi. So, when the confguration
in qg with the remaining input aabb was created, confgurations for q6 and qn were created as well
because the closure of qg includes q6 and ql1.
As you may hav

fgured out, of these two paths of confgurations, the only one that will
eventually lead to an accepting confguration is the confguration on qg. Click on this confguration
to select it. With the confguration selected, click Feeze. The confguration will appear tinted light
ice blue! Now try stepping again: While the other confgurations move on and are rejected), that
confguration will not progress! Frozen confgurations do not progress when the simulator steps.
With that confguration still selected, click Thaw. Thaw "unfreezes" selected confgurations.
Click the Step button once more, and the now unfrozen confguration will continue, and one of its
nondeterministic paths will be accepted.
Select the accepting confguration and click Tace to view the series of confgurations that led
to the accepting confguration. Notice that there is a confguration from qlQ directly to ql1, even
though there is no transition from qlQ to ql1. In stepping by closure one does not explicitly traverse
A-transitions in the same sense that one traverses regular transitions: Instead, no confguration was
ever generated for qg, and the simulator implicitly traversed the A-transition.
When you have fnished, dismiss the simulator tab.
Stepping simulation: Step by State
Select the menu item Input : Step by State, and input the string "aaaabb". In stepping by
state, the closure is not taken, so the simulator explicitly traverses A-transitions. If you step twice,
you will have confgurations in q2 and qg, but not the confgurations in q6 and qn that we saw when
stepping by closure.
Notice that the unread input on the qg confguration is aabb. If you step again, the confguration
on qg will split into three confgurations, two of which are on q6 and qn. The A-transition was taken
explicitly over a step action. If you continue stepping until an accepting confguration is encountered
and run a trace, the confguration after qlQ is on qg, which then proceeds to ql1 after explicitly
taking the A-transition.
Though stepping by state is in some ways less confusing, stepping with closure is often preferred
because it guarantees that each step will read an input symbol.
Fast simulation
The fast simulator has some additional features specifcally for nondeterminism. Select Input :
Fast Run, and enter the string "aaaaaabb". Once you enter this, JFLAP will display one trace of
accepting confgurations.
c
12
Figure l. 7: Another FA, which also recognizes the language of the automaton in Figure 1. l.
The button Keep Looking i s useful for nondeterministic machines, where multiple branches
of confgurations may accept the same input. Note that there are six a's. Since six is divisible by
both two and three, there will be two paths of confgurations that accept this input: one path leads
through state q3 (which verifes that the number of a's is divisible by three) , and another path
leads through state qg (which verifes that the number of a's is divisible by two) . The trace through
either q3 or qg should be visible now. Click Keep Looking, and it will search for and display
the trace through the other state. Click Keep Looking again. JFLAP will display a message, 2
confgurations accepted, and all other possibilities are exhausted, which indicates that no
other accepting confgurations are possible.
Multiple .simulation
Nondeterministic machines may produce multiple confguration paths per run. However, the mul
tiple run simulator's ability to view traces of selected runs will present only a single trace for each
run. Specifcally, this feature displays only the trace of the last confguration generated for a run.
This means that for an accepting run JFLAP displays the trace of the frst accepting confguration
encountered, and further for a rejecting run displays the trace of the last confguration rejected,
which may not provide enough information. Viewing a run in the stepwise simulator can give a
more complete picture if you want to debug a nondeterministic machine.
J. Simple Analysis Operators
In addition to the simulation of input , JFLAP ofers a few simple operators from the Test menu
to determine various properties of the automaton.
1.4.1 Compare Equivalence
This operator compares two fnite automata to see if they accept the same language. To illustrate
how this works, we shall load an automaton that recognizes the same language as the automaton
we have abused throughout much of this chapter: the automaton shown in Figure l. 7, stored in
fle ex1.4a. Open this fle. Also, open the fle ex1.1a; this contains the automaton of Figure l. l.
1. 5. ALTERNATIVE MULTIPLE CHARACTER TRANSITIONS* 13
You will now hav_two windows, one with the original automaton of Figure l. 1 (presumably
titled ex1.1a), the other with the automaton of Figure l. 7 (presumably titled ex1. 4a). Choose the
menu item Test : Compare Equivalence from the ex1.4a window. A prompt will appear where
you may choose from the names of one other automaton (i. e. , the title of another automaton's
window) from a list. After you select the original automaton's window' s name (again, presumably
ex1. 1a), click OK. You will then receive a dialog box telling you that they are equivalent! Dismiss
this dialog. Edit the Figure l. 7 automaton so that the b transition from qo to q1 is instead an a
transition (so that the automaton now recognizes strings with any nonzero number of a's and an
even number of b's) , or make whatever other change is to your liking so that the automaton no
longer recognizes the same language as the original. Repeat the test for equivalence, and this time
you will receive a notice that it does not accept the same language.
Close the two fles, but do not save the changes from the modifed ex1.4a.
1.4.2 Highlight N ondeterminism
This operator will show the user which states in an automaton are nondeterministic states. Consider
again the automaton in Figure l. 5, stored in the fle ex1. 3a. Load this fle. The state q1 is obviously
nondeterministic, and JFLAP considers all states with outgoing A-transitions to be nondeterministic
states, so q3 and qg are nondeterministic. Select Test : Highlight N ondeterminism: a new view
will display the automaton with these states highlighted.
1.4.3 Highlight.-Tansitions
This operator will highlight all A-transitions. Here we use the same automaton we built in Sec
tion l. 3. 1, the automaton shown in Figure l. 5 and stored in the fle ex1. 3a. Load this fle if it is
not already present. When you select Test : Highlight A-Tansitions, a new view will display
the automaton with the four A-transitions highlighted.
J. Alternative Multiple Character Tansitions*
JFLAP provides a more general defnition of an FA, allowing multiple characters on a transition.
This can result in simpler FAs. Pictured in Figure l. 8 is a fve-state NFA that accepts the same
language as the thirteen-state NFA in Figure l. 5. Notice that the six transitions that are not
A-transitions are on multiple symbols, for example, aaa from qo to q1 . A confguration may proceed
on an U character transition of 8182 . . . 8n if the next unread input symbols are 5 1 , 82, and so on
through 8n .
We will now run a simulation on this NFA. Load the fle ex1. 5a, select Step With Closure,
and enter the same aaaabb string we used in Section l. 3. 2. After you enter the input, you will see
(
14
bbb
Figure 1.8: An NFA equivalent to that of Figure 1.5.

the familiar step simulator, with a starting confguration on ,_with all the input remaining to be
processed. Click Step once and you will see six confgurations! There are two confgurations for
,,, one closure from ,, and one closure from ,,. Note that these two confgurations have diferent
amounts of remaining input since the transitions to ,, and ,,process a diferent amount of input.
Similarly, there are two confgurations for ,,. Stepping twice more results in acceptance in ,,.
By allowing multiple character transitions, the frst condition for FA nondeterminism in Sec
tion 1. 3 changes. The frst condition is now the following: if the FA has two transitions from the
same state that read strings A and B, where A is a prefx of B, the FA is considered an NFA. For
example, note that ,_ is a nondeterministic state: it has two transitions, one from aaa and the
other from aa; aa is a prefx of aaa, so the FA is nondeterministic. The NFA would use both of
these transitions while simulating the string aaaabb.
J.U Defnition of FA in JFLAP
JFLAP defnes a fnite automaton NI as the quintuple NI = (Q,, 6, ,,,F ) where
Q is a fnite set of states ],,,.is a nonnegative integer}
is the fnite input alphabet
6 is the transition function, 6 : D - 2
Q
where D is a fnite subset of Q X *
,,E Q is the initial state
F <; Q is the set of fnal states
Users reading only Sections 1. 1-1. 4 will want to use a simpler defnition of 6. In that case, for
a DFA 6 is the transition function 6 : Q X - Q, and for an NFA 6 is the transition function
6 : Q X U {A} - 2
Q
.
For those users reading Section 1.5, note that JFLAP allows for multiple characters on a tran-
sition. These multiple character transitions complicate the defnition of the transition function's
domain: the set Q X * is of infnite cardinality, though the transition function requires a fnite
domain. * means a string of 0 or more symbols from the input alphabet.
1. 7. SUMMARY 15
J. Summary
In Section 1. 1 you learned how to create a deterministic fnite automaton (DFA) in JFLAP. The
editor for an automaton has a tool bar along the top portion of the window, and the automaton
display on the bottom portion of the window. You create states with the tool, create transitions
with the>" tool, delete states and transitions with the: tool, and edit attributes (position, labels,
setting fnal and initial) of existing states and transitions with the tool.
In Section 1.2 you learned how to simulate input on automata. Each simulator accepts an input
string and determines if the automaton accepts that input. The step simulator is useful if you
are interested in seeing every confguration generated by a machine as it attempts to read your
input. The fast simulator is useful if you are interested only in those confgurations that led to
an accepting confguration. The multiple input simulator is useful if you are interested in running
many inputs on an automaton quickly.
In Section 1. 3 you learned about creating and simulating input on a nondeterministic fnite
automaton (NFA) . Leaving the feld blank when creating a transition will produce a A-transition.
While simulating input, the step simulator may display multiple confgurations at once as the
machine follows diferent paths attempting to read the input. The fast simulator can search for
multiple branches of nondeterminism accepting the same input.
In Section 1. 4 we presented three analysis operators available from the Test menu. Compare
Equivalence checks if two fnite automata accept the same language. Highlight Nondetermin
ism highlights nondeterministic states, and Highlight A-Tansitions highlights A-transitions.
In Section 1.5 we presented an alternative defnition of an FA that allows for multiple characters
on a transition. This can lead to an FA with a smaller number of states.
In Section 1.6 we presented JFLAP's formal defnition of a fnite automaton, which corresponds
to Section 1. 5. We also presented a simpler defnition corresponding to Sections 1. 1-1. 4.
J.h Exercises
1. Build FAs with JFLAP that accept the following languages:
(a) The language over = {a} of any odd number of a's.
(b) The language over = {a} of any even number of a's.
(c) The language over = {a, b} of any even number of a's and any odd number of b' s.
(d) The language over = {a, b} of any even number of a's and at least three b' s.
(
18
b, Repeat part a, , but with the language of strings a
n
bnc
n
alblClaoboco
c, Repeat part a, , but with the language of strings a
O
anbo bnco Cn
8. Given two FAs A with language LA and B with language LB, you can use JFLAP's Compare
Equivalence operator to determine whether or not LA = LB Can you deise a general
method using JFLAP to determine whether LA C; LB i .e., B accepts every stnng A acePts,
.
C E I valence? Yes part of your instructions may, indeed must, mvolve
usmg ompare qu . ,
editing A or B. Your method must produce the right answer for any two FAs! ,
Chapter Z
D1^ lO 11^ lO PHHa 11^
This chapter shows how each NFA can be converted into an equivalent DFA, and how each DFA
can be reduced to a DFA with a minimum number of states. Although an NFA might be easier to
construct than a DFA, the NFA is usually not efcient to run, as an input string may follow several
paths. Converting an NFA into an equivalent DFA ensures that each input string follows only one
path. The NFA to DFA algorithm in JFLAP combines similar states reached in the NFA into one
state in the DFA. The DFA to minimum state DFA algorithm in JFLAP determines which states
in the DFA have similar behavior with respect to incoming and outgoing transitions and combines
these states, resulting in a minimal state DFA.
2.J NFA to DFA
In this section we use JFLAP to show how to convert an NFA into an equivalent DFA. The idea
in the conversion is to create states in the DFA that represent multiple states in the NFA. The
start state in the DFA represents the start state in the NFA and any states reachable from it on
A. For each new state in the DFA and each letter of the alphabet, one determines all the reachable
states from the corresponding NFA states and combines them into a new state for the DFA. This
state in the DFA will have a label that will contain the state numbers from the NFA that would
be reachable in taking the same path.
2.1.1 Idea for the Conversion
Load the NFA in fle ex2.la as shown in Figure 2. 1. We will refer to this example in explaining
the steps in converting this NFA to a DFA.
First examine the choices that occur when the NFA processes input . Select Input : Step with
Closure and enter the input string "aabbbaa" and press return. Clicking Step once shows that
processing a can result in arriving in both states qo and ql. Clicking Step six more times shows
19
c
20
CHAPTER 2. NFA TO DFA TO MINIMAL DFA
a 0
a
Figure 2. 1: Example from fle ex2.1a.
that there are always three confgurations (one of which is rejected) , and results in two paths of
acceptance in states q2 and q3
The states in the constructed DFA will represent combined states from the NFA. For example,
processing an a resulted in either state qo or ql . The DFA would have a state that represents both
of these NFA states. Processing aabbbaa resulted in reaching fnal states q2 and q3 The DFA would
have a state that represented both of these NFA states. Dismiss the tab for the step run (select
File : Dismiss Tab) to go back to the NFA editor.
2.1.2 Conversion Example
Now we will convert the NFA to a DFA (select Convert: Convert to DFA) , showing the NFA
on the left and the frst state of the DFA on the right. The initial state in the DFA is named qo
and has the label 0, meaning it represents the qo state from the NFA.
Tip
The NFA may be tiny. Adjust the size in one of two ways: either resize the window,
or drag the vertical bar between the NFA and the DFA to the right. In addition, the
states in the DFA can be dragged closer to each other, resulting in larger states.
We will now add the state that is reachable from qo on the substring a. Select the Expand
Group on Terminal tool n,? Click and hold the mouse on state qo , drag the cursor to where you
want the next state, and release it. When prompted by Expand on what terminal?, enter "a"
and press return. When prompted by Which group of NF A states will that go to on a?, enter
the numbers of the states that are reachable from qo on an a. In this case enter "0,1". (These NFA
states could also be entered with a blank separator and with or without the q, such as "qO,q1". )
The new state ql appears i n Figure 2. 2.
Use the Attribute Editor tool you learned about in Chapter 1 to move states around if you
don't like their placement.
2.1. NFA TO DFA 21
Figure 2. 2: Expansion of state Q on a.
8
b
Figure 2. 3: Expansion of a and b from state ql .
Ty expanding DFA state Q on the terminal b. Since there are no paths from NFA state Q on
a b, a warning message is displayed.
Next expand the DFA state ql on the terminal a. Note that DFA state ql represents both states
qo and ql from the NFA. In the NFA, state qo on an a reaches states qo and ql , and state ql on an a
reaches no state. The union of these results (0, 1) are the states reachable by DFA state ql , which
happens to be the DFA state ql . Upon the completion of the expansion a transition loop labeled
a is added to DFA state ql . Now expand DFA state ql on b. The result of these two expansions is
shown in Figure 2. 3. Why is DFA state q2 a fnal state? If a DFA state represents any NFA state
that is a fnal state, then the substring processed is accepted on some path, and thus the DFA state
also must be a fnal state. NFA state q2 is a fnal state, so DFA state q2 (representing NFA states
ql and q2) is a fnal state.
Expand DFA state q2 on a. This state is represented by NFA states ql and q2 . NFA state ql
does not have an a transition. NFA state q2 on an a reaches state q3 and due to the A-transition
also reaches state q2 .
Note In using the Expand Group Terminal tool, if the destination state already exists, then
drag to the existing state and you will be prompted only for the terminal to expand.
Thus, to add a loop transition, just click on the state.
Expand DFA state q2 on b by clicking on state q2 . You are prompted for the b, but not the
states reachable, as that is interpreted as your selected state (itself in this case) . The resulting
DFA is shown in Figure 2. 4.
There is another way to expand a state-the State Expander tool . When one selects this
tool and clicks on a state, all arcs out of the state are automatically expanded. In Figure 2.5 state
q3 was selected and expanded on both a and b, resulting in a new state q4 .
22
a
Figure 2. 4: Expansion of 0 and b from state q2 .
Figure 2. 5: State Expander tool applied to state q3
|
Figure 2. 6: The completed DFA.
Is the DFA complete? Select the Done? button. If the DFA is not complete, a message
indicating items missing is displayed. At this time, one transition is missing.
Expand DFA state q4 on b by going back to the Expand Group on Terminal tool. Note that q4
on b goes to the existing DFA state q2 . Click on state q4 , drag to state q2 , and release. You will be
prompted for the terminal only.
Is the DFA complete? Select the Done? button. The DFA is complete and is exported to a
new window. The complete DFA is shown in Figure 2. 6. Alternatively, the Complete button can
be selected at any time during the construction process and the complete DFA will be shown.
The constructed DFA should be equivalent to the NFA. To test this, in the DFA window select
Test : Compare Equivalence. Select fle ex2 . la, the name of the NFA, and then press return.
The two machines are equivalent.
2.2. DFA TO MINIMAL DFA
2.1.3 Algorithm to Convert NFA M to DFA M'
23
We describe the algorithm to convert an NFA M to a DFA M
'
. We frst defne the closure of a set
of states to be those states unioned with all states reachable from these states on a A-transition.
1. The initial state in M
'
is the closure of the initial state from M.
2. For each state q
'
in M
'
and each terminal J do the following:
(a) States q and r are states in M. For each state q that is in state q
'
, if q on an J reaches
state r on an J, then place state r in new state p'.
(b) p' = closure(p')
( c) If another state is equivalent to state p' (represents the same states from M) , then set
p' to the state already existing.
(d) Add the transition to M
'
: q
'
to p' on an J.
3. Each state q
'
in M' is a fnal state if it contains a fnal state from M.
2.2 DFA to Minimal DFA
In this section we show how to convert a DFA to a minimal state DFA. Consider two states p and q
from a DFA, each processing a string starting from their state. If there is at least one string w such
that states p and q process this string and one accepts w and one rejects w, then these states are
distinguishable and cannot be combined. Otherwise, states p and q "act the same way," meaning
that they are indistinguishable and can be combined.
2.2.1 Idea for the Conversion
Load the DFA in Figure 2. 7 (fle eX2. 2a, . We will refer to this example to explain the steps to
convert this DFA to a minimal state DFA.
We would like to examine pairs of states to see if they are distinguishable or not. To do this we
will need two separate windows for this DFA. JFLAP lets you open only one copy of each fle, so if
you try to open the same fle again, JFLAP will show just the one window. Instead we will make
a duplicate copy of this fle by saving it with a diferent name (select File : Save as and type
the flename "ex2. 2a-dup") . The current window is now associated with the duplicate fle. Load
the original fle ex2. 2a again and it will appear in a separate window (possibly on top of the frst
window) . Move the two windows so you can see both of them.
24
Figure 2. 7: Example from fle ex2. 2a.
We will examine the two states qo and ql to see if they are distinguishable. In one of the
windows, change the start state to ql . Examine the two DFA. Are there any strings that one DFA
accepts and the other DFA rejects?
We will examine several strings to see if there is any diference in acceptance and rejection. In
both DFA windows, select Input : Multiple Run. In both windows, enter the following strings
..
1 'd l
k t t " " " b" " b" "b " "ba a" and "bba" Select
and any addltlOna ones you ! e O ry: a , aa , aaaa , aa , a , .
Run Inputs and examine the results. Do the strings have the same result in both DFAs? There
is at least one string in which the result is Accept for one DFA, and Reject in the other DFA.
Thus the two states qo and ql are distinguishable and cannot be combined.
N ow we will examine the two states q2 and q5 to see if they are distinguishable. Dismiss the tab
in both windows to go back to the DFA window. In one window change the start state to q2 , and
in the other window change the start state to q5 . Select Input : Multiple Run again. Notice
that the strings from the last run still appear in the window. Select Run Inputs to try these
same strings. Type in additional strings and try them as well. Are these states distinguishable
or indistinguishable? They are distinguishable if there is one string that accepts in one and does
not accept in the other. All strings must be tested to determine if the states are indistinguishable.
Clearly it is impossible to test all strings, so a reasonable test set should be created.
2.2. DFA TO MINIMAL DFA 25
Figure 2. 8: Initial split of fnal and nonfnal states.
2.2.2 Conversion Example
We go through an example of converting a DFA to a minimum state DFA. Remove the previous
windows (without saving them) and load the fle ex2. 2a again, which should have the start state
qo. Select Convert : Minimize DFA. The window splits into two showing the DFA on the left
and a tree of states on the right.
We assume that all states are indistinguishable to start with. The root of the tree contains all
states. Each time we determine a distinction between states, we split a node in the tree to show
this distinction. We continue to split nodes until there are no more splits possible. Each leaf in the
fnal tree represents a group of states that are indistinguishable.
The frst step in distinguishing states is to note that a fnal and a nonfnal state are diferent.
The former accepts A and the other does not. Thus the tree has already split the set of states into
two groups of nonfnal and fnal states as shown in Figure 2. 8.
For additional splits, a terminal will be selected that distinguishes the states in the node. If
some of the states in a leaf node on that terminal go to states in one leaf node and other states on
that same terminal go to states that are in another leaf node, then the node should be split into
two groups of states (i. e. , two new leaf nodes) .
Let's frst examine the leaf node of the nonfnal states (0, 1, 2, 4, 5, 7) . What happens for each
of these states if they process a b? State qo on a b goes to state q2 , state ql on a b goes to state
qo, and so on. Each of these states on a b goes to a state already in this node. Thus, b does not
distinguish these states. In JFLAP, click on the tree node containing the nonfnal states. (Click on
the circle, not the label or the word Nonfnal . ) The states in this node are highlighted in the DFA.
Try to split this node on the terminal b. Select Set Terminal and enter b. A message appears
informing you that b does not distinguish these states.
Again select Set Terminal and enter the terminal 0. Since a does distinguish these states, the
node is split, resulting in two new leaf nodes. The set of states from the split node must be entered
into the new leaf nodes, into groups that are indistinguishable. A state number can be entered by
26
Figure 2. 9: Split node on O.
Figure 2. 10: Node (0, 1, 2, 4, 5, 7) split on O.
frst selecting the leaf node it will be assigned to, and then clicking on the corresponding state in
the DFA. Click on the left leaf node and then click on state qo in the DFA. The state number 0
should appear in the leaf node, as shown in Figure 2. 9.
State qo on an O goes to state q5 , which i s i n the node we are splitting. Note that states ql , q4 ,
and q7 on an O also go to a state in the node we are splitting. Add all of them to the same new leaf
node as 0 by clicking on these states in the DFA. The remaining states, q2 and q5 on an O, go to a
fnal state, thus distinguishing them. Click on the right new leaf node, and then click on states q2
and q5 to enter them into this node, resulting in the tree shown in Figure 2. 10. To see if we have
done this correctly, click on Check Node. Figure 2. 10 shows the resulting tree after splitting this
node on O.
2.2. DFA TO MINIMAL DFA
Figure 2. 1 1 : The completed tree of distinguished states.
Figure 2. 12: The states for the minimum DFA.

27
We must continually try to split nodes on terminals until there is no further splitting. Each
time we split a node, we have created new groups that might now allow another group to be split
that could not be split before.
Next we try to split the leaf node with states 0,1,4, and 7. Which terminal do you try? In this
case either O or b will cause a split. We will try O. Select Set Terminal and enter O. Enter the
split groups. State qo on an O goes to state q5 , which is in leaf node group 2, 5, and states ql , Q4 ,
and Q7 on an O go to states in the leaf node we are splitting. Let' s enter these states a diferent way.
Select Auto Partition and the states will automatically be entered in as shown in Figure 2. 1 1 .
When the tree is complete as it is now, convince yourself that none of the leaf nodes can be
further split) , then the only option visible is Finish. Select Finish and the right side of the window
is replaced by the new states for the minimum DFA. There is one state for each leaf node from the
tree note the labels on the states correspond to the states from the original DFA) , as shown in
Figure 2. 12. You may want to rearrange the states using the Attribute Editor.
Now add in the missing arcs in the new DFA using the Tansition Creator tool. In the
original DFA there is an O from state qo to state q5 , so in the new DFA a transition is added
28
O
a
D
8
d
D
Figure 2. 13: The minimum DFA.
from state ,, (representing the old state ,,, to state ,, (representing the old state , Selecting
Hint will add one transition for you and selecting Complete will complete the DFA, as shown in
Figure 2. 13. Selecting Done? will export the new DFA to its own window.
The minimum state DFA should be equivalent to the original DFA. Test this using the Test :
Compare Equivalence option.
Note When you select a node and select 5ct 1crm|naI, the node you select is split and two
children appear. It is possible that the node to be split might need more children; that
is, there may be or more distinguished groups split on this terminal. In that case,
you must add the additional leaf nodes by selecting the Add Ch|Id option for each
additional child desired.
2.2.3 Algorithm
We describe the algorithm to convert a DFA !I to a minimal state DFA M'.
1 . Create the tree of distinguished states as follows:
(a) The root of the tree contains all states from !I
(b) If there are both fnal and nonfnal states in M, create two children of the root-one
containing all the nonfnal states from M and one containing all the fnal states from
M.
( c) For each leaf node N and terminal J, do the following until no node can be split:
!. If states in N on J go to states in k diferent leaf nodes, k ` 1, then create k children
for node N and spread the states from N into the k nodes in indistinguishable groups.
2. Create the new DFA as follows:
(a) Each leaf node in the tree represents a state in the DFA M' with a label equal to the
states from M in the node. The start state in M' is the state that contains the start
2. 3. EXERCISES
29
Figure 2. 14: DFA from fle ex2.3a.
state from M in its label. A state in M' is a fnal state if it contains a fnal state from
M in its label.
(b) For each arc in M from states p to ,, add an arc in M' from the state that has p in its
label to the state that has ,in its label. Do not add any duplicate arcs.
2. Exercises
1 . Convert the NFAs in the given fles into DFAs.
(a) ex2-nfa2dfa-a
(b) ex2-nfa2dfa-b
(c) ex2-nfa2dfa-c
(d) ex2-nfa2dfa-d
(e) ex2-nfa2dfa-e
(f) ex2-nfa2dfa-f
2. Consider the language L = {w E L* I w does not have the substring aabb} , L = {a, b} .
Load the DFA in fle ex2.3a shown in Figure 2. 14. This DFA recognizes L.
Also load the fle ex2. 3b. It is the NFA shown in Figure 2. 15 that attempts to recognize L,
but fails.
Give an input string that shows why this NFA is not equivalent to this DFA.

44 CHAPTER 3. REGULAR GRAMMARS
(b) We now want to count the number of ways to generate some of these strings; the brute
force parser will fnd only one, but we convert the grammar to an equivalent FA and use
the fast simulator. Convert the right-linear grammar to an FA. Let aR be the string of
a's of length e. Run the fast simulator described in Section 1 . 2. 2 on the strings a
O
= A,
a
1
= a, . . . , through a
6
= aaaaaa, and count the number of ways the fast simulator fnds
to accept each of these strings. Remember, you can keep pressing Keep Looking until
the fnal summary message appears saying how many accepting confgurations it found.
(c) Let An be the number of ways the FA can accept (equivalently, that the grammar can
generate) the string an. We have Ao , Al , . . . , A6 . Present a recursive formula for An,
that is, determine a formula for An in terms of values of Ai , where i < n. Hint: Use
a counting argument. If we use the production S - aaS, how many ways are there to
generate the rest of the string without the aa ?
(d) Load the right-linear grammar in the fle ex3.6b. Let Bn be the number of ways to
generate an with this new grammar. Using your knowledge in determining a recursive
formula for An, determine a recursive formula for Bn Hint: If you convert this to an
FA, the number of accepting confgurations during simulation of a
n
is the same as the
number of ways to generate a
n
. For various a
n
, do a fast simulation as described in
Section 1 . 2. 2 to count accepting confgurations. You can manually fnd specifc Bn this
way until you see the pattern.
8. Consider the conversion of a right-linear grammar to an FA. Sometimes the conversion of a
right-linear grammar will result in a DFA, and sometimes it will result in an NFA, depending
on the structure of the grammar. In this problem we explore theoretical properties of JFLAP' s
converter of right-linear grammars to FAs.
(a) In Chapter 1 we explored a DFA that accepted the language over ' = {a, b} of any
number of a' s followed by any odd number of b' s. Can you create a right-linear grammar
that generates this language and converts directly to a DFA? If you can, create the
grammar with JFLAP and convert it to a DFA.
(b) Consider a second language, the language over ' = {a, b, c} of any number of a's followed
by any odd number of b' s, and fnally sufxed with a single c. Can you create a right
linear grammar that generates this language and converts directly to a DFA? If you can,
create the grammar with JFLAP and convert it to a DFA.
( c) What is the general characteristic of a language for which one may construct a right
linear grammar that converts directly to a DFA? Hint: The string aabbb is in the frst
language. Does any other string in that language start with aabbb ? The string aabbbc is
in the second language. Does any other string in the language start with aabbbc ?
Chapter
egDa: 1xj:essOHs
In this chapter we introduce a third type of representation of regular languages: regular expressions
(REs) . We describe how to edit REs, convert an RE to an equivalent NFA, and convert an FA to
an equivalent RE, and then give JFLAP' s formal defnition of an RE.
.J
Regular Expression Editing
Figure 4. 1: The editor for REs where the
RE (q+a) . . . + b*+cd has been entered.
In this section we learn how to edit REs. Start JFLAP' if it is al e d
.
h
, r a y runnmg, c oose to create
a new structure via the menu item File : New. Select Regular Expression from the list of new
strcture choices. A window will appear that is similar to Figure 4. 1. Since an RE is essentially a
strmg, JFLAP's RE editor consists of a small text feld in the middle of the wind ow.
JFLAP' RE h
.
s s use t ree baSiC operators. To clarify, these are not operators in the JFLAP sense,
but rather the mathematical sense (e. g. , pluses and minuses) . The three operators in order of
deceasing precedence are: the Kleene star (represented by the asterisk character *) , the concate
natlOn operator (implicit by making two expressions adjacent), and the union operator (also called
th " " e or operator, represented by the plus sign , . You may use parentheses to specify the order
45
46 CHAPTER 4. REGULAR EXPRESSIONS
of operations. Lastly, the exclamation point , , designates the empty string, and is an easy way
to enter A.
A few examples of REs will help clarify JFLAP's operators' precedence. The expression a+b+cd
describes the language {a, b, cd}, whereas abcd describes the singleton language {abcd} . The expres
sion a(b+c) d describes the language {abd, acd} , whereas ab+cd describes the language {ab, cd} . The
expression abc* describes the language {ab, abc, abcc, abccc, . . . } , whereas (abc) * describes the language
{A, abc, abcabc, abcabcabc, . . . } . The expression a + b* describes the language {a, A, b, bb, bbb, . . . } ,
whereas (a+b) * describes the language {A, a, b, aa, ab, ba, bb, aaa, aab, . . . } . The expression O +a) bc
describes the language {bc, abc} ; recall that ! is the user' s way of entering A.
In this chapter we restrict ourselves to languages over lowercase letters, but JFLAP allows any
character except * (, ) , or as part of an RE' s language. Specifcally, beware that the space
key is a perfectly legal character for a language. For example, a * where a space follows the a (so
a is followed by any number of spaces) is distinct from a* (any number of a's) . Note that none of
the regular expressions in this chapter or its exercises have spaces in them, so do not type them in.
We are going to enter the RE (q+a)+ b*+ cd, a very simple RE that indicates that we want a
string consisting of either q or a, or of any number of b' s, or the string cd. Type this RE into the
text feld.
.2 Convert a Regular Expression to an NFA
Since REs are equivalent in power to FAs, we may convert between the two. In this section we will
illustrate the conversion of an RE to an NFA. For this example we use the RE defned in Figure 4. 1,
the expression (q+ a}+b*+cd, also stored in fle ex4. la. In the window with the RE, select the menu
item Convert : Convert to NFA to start the converter.
Figure 4. 2: The starting GTG in the conversion.
For the purpose of the converter, we use a generalized transition graph (GTG), an extension of
the NFA that allows expression transitions, transitions that contain REs. In a GTG, a confguration
may proceed on a transition on a regular expression R if its unread input starts with a string 8 E R;
this confguration leads to another confguration with the input 8 read. We start with a GTG of
two states, and a single expression transition with our regular expression from the initial to the
fnal state. The idea of the converter is that we replace each transition with new states connected
by transitions on the operands of that expression' s top-level operator. (Intuitively, the top-level
4.2. CONVERT A REGULAR EXPRESSION TO AN NFA
47
operator is the operator in an expression that must be evaluated last. For example, in ab+c, the
top-level operator is + since the concatenation operator has higher priority and will be evaluated
before the +. ) We then connect these operands with A-transitions to duplicate the functionality
of the lost operator. In this way, at each step we maintain a GTG equivalent to the original RE.
Eventually all operators are removed and we are left with single character and A-transitions at ,
which point the GTG can be considered a proper NFA.
Tip You may use the Attribute Editor tool at any point to move states around. In addition
to moving states manually, with this tool the automatic graph layout algorithm may be
applied, as described in Section 1. 1. 5.
4.2.1 "De g E . T . .
- rIng an xpresslon ansltlOn
Figure 4.3: The GTG after "de-expressionifying" the
frst transition, but before we add the supporting
A-transitions.
To start converting, select the De-expressionify Tansition tool A. With this tool active click ,
on the (q+a)+b*+cd transition. The GTG will be reformed as shown in Figure 4. 3. Note that the
transition has been broken up according to the top-level + union operator, and that the operands
that were being "ored" have now received their own transitions. The De-expressionify Transition
tool :. determines the top-level operator for an expression, and then puts the operands of that
operator into new expression transitions.
Note the labels near the top of the converter view: De-oring (q+a)+b*+cd, and 6 more
A-transitions needed. These labels give an idea of what you must do next .
In this case, you must produce six A-transitions so that these new six states (q2 through q7) and
their associated transitions act like the + union operator that we have lost. To add these transitions,
select the Transition Creator tool . To approximate the union functionality, you must add six
A-transitions, three from qo to q2 , q4, and q
6
, and three more to ql from q3 , q5 , and q7. Intuitively,
48
CHAPTER 4. REGULAR EXPRESSIONS

(q+a)+b" +C
mceos nsceeded.
Figure 4. 4: The converter window in the midst of "de-oring"
the frst transition. All the A-transitions for this de-oring
have been added, except the transition from q7 to ql .
in going from qo to ql , a simulation may take the path through the (q+a) expression transition OI
the b* expression transition OI the cd expression transition. In short, these A-transitions help to
approximate the functionality of the lost + operator on these operands. Use the Tansition Creator
tool > to create these. All transitions are A-transitions, so JFLAP does not bother asking for
labels. As you add transitions, the label at the top of the window decrements the number of
transitions needed. Figure 4.4 shows an intermediate point in adding these transitions, with only
the transition from q7 to ql not created. When you fnish adding these transitions to the GTG,
JFLAP allows you to "de-expressionify" another transition.
4.2.2 "De-concatenating" an Expression Tansition
Once you fnish "de-oring" the frst transition, you have three expression transitions. We will
reduce cd next; the top-level operator for this expression is the concatenation operator. Select
the De-expressionify Transition tool once more, and click on the cd transition. In Figure 4. 5
you see the result. Note that JFLAP informs us that we are De-concatenating cd and that we
have 3 more A-transitions needed; similar to de-oring, de-concatenating requires the addition
of A-transitions to approximate the lost concatenation operator.
i > 8

Figure 4. 5: The beginning of de-con-
catenating the expression transition cd.
States and transitions extraneous to the de
concatenating are cropped out.
49
We require three A-transitions: one from q6 to qs , another from qg to qlQ, and a last one from
ql 1 to q7 Confgurations on Q will have to satisfy the c expression ,between qs and qg) , and
then satisfy the d expression ,between qlQ and ql 1 ) before proceeding to q7. This arrangement is
functionally equivalent to c concatenated with d.
A remedy of errors
Select the Transition Creator tool >. Instead of adding the right transitions, let' s add an incorrect
transition! Create a transition from q6 to qlQ. With this transition, the confguration can proceed
from Q to the d portion, bypassing c. This is incorrect. A dialog box will report A transition
there is invalid, and the transition will not be added.
Although checking for wrong transitions is universal to the converter no matter what operator
you are splitting on, the de-concatenating process has some additional restrictions. Add a transition
from ql 1 to q7 This is perfectly valid! However, JFLAP reports in a dialog, That may be
correct, but the transitions must be connected in order. In this case, this means you must
frst connect Q to qs , and then qg to qlQ, and only then may you connect ql 1 to q7 . Add these
transitions now.
Figure 4. 6: The fnished de-concatenating of
the expression transition cd.
The relevant portion of the automaton will resemble Figure 4. 6. Since you have fnished the de
concatenation of cd, you may now reduce another expression transition. Select the De-expressionify
Tansition tool - again. Recall that the converter recursively breaks down expression transitions
until they are either one character or A-transitions. If you click on the c transition, the message
That's as good as it gets appears to inform you that you needn' t reduce that transition.
4.2.3 "De-staring" a Tansition
We will reduce the b* transition next. With the De-expressionify Tansition tool active, click the
b* transition. Kleene stars may have only one operand, in this case b. As we see in Figure 4. 7, the b
has been separated into a new portion of the automaton. JFLAP tells us that we are De-staring
h* and that there are 4 more A-transitions needed.
Similar to concatenations and ors, we must add A-transitions to duplicate the functionality of
the Kleene star. The four transitions that JFLAP wants are from q4 to q12 and q13 to q5 (to allow
confgurations to read a b from their input) , and another from q4 to q5 (to allow zero b' s to be
read) , and the last from q5 to q4 (to allow for repeat reading of b) . Select the Tansition Creator
tool > and add these transitions so the relevant portion of the GTG resembles Figure 4. 8. ,
Figure 4. 7: The beginning of de-staring
the expression transition b*. States and
transitions extraneous to the de-staring are
cropped out.
Figure 4. 8: The fnished de-staring of the
expression transition b*.
4. 2.4 Surrounding Parentheses
51
The only remaining existing transition incompatible with an NFA is the (q+a) transition, which has
surounding parentheses. The parentheses are the top-level operator since they indicate that their
contents must be evaluated frst, and only when that evaluation fnishes do the parentheses fnish
evaluating. However, when the parentheses surround the entire expression, they are completely
unnecessary. Activate the De-expressionify Tansition tool J, and click on the (q+a) transition.
The surrounding parentheses will disappear, leaving you with q+a. No A-transitions are needed.
H
a
Figure 4. 9: The fnished de-oring of the expression tran
sition q+a.
Figure 4. 10: The NFA that recognizes the language
(q+a)+b*+cd.
To fnish, use the De-expressionify Tansition tool - tool once more to break q+a by the +
operator. Connect A-transitions similar to the procedure described in Section 4. 2. 1, so that the
relevant section of the GTG resembles Figure 4. 9, and overall the automaton resembles Figure 4. 10.
The GTG is now a proper NFA, so the conversion to an NFA is fnished! You may press the Export
button to put the automaton in a new window.
4.2.5 Automatic Conversion
Dismiss the Convert RE to NFA tab now. Once you have returned to the RE editor, select the
menu item Convert : Convert to NFA. We shall convert the same RE again, but we'll do it
automatically this time!
Once you see the converter view with the GTG as pictured in Figure 4. 2, press Do Step. A step
in this conversion is the reduction of a single expression transition. There is only one expression
transition, the q+a)+b*+cd transition, so that is reduced and the requisite A-transitions are added
without intervention from the user.
The second option is Do All; this is functionally equivalent to pressing Do Step until the
conversion fnishes. This is useful if you want the equivalent NFA immediately. Press Do All; the
fnished NFA will appear in the window, ready to be exported.
4.2.6 Algorithm to Convert an RE to an NFA
1 . Start with an RE R.
2. Create a GTG G with a single initial state qo , single fnal state q1 , and a single transition
from qo to q1 on the expression R.
3. Although there exists some transition t E G from states qi to qj on the expression S longer
than one character, let be the top-level operator of the expression S, and let aI , a2, . . . , a,p[
be the ordered list of operands of the operator (since parenthetical and Kleene star operators
take exactly one operand 1 = 1 in those cases) .
(a) If is a parenthetical operator, replace t with an expression transition on a1 from qi to
qj .
(b) If is a Kleene star operator *, , create two new states qx and qy for G, remove t , and
create an expression transition on a1 from qx to qy , and create four A-transitions from
qi to qx , qy to qj , qi to qj , and qj to qi
(c) If is a union operator +) , remove t, and for each k from 1 through 1 (i) create two
new states qXk and qYk ' (ii) create an expression transition on ak from qXk to qYk ' and
(iii) create two A-transitions, from qi to qXk and from qYk to qj .
(d) If is a concatenation operator, remove t , and for each k from 1 through 1J (i) create two
new states qXk and qYk ' (ii) create an expression transition on ak from qXk to qYk ' and
4. 3. CONVERT AN FA TO A REGULAR EXPRESSION 53
(iii) if k ` 1 create a A-transition from qYk-l to qXk . Finally, create two A-transitions,
one from qi to qXl and another from qy'i to qj .
4. The GTG is now a proper NFA. The conversion is fnished.
*
. Convert an FA to a Regular Expression
The conversion of an FA to an RE follows logic that is in some respects reminiscent of the RE to
NFA conversion described in Section 4. 2. We start with an FA that we consider a GTG for the
purposes of conversion. We then remove states successively, generating equivalent GTGs until only
a single initial and single fnal state remain. JFLAP then uses a formula to express the simplifed
GTG 8 a regular expression.
E
D
Figure 4. 1 1 : The FA we convert to an RE.
In this walk-through we convert the automata pictured in Figure 4. 1 1 to a regular expression.
This automata is stored in the fle ex4. 3a. Open this automata. Choose the menu item Convert
: Convert FA to RE to begin converting. Your window will resemble Figure 4. 12.
4.3.1 Reforming the FA to a GTG
The algorithm to convert an FA to an RE requires frst that the FA be reformed into a GTG with
a single fnal state, an initial state that is not a fnal state, and exactly one transition from qi to qj
for every pair of states qi and qj (i may equal j) .
Reform FA to have a single noninitial fnal state
There are two things wrong with our FA's fnal states: there are two fnal states, and one of them
is also the initial state. We must reform the automaton so that it has exactly one fnal state and
ensure that that fnal state is not the initial state. To do this JFLAP frst requires that a new state
be created: select the State Creator tool and click somewhere on the canvas to create a new
state. (Similar to the conversion from an RE to an NFA, this converter also displays directions
above the editor. At this stage it tells you Create a new state to make a single fnal state. )
54
JHAP :
fi l e I nput Test Convert Hel p
lT
D3K0 H 0|0H' H| Udl ! G3| >30
Lt03l 3 0 5l3\0 U O3Kt d S' HQ| 0H3 5 l|0.

Figure 4. 12: The starting window when con
verting an FA to an RE.
e
d
Figure 4. 13: The FA after a new fnal state is created.
Once this new state is created, the FA will resemble Figure 4. 13. Note that this new state is the
fnal state, and those states that were previously fnal states are now regular states and have been
highlighted. JFLAP directs you to put A-transitions from old fnal states to new. Select
the Transition Creator tool . and create transitions from each of the highlighted states to the
new fnal states. JFLAP assumes that every transition is a A-transition and does not query for the
4.3. CONVERT AN FA TO A REGULAR EXPRESSION
E
d
Figure 4. 14: The FA after the A-transitions
have been made from the old fnal states to
the new fnal state.
55
transition label. As you create each A-transition, the source state will be de-highlighted. When
you fnish, your FA will resemble Figure 4. 14.
Collapse multiple transitions
One of the requirements of this algorithm is that for every pair of states Q and Qj there must be
exactly one transition from Q to Qj . Half of this requirement is that there cannot be more than
one transition from Q to Qj . Consider the two loop transitions for Q on d and e. We can satisfy
the requirement by replacing these two transitions with the single expression transition d+e, which
indicates that we may proceed on either d or e.
Select the Tansition Collapser tool
, and click on either the d or e. When you click on

a transition that goes from Q to Qj , this tool reforms all transitions from Q to Qj into a single
transition where the labels of the removed transitions are separated by + operators. The new
transition will be either d +e or e +d, either of these is equivalent, of course, but for the sake of
this discussion's simplicity we assume the result was d+e. With this step, our GTG is no longer a
proper FA. The GTG is shown in Figure 4. 15.
In general, i f more than one pair of states have more than one transition, use the Tansition
Collapser tool on their transitions as well .
Add empty transitions
Recall once more that every pair of states Q and Qj must have exactly one transition from Q to
Qj . This means that if no transition exists, an empty trnsition on the empty set symbol 0) must
56
d +e
Figure 4. 15: The GTG after the d and e
loop transitions on ql are combined into
d+e.
be created! Select the Tansition Creator tool - again, and create a transition from qo to q2 . A
transition on 0 will appear.
d +e
Figure 4. 16: The FA after the addition of
empty transitions.
The essential distinction between GTGs and FAs is that FA transitions describe a single string,
while GTG transitions describes sets of strings. In this particular case, we are creating transitions
on the empty set of strings, hence transitions on 0. Similar to the earlier creation of A-transitions,
JFLAP assumes you are creating empty transitions. As you proceed, JFLAP will inform you how
many more empty transitions are required. Seven are required in all: from qo to q2, ql to q3 , q2 to
qo, q3 to qo, q3 to ql , q3 to q2, and a loop transition on q3 (q3 to q3) . When you fnish, your GTG
will resemble Figure 4. 16.
4.3. CONVERT AN FA TO A REGULAR EXPRESSION
4.3.2 Collapse Nonfnal, Noninitial States
57
Now we have a GTG with a single fnal state, an initial state that is not a fnal state, and for every
pair of states qi and qj there is exactly one transition from qi to qj. The next step is to iteratively
rmove every state in the GTG except the fnal state and the initial state. As each state is removed,
we adjust the transitions remaining to ensure the GTG after the state removal is equivalent to the
G TG before the state removal.
0 0 a
0 J o
0 3 A
1 0 o
J J a c
J 3 ca
3 0
3 1
: 3
Finalize
Figure 4. 17: The window that shows the
replacement transitions when removing a
state.
The states can be collapsed in any order. However, to understand the following discussion, you
will need to collapse states in the given order. Select the State Collapser tool . Once selected,
click frst on state q2

A window like the one shown in Figure 4. 17 appears that informs you of the
new labels for transitions before the collapse occurs. Let 7ij be the expression of the transition from
qi to qj . The rule is, if we are removing qk , for all states qi and qj so that i i k and j i k, 7ij is
replaced with 7ij + 7ik7kk7kj . In other words, we compensate for the removal of qk by encapsulating
in the walk from qi to qj the efect of going from qi to qk (hence 7ik) , then looping on qk as much
as we please (hence 7kk) ' and then proceeding from qk to qj (hence 7kj) . Lastly, note that 0 obeys
the following relations: if 7 is any regular expression, 7 + 0 = 7, 70 = 0, and 0* = A.
Select the row that describes the new transition from ql to ql (the loop transition on ql ) ,
d+e+ca*c. The transitions from which this new transition is composed are highlighted in the GTG.
There are two paths that must be combined into one expression transition, the walk from ql to ql ,
d+e, and the alternative walk from ql to ql that goes through q2 , ca*c. More formally, 71, 1 = d+e,
71 , 2 = 72, 1 = c, and 72,2 = a, so the new transition is 71 1 + 71 272* 272 1 = d + e + ca* c as JFLAP ,
' "
M
58
indicates.
The rules for operations on the empty set are more unfamiliar. Select the row that describes
the new transition from ,,to ql . There are two paths that must be combined into one expression
transition, the walk from ,,to qo, b, and the alternative walk from ,,to ,,that goes through
q, , 0a*c. More formally, , = b,
, = 0, ,, = a, and , , = c, so the new transition is

,+ ,,,, ,= b+0a*c. The concatentation of any expression with the empty set is the empty
set, so 0a*c = 0, so b+a*c = b+. The union of the empty set with any expression is that expression,
so b+0 = b, which is the new expression from ,,to ql
Figure 4. 18: The fnished GTG after the
removal of q2 and ,,
Inspect all the other replacements to see if you can fgure out the formula, and then reduce it to
the label shown in Figure 4. 1 7. Then click Finalize. The transitions listed will be replaced, and q2
will be removed. Repeat this process with q1 . Note there are only four replacements, and some of
the labels are quite long. (You might have to resize the window to see the complete labels. ) When
ql is removed, your GTG will resemble Figure 4. 18.
4.3.3 Regular Expression Formula
At this point your GTG should have two states-one fnal and one initial-and resemble Figure 4. 18.
Let ,be the expression of the transition from ,,to , For a GTG in this form, where qi i s the
initial state and qj is the fnal state, the equivalent RE is given by equation 4. l.
(4. 1,
The conversion is now fnished, and JFLAP displays the RE of equation 4. 2, derived from
equation 4. 1 .
(a+b (d+e+ca*c) *b) * ( A+b (d+e+ca*c)* ca*
(4. 2)
At this point, you may press Export to put the fnished RE in a new window.
4. 4. DEFINITION OF AN RE IN JFLAP
Note If for your input FA any of these steps are unnecessary, JFLAP will skip over them. In
the extreme case, if you have an FA with two states one initial, the other final,, and
with four transitions a loop on the initial, a loop on the final, another from the initial
to final , and a last one from the final to the initial,, JFLAP will skip everything and
display the finished RE!
4.3.4 Algorithm to Convert an FA to an RE
1 . Start with 8 FA, though we consider it a GTG G for the purpose of the algorithm.
59
2. Let F be the set of G's fnal states, and ,,be its initial state. If E ` 1 or F = {qo}, create
a new state qf, produce A-transitions for every qi E F from qi to qf, and make ,the only
fnal state.
3. Let S be the set of G's states. For every qi , qj, E S ` S, let L= {,! , 2 , . . . , n} be the set
of expressions of transitions from qi to qj . Let e = 0 if L = 0 and e = 1 + 2 +
. . .
+ n
otherwise, and replace all transitions from qi to qj with a single transition from qi to qj on
the expression e.
4. Let 1be the set of G' s nonfnal, noninitial states. Let ,be the expression of the transition
from qx to , For every qk E T, for every qi , qj , E 1- {qk}) ` 1- {qk}) replace rij with
rij + rikrkrkj , and fnally remove qk from G. (Note: If I is any regular expression, I + 0 =
0 = 0, and 0* = A. )
5. G now has two states: the initial state ,,and single fnal state qf. The equivalent regular
expression is = ,,,
,,
*
,,
,
. Defnition of an RE in JFLAP
Let " be some alphabet. The set of all possible regular expressions is given by R.
R = {0, A} U " U {abl a, b E R} ' {a+bl a, b E R} ' {a*l a E R} ' {(a) la E R}
. Summary
In Section 4. 1 we learned how to edit regular expressions (REs) . JFLAP respects the following
operators in order of decreasing precedence: the Kleene star (the * character) , concatenation
(implicit by making two expressions adjacent) , and lastly, union (the character) . Parentheses

JFLAP Manual PDF

Uploaded by

Copyright:

Available Formats

JFLAP Manual PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

JFLAP Manual PDF

Uploaded by

Copyright:

Available Formats

JFLAP lu:lDj

ons When a confguration proceeds to a state qi, Step with Closure

Figure 1.8: An NFA equivalent to that of Figure 1.5.

Figure 2. 12: The states for the minimum DFA.

, and click on either the d or e. When you click on

, = 0, ,, = a, and , , = c, so the new transition is

You might also like