Editing Create FA

==Definition==
<P>JFLAP defines a finite automaton (FA) <I>M</I> as the quintuple <I>M</I>
= (<I>Q</I>, Σ<!--capital sigma-->, δ<!--small delta-->, <I>q<SUB>s</SUB></I>,
<I>F</I>) where 
</P>
<P><I>Q</I> is a finite set of states {<I>q<SUB>i</SUB></I> | <I>i</I>
is a nonnegative integer} <BR>Σ is the finite input alphabet <BR>δ
is the transition function, δ : <I>D</I> →<!--right arrow--> 2<I><SUP>Q</SUP></I>
where <I>D</I> is a finite subset of <I>Q</I> &times;<!--times--> Σ*
<BR><I>q<SUB>s</SUB></I> (is member of<!--&#8712;--><!--element of-->
<I>Q</I>) is the initial state <BR><I>F</I> (is a subset of<!--&#8839--><!--subset of or equal-->
<I>Q</I>) is the set of final states 
</P>
<P>Note that this definition includes both deterministic finite
automata (DFAs), which we will be discussing shortly, and
nondeterministic finite automata (NFAs), which we will touch on
later. 
</P>
Building the different types of automata in
JFLAP is fairly similar, so let's start by building a DFA for the
language <I>L</I> = {<I>a<SUP>m</SUP>b<SUP>n</SUP></I> : <I>m</I> ≥<!--greater --><!--than or equal-->
0, n &gt;<!--greater than--> 0, <I>n</I> is odd}. That is, we will
build a DFA that recognizes that language of any number of <I>a</I>'s
followed by any odd number of <I>b</I>'s. (Examples taken from <I>JFLAP:
An Interactive Formal Languages and Automata Package</I> by Susan
Rodger and Thomas Finley.) 
</P>

