COSC1105/1107 – Computing Theory JFLAP Warmup Exercise A/Prof. ̃a
Semester 2, 2019
This is an introductory exercise to JFLAP1, a tool to provide hands-on experience with formal languages. JFLAP provides graphical tools to visualise various formal concepts that we will be teaching in this course such as finite automatons, regular expressions, Turing machines, etc. More information about JFLAP can be found at its website http://www.jflap.org/.
Though this exercise does not carry any marks, it will help students to familiarize with JFLAP that will be used in assessments. We strongly advise to get started on this exercise as soon as possible to weed out any teething problems that may arise.
1 Download JFLAP
JFLAP requires JAVA version 1.6 or higher. You can check the default java version in your system by running the command “java -version” in a terminal/console. In case you have an older version of JAVA, you can get the latest version from here.
1. Please fill out the download form.
2. Aftersubmittingtheform,apagewillbeshown that has multiple versions to download. Please download the May 15, 2011 version that has SVG included.
3. RunJFLAPwiththefollowingcommand“java -jar
Figure 1: JFLAP home screen.
JFLAP is a powerful tool to manipulate various formalisations and all its capabilities can be accessed via its home screen. Do not be alarmed to see options that may not make sense to you at this stage. During the course you will be introduced to these concepts.
1 http://www.jflap.org/
1
2 Finite Automaton
We will create a simple finite state automaton using JFLAP. Fi- nite state automatons are simple machines to recognize regular lan- guages. They can be visualized as graphs consisting of states and transitions. Let us create a simple three state automaton.
1. Click the “Finite Automaton” button (first button from top) on the JFLAP home screen.
2. A new window should be created with an Editor tab opened (see Figure 2).
3. The image below shows the editor tools seen at the top area of the tab.
2.1 Creating states
Let us now create and add some states to our FSM:
Figure 2: Editor for finite automaton.
1. Click the create state button and do a left mouse click anywhere in the empty canvas area of the editor. A state with label q0 should be created. Do two more left mouse clicks to create states q1 and q2.
2. Choose the select tool by doing a left mouse click on the select button in the editor tools.
3. Right click on the state q0. A context menu should appear as shown in the figure below.
2
4. Choose “Initial” from the menu to make q0 as the initial state for the automaton. Similarly, right click on state q2 and make it a final state by selecting “Final”. Observe that q0 has a triangle pointing towards it and q2 has a double outline.
2.2 Creating transitions
1. Select the create transition tool by doing a left mouse click on it in the editor tools.
2. Left click and hold on state q0 and drag towards state q1 without releasing the mouse. Release the mouse once
it is over state q1. A text input field should appear between the states q0 and q1 as shown below.
3. Type the letter “a” in the input field and press enter. An arrow with label “a” should appear between states q0 and q1. Add another transition between states q1 and q2 with label “b”. The automaton should now look like the figure below.
4. Try deleting the transition between q1 and q2 using the delete tool and re-creating it again as per the previous step.
5. In this step we will add a “loop” on state q1. Select the create transition tool. Left click on state q1, drag and release the mouse while in state q1. Type the letter “c” in the input text field that appears. You should now see a loop on state q1 with label c.
Congratulations! You have just created your first automaton in JFLAP.
2.3 Saving and loading files
Saving and loading files with JFLAP is similar to any other software you might have used.
1. Select the “Save as” sub-menu under the “File” menu see on the top of the editor.
2. Browse to the directory where you want to save the file and enter the file name “FirstFSA” before clicking the Save button. JFLAP files are saved using the “jff” extension.
3. Exit JFLAP.
4. Open JFLAP again (see Step 3 in Section 1).
5. From the home screen of JFLAP (see Figure 1) open the saved file using the File menu.
6. The Finite Automaton editor should automatically open showing the finite state automaton you just created.
3
2.4 Simulations
Recall that finite state automatons can be used to recognize languages. Let us now test what words can be recognized by the automaton we created. Intuitively, a finite state automaton accepts a word if starting from the initial state the automaton reaches a final state once it has consumed all the symbols in the word.
For example, consider a word w1 consisting of just a single symbol a; that is, w1 = a. Our automaton will start from its initial state q0, read symbol a, and transition to state q1. State q1 is not an final state and there are no more symbols to read, hence the automaton terminates at q1 without accepting the word w1.
Consider another word w2 = ab. The automaton will begin in its initial state q0, read a and transition to q1. Once in q1 it will read the last remaining symbol b and transition to q2. Since q2 is a final state and we have read all the input, the automaton terminates in q2 accepting the word w2.
Time for some hands-on exercise! Make sure that the automaton we created is open the editor. From the top menu left click Input and select “Step by State”. A new window will open. Please type the word “ab” and press OK. A new tab will open as shown below.
Press the “Step” button located at the bottom left of the Simulate tab. See how the active state changes as the input is sequentially read. Experiment simulating the automaton with different inputs. Observe the area where the input is mentioned will turn green when an input is accepted and red when an input is rejected.
4