==The Editor Window==
<P>To start a new FA, start JFLAP and click the <B>Finite Automaton</B>
option from the menu. 
</P>
<P ALIGN=CENTER>[[Image:faSelection.png]]
</P>
<P ALIGN=CENTER>Starting a new FA 
</P>
<P>This should bring up a new window that allows you to create and
edit an FA. The editor is divided into two basic areas: the canvas,
which you can construct your automaton on, and the toolbar, which
holds the tools you need to construct your automaton. 
</P>
<P ALIGN=CENTER>[[Image:faNewWindow.png]]
</P>
<P ALIGN=CENTER>The editor window 
</P>
<P><A NAME="toolbar"></A>Let's take a closer look at the toolbar. 
</P>
<P ALIGN=CENTER>[[Image:faToolbar.png]]
</P>
<P ALIGN=CENTER>The FA toolbar 
</P>
<P>As you can see, the toolbar holds four tools: 
</P>
<UL>
	<LI><P STYLE="margin-bottom: 0in">Attribute Editor tool 
	[[Image:images/arrow.gif]]
	[http://jflap.wikia.com/wiki/Create_FA#Defining_Initial_and_Final_States sets initial and final states]
	</P>
	<LI><P STYLE="margin-bottom: 0in">State Creator tool 
	[[Image:images/state.gif]]
	<A HREF="#creatingStates">creates states</A> 
	</P>
	<LI><P STYLE="margin-bottom: 0in">Transition Creator tool 
	[[Image:images/transition.gif]]
	<A HREF="#creatingTransitions">creates transitions</A> 
	</P>
	<LI><P>Deletor tool 
	[[Image:images/delete.gif]]
	<A HREF="#deleting">deletes states and transitions</A> 
	</P>
</UL>
<P>To select a tool, click on the corresponding icon with your mouse.
When a tool is selected, it is shaded, as the Attribute Editor tool 
[[Image:images/arrow.gif]]
is above. Selecting the tool puts you in the corresponding mode. For
instance, with the toolbar above, we are now in the Attribute Editor
mode. 
</P>
<P>The different modes dictate the way mouse clicks affect the
machine. For example, if we are in the State Creator mode, clicking
on the canvas will create new states. These modes will be described
in more detail shortly. 
</P>
<P>Now let's start creating our FA. 
</P>
==Creating States==
<P>First, let's create several states. To do so we need to activate
that State Creator tool by clicking the 
[[Image:images/state.gif]]
button on the <a href="#toolbar">toolbar</a>. Next, click on the
canvas in different locations to create states. We are not very sure
how many states we will need, so we created four states. Your editor
window should look something like this: 
</P>
<P ALIGN=CENTER>[[Image:images/faStatesCreated.png]]
</P>
<P ALIGN=CENTER>States created 
</P>
<P>Now that we have created our states, let's define initial and
final state. 
</P>
==Defining Initial and Final States==
<P>Arbitrarily, we decide that <I>q</I><SUB>0</SUB> will be our
initial state. To define it to be our initial state, first select the
Attribute Editor tool 
[[Image:images/arrow.gif]]
on the <A HREF="#toolbar">toolbar</A>. Now that we are in Attribute
Editor mode, right-click on <I>q</I><SUB>0</SUB>. This should give us
a pop-up menu that looks like this: 
</P>
<P ALIGN=CENTER>[[Image:images/faStateMenuInitial.png]]
</P>
<P ALIGN=CENTER>The state menu 
</P>
<P>From the pop-up menu, select the checkbox <B>Initial</B>. A white
arrowhead appears to the left of <I>q</I><SUB>0</SUB> to indicate
that it is the initial state. 
</P>
<P ALIGN=CENTER>[[Image:images/faInitialState.png]]
</P>
<P ALIGN=CENTER><I>q</I><SUB>0</SUB> defined as initial state 
</P>
<P>Next, let's create a final state. Arbitrarily, we select <I>q</I><SUB>1</SUB>
as our final state. To define it as the final state, right-click on
the state and click the checkbox <B>Final</B>. It will have a double
outline, indicating that it is the final state. 
</P>
<P ALIGN=CENTER>[[Image:images/faFinalState.png]]
</P>
<P ALIGN=CENTER><I>q</I><SUB>1</SUB> defined as final state 
</P>
<P>Now that we have defined initial and final states, let's move on
to creating transitions. 
</P>
==Creating Transitions==
<P>We know strings in our <A HREF="#language">language</A> can start
with <I>a</I>'s, so, the initial state must have an outgoing
transition on <I>a</I>. We also know that it can start with any
number of <I>a</I>'s, which means that the FA should be in the same
state after processing input of any number of <I>a</I>'s. Thus, the
outgoing transition on <I>a</I> from <I>q</I><SUB>0</SUB> loops back
to itself. 
</P>
<P>To create such a transition, first select the Transition Creator
tool 
[[Image:images/transition.gif]]
from the <A HREF="#toolbar">toolbar</A>. Next, click on <I>q</I><SUB>0</SUB>
on the canvas. A text box should appear over the state: 
</P>
<P ALIGN=CENTER>[[Image:images/faTransition1a.png]]
</P>
<P ALIGN=CENTER>Creating a transition 
</P>
<P>Note that λ<!--lambda-->, representing the empty string, is
initially filled in for you. If you prefer ε representing the empty
string, select <B>Preferences : Preferences</B> in the <A HREF="#editor">main
menu</A> to change the symbol representing the empty string. 
</P>
<P>Type &quot;a&quot; in the text box and press <B>Enter</B>. If the
text box isn't selected, press <B>Tab</B> to select it, then enter
&quot;a&quot;. When you are done, it should look like this: 
</P>
<P ALIGN=CENTER>[[Image:images/faTransition1b.png]]
</P>
<P ALIGN=CENTER>Transition created 
</P>
<P>Next, we know that strings in our <A HREF="#language">language</A>
must end with a odd number of <I>b</I>'s. Thus, we know that the
outgoing transtion on <I>b</I> from <I>q</I><SUB>0</SUB> must be to a
final state, as a string ending with one <I>b</I> should be accepted.
To create a transition from our initial state <I>q</I><SUB>0</SUB> to
our final state <I>q</I><SUB>1</SUB>, first ensure that the
Transition Creator tool 
[[Image:images/transition.gif]]
is selected on the <A HREF="#toolbar">toolbar</A>. Next, click and
hold on <I>q</I><SUB>0</SUB>, and drag the mouse to <I>q</I><SUB>1</SUB>
and release the mouse button. Enter &quot;b&quot; in the textbox the
same way you entered &quot;a&quot; for the previous transition. The
transition between two states should look like this: 
</P>
<P ALIGN=CENTER>[[Image:images/faTransition2b.png]]
</P>
<P ALIGN=CENTER>Second transition created 
</P>
<P>Lastly, we know that only strings that end with an odd number of
<I>b</I>'s should be accepted. Thus, we know that <I>q</I><SUB>1</SUB>
has an outgoing transition on <I>b</I>, that it cannot loop back to
<I>q</I><SUB>1</SUB>. There are two options for the transtion: it can
either go to the initial state <I>q</I><SUB>0</SUB>, or to a brand
new state, say, <I>q</I><SUB>2</SUB>. 
</P>
<P>If the transition on <I>b</I> was to the initial state <I>q</I><SUB>0</SUB>,
strings would not have to be of the form <I>a<SUP>m</SUP>b<SUP>n</SUP></I>;
strings such as <I>ababab</I> would also be accepted. Thus, the
transition cannot be to <I>q</I><SUB>0</SUB>, and it must be to <I>q</I><SUB>2</SUB>.
</P>
<P>Create a transition on <I>b</I> from <I>q</I><SUB>1</SUB> to <I>q</I><SUB>2</SUB>.
As the FA should accept strings that end with an odd number of <I>b</I>'s,
create another transition on <I>b</I> from <I>q</I><SUB>2</SUB> to
<I>q</I><SUB>1</SUB>. Your FA is now a full, working FA! It should
look something like this: 
</P>
<P ALIGN=CENTER>[[Image:images/faFinished.png]]
</P>
<P ALIGN=CENTER>The working FA 
</P>
<P>You might notice that the <I>q</I><SUB>3</SUB> is not used and can
be deleted. Next, we will describe how to delete states and
transitions. 
</P>

==Deleting States and Transitions==
<P>To delete <I>q</I><SUB>3</SUB>, first select the Deletor tool 
[[Image:images/delete.gif]]
on the <A HREF="#toolbar">toolbar</A>. Next, click on the state <I>q</I><SUB>3</SUB>.
Your editor window should now look something like this: 
</P>
<P ALIGN=CENTER>[[Image:images/faFinished2.png]]
</P>
<P ALIGN=CENTER><I>q</I><SUB>3</SUB> deleted 
</P>
<P>Similarly, to delete a transition, simply click on the input
symbol of the transition when in Deletor mode. 
</P>
<P>Your FA, <A HREF="files/faex.jff">faex.jff</A>, is now complete.</P>
<H2><A NAME="multipleRun"></A>Running the FA on Multiple Strings</H2>
<P>Now that you've completed your FA, you might want to test it to
see if it really accepts strings from the <A HREF="#language">language</A>.
To do so, select <B>Input : Multiple Run</B> from the menu bar. 
</P>
<P ALIGN=CENTER>[[Image:images/faMultipleRun.png]]
</P>
<P ALIGN=CENTER>Starting a multiple run tab 
</P>
<P>A new tab will appear displaying the automaton on the left pane,
and an input table on the right: 
</P>
<P ALIGN=CENTER>[[Image:images/faMultipleRunTab.png]]
</P>
<P ALIGN=CENTER>A new multiple run tab 
</P>
<P>To enter the input strings, click on the first row in the <B>Input</B>
column and type in the string. Press <B>Enter</B> to continue to the
next input string. When you are done, click <B>Run Inputs</B> to test
your FA on all the input strings. The results, <B>Accept</B> or
<B>Reject</B> are displayed in the <B>Result</B> column. You can also
load the inputs from file delimited by white space. Simply click on
<B>Load Inputs</B> and load the file to add additional input strings
into multi-run pane.</P>
<P ALIGN=CENTER>[[Image:images/faMultipleRan.png]]
</P>
<P ALIGN=CENTER>Running multiple inputs 
</P>
<P>Clicking <B>Clear</B> deletes all the input strings, while <B>Enter
Lambda</B> enters the empty string at the cursor. <B>View Trace</B>
brings up a separate window that shows the trace of the slected
input. To return to the Editor window, select <B>File : Dismiss Tab</B>
from the menu bar. 
</P>

==Building a Nondeterministic Finite Automaton==
<P>Building a nondeterministic finite automaton (NFA) is very much
like building a DFA. However, an NFA is different from a DFA in that
it satisfies one of two conditions. Firstly, if the FA has two
transitions from the same state that read the same symbol, the FA is
considered an NFA. Secondly, if the FA has any transitions that read
the empty string for input, it is also considered an NFA. 
</P>
<P>Let's take a look at this NFA, which can be accessed through
<A HREF="files/ex1.3a.jff">ex1.3a.jff</A>: (Note: This example taken
from <I>JFLAP: An Interactive Formal Languages and Automata Package</I>
by Susan Rodger and Thomas Finley.) 
</P>
<P ALIGN=CENTER>[[Image:images/nfa.png]]
</P>
<P ALIGN=CENTER>An NFA 
</P>
<P>We can immediately tell that this is an NFA because of the four
λ<!--lambda-->-transitions coming from <I>q</I><SUB>3</SUB> and <I>q</I><SUB>9</SUB>,
but we might not be sure if we have spotted all the nondeterministic
states. JFLAP can help with that. 
</P>
<H2><A NAME="nondeterminism"></A>Highlighting Nondeterministic States</H2>
<P>To see all the nondeterministic states in the NFA, select <B>Test
: Highlight Nondeterminism</B> from the menu bar: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaHighlight.png]]
</P>
<P ALIGN=CENTER>Highlighting nondeterministic states 
</P>
<P>A new tab will appear with the nondeterministic states shaded a
darker color: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaHighlightTab.png]]
</P>
<P ALIGN=CENTER>Nondeterministic states highlighted 
</P>
<P>As we can see, <I>q</I><SUB>3</SUB> and <I>q</I><SUB>9</SUB> are
indeed nondeterministic because of their outgoing λ<!--lambda-->-transitions.
Note that they would both be nondeterministic even if they each had
one λ<!--lambda-->-transition instead of two: only one λ<!--lambda-->-transition
is needed to make a state nondeterministic. We also see that <I>q</I><SUB>1</SUB>
is nondeterministic because two of its outgoing transitions are on
the same symbol, <I>a</I>. Next, we will go through JFLAP's tools for
running input on an NFA. 
</P>

==Running Input on an NFA==
<P>To step through input on an NFA, select <B>Input : Step with
Closure...</B> from the menu bar. A dialog box prompting you for
input will appear. Ordinarily, you would enter the input you wish to
step through here. For now, type &quot;aaaabb&quot; in the dialog box
and press <B>Enter</B>. You can also load the input file instead of
typing the string. 
</P>
<P><B>NOTE :</B> When loading input from the file, JFLAP determines
end of input string by the white space. Thus if there is string “ab
cd” in a file, only “ab” will be considered as an input (“cd”
will be ignored since there is a white space before them).</P>
<P ALIGN=CENTER>[[Image:images/nfaStepInput.png]]
</P>
<P ALIGN=CENTER>Entering input 
</P>
<P>A new tab will appear displaying the automaton at the top of the
window, and configurations at the bottom. The current state is
shaded. 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep0.png]]
</P>
<P ALIGN=CENTER>A new input tab 
</P>
<P>First, let's take a closer look at a configuration: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaConfig.png]]
</P>
<P ALIGN=CENTER>A configuration icon 
</P>
<P>The configuration icon shows the current state of the
configuration in the top left hand corner, and input on the white
tape below. The processed input is displayed in gray, and the
unprocessed input is black. 
</P>
<P>Click <B>Step</B> to process the next symbol of input. You will
notice <I>q</I><SUB>1</SUB> becomes the shaded state in the NFA, and
that the configuration icon changes, reflecting the fact that the
first <I>a</I> has been processed. Click <B>Step</B> again to process
the next <I>a</I>. You will find that four states are shaded instead
of one, and there are four configurations instead of one. 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep2.png]]
</P>
<P ALIGN=CENTER><I>aa</I> processed 
</P>
<P>This is because the machine is nondeterministic. From <I>q</I><SUB>1</SUB>,
the NFA took both <I>a</I> transitions to <I>q</I><SUB>2</SUB> and
<I>q</I><SUB>9</SUB>. As <I>q</I><SUB>9</SUB> has two λ<!--lambda-->-transitions
(which do not need input), the NFA further produced two more
configurations by taking those transitions. Thus, the simulator now
has four configurations. Click <B>Step</B> again to process the next
input symbol. 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep3.png]]
</P>
<P ALIGN=CENTER><I>aaa</I> processed 
</P>
<P>Notice that two of the configurations are highlighted red,
indicating they were rejected. Looking at their input, we also know
that only <I>aa</I> was processed. What happened? 
</P>

==Producing a Trace==
<P>To select a configuration, click on it. It will become a solid
color when selected, instead of the slightly graded color. Click on
the icon for the rejected configuration with state <I>q</I><SUB>11</SUB>,
and click <B>Trace</B>. A new widow will appear showing the traceback
of that configuration: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaTrace.png]]
</P>
<P ALIGN=CENTER>A configuration's traceback 
</P>
<P>The traceback shows the configuration after processing each input
symbol. From the traceback, we can tell that that configuration
started at <I>q</I><SUB>0</SUB> and took the transition to <I>q</I><SUB>1</SUB>
after processing the first <I>a</I>. After processing the second <I>a</I>,
it was in <I>q</I><SUB>11</SUB>. Although <I>q</I><SUB>11</SUB> is
not adjacent to <I>q</I><SUB>1</SUB>, it can be reached by taking a
λ<!--lambda-->-transition from <I>q</I><SUB>9</SUB>. As the
simulator tried to process the next <I>a</I> on this configuration,
it realized that there are no outgoing <I>a</I> transitions from <I>q</I><SUB>11</SUB>
and thus rejected the configuration. 
</P>
<P>Although rejected configurations will remove themselves in the
next step, we can also remove configurations that have not been
rejected. 
</P>

==Removing Configurations==
<P>Looking at the tracebacks of the rejected configurations, we can
tell that any configurations that are in <I>q</I><SUB>11</SUB> or <I>q</I><SUB>6</SUB>
and whose next input symbol is <I>a</I> will be rejected. 
</P>
<P>As the next input symbol is <I>a</I>, we can tell that the
configurations that are currently in <I>q</I><SUB>6</SUB> and <I>q</I><SUB>11</SUB>
will be rejected. Click once on each of the four configurations to
select them, then click <B>Remove</B>. The simulator will no longer
step these configurations. (Although we are only removing
configurations that are about to be rejected, we can remove any
configurations for any purpose, and the simulator will stop stepping
through input on those configurations.) 
</P>
<P>Your simulator should now look something like this: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep3b.png]]
</P>
<P ALIGN=CENTER>Rejected configurations removed 
</P>
<P>Now when we step the simulator, the two configurations will be
stepped through. 
</P>
<P>Looking at the two configurations above, we might realize that the
configuration on <I>q</I><SUB>3</SUB> will not lead to an accepting
configuration. We can test our idea out by freezing the other
configuration. 
</P>

==Freezing and Thawing configurations==
<P>To freeze the configuration on <I>q</I><SUB>10</SUB>, click on <I>q</I><SUB>10</SUB>
once, then click the <B>Freeze</B> button. When a configuration is
frozen, it will be tinted a darker shade of purple: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep3c.png]]
</P>
<P ALIGN=CENTER>Configuration on <I>q</I><SUB>10</SUB> frozen 
</P>
<P>With that configuration frozen, as you click <B>Step</B> to step
through the configuration on <I>q</I><SUB>3</SUB>, the frozen
configuration remains the same. Clicking <B>Step</B> two more times
will reveal that the configuration on <I>q</I><SUB>3</SUB> is not
accepted either. Your simulator will now look like this: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep5.png]]
</P>
<P ALIGN=CENTER>Other configurations rejected 
</P>
<P>To proceed with the frozen configuration, select it and click
<B>Thaw</B>. The simulator will now step through input as usual.
Click <B>Step</B> another three times to find an accepting
configuration. An accepting configuration is colored green: 
</P>
<P ALIGN=CENTER>[[Image:images/nfaStep8.png]]
</P>
<P ALIGN=CENTER>Accepting configuration found 
</P>
<P>If we click <B>Step</B> again, we will see that the last
configuration is rejected. Thus, there is only one accepting
configuration. However, we might be unsure that this is really the
case, as we had removed some configurations. We can double-check by
resetting the simulator. 
</P>

==Resetting the simulator==
<P>At any point in the simulation, we can restart the entire
simulation process by clicking <B>Reset</B>. This will clear all the
current configurations and restart the simulation. If we click <B>Reset</B>
and step all the configurations, we will find that there is, indeed,
only one accepting configuration.</P>
<P>This concludes the walkthrough, although there is an appendix
noting a few more features that JFLAP supports.</P>
</A><B><STRONG><U>Appendix</U></STRONG>
</B>
</P>
<B>Notes</B></P>
<P>To add a note to a JFLAP file, choose the Attribute Editor, right
click and select “Add Note”. The note will start with the message
&quot;insert_text&quot;. To change the text simply click in the note,
select where you want to start typing, and type your note. Click
outside the note to get rid of the cursor. Click and drag the note to
move it.</P>
<P ALIGN=CENTER>&lt;[[Image:note.jpg]]
<P CLASS="style5" ALIGN=LEFT><A NAME="selection"></A>Selection 
</P>
<P>To select more than one state or block at once, choose the
attribute editor, click on empty space, and drag the mouse. A
bounding box appears and all states and blocks within the box are
selected, their color now blue. To move the selected states as a
group, click and drag any of them. To deselect them, click anywhere
else.</P>
<P ALIGN=CENTER>[[Image:selection.jpg]]

==Layout Commands (as of JFLAP version 6.2)==
<P>JFLAP will now let you apply predefined graph layout commands to
your graph, which can help with a more aesthetically pleasing graph.
There is a new menu in the automaton editor window, the “View”
menu, which will allow one to both save the current graph layout and
to apply different graph layout commands and algorithms. For a full
tutorial on how to use these features, and to see a description of
the built-in layout commands, feel free to read the <A HREF="../layout/index.html">layout
command tutorial.</A></P>
<P>The following are pictures of the finite automaton used earlier,
<A HREF="files/ex1.3a.jff">ex1.3a.jff</A>, with new graph layouts.
The first picture demonstrates the automaton under a “GEM” layout
algorithm, the second under a “Tree (Degree, Vertical)” layout
algorithm, and the last under a “Two Circle” layout algorithm.</P>
<P ALIGN=CENTER>[[Image:ex1_3aGEM.jpg]]
<P ALIGN=CENTER>[[Image:ex1_3aTreeDV.jpg]]
<P ALIGN=CENTER>[[Image:ex1_3aTwoCircle.jpg]]
<P><B>This concludes our brief tutorial on building finite automata.
Thanks for reading!</B> 
</P>
</BODY>
</HTML>