fulltext - MDH DiVA
Contents
1. There are several ways to teach automata by visualization that is useful for students One way is so called hypertext books 13 These were HTML pages that have active learning applets which the students are encouraged to step through on their own Majority of simulators found on the internet are have no graphical interface but they are frameworks that either have the necessary algorithms Such as conversion between automata types minimization etc or drawing tools One of them is FAgoo which contains graph drawing algorithms for arranging finite automata 15 GraphViz is used on some of our test simulators and is very extensive graph viewing software that supports most type of graphs 16 2 2 Collection of simulators Most of the simulators are found using the Google Search engine with the keywords automata automaton Turing Machine Pushdown grammar simulator sim editor state graph Only exception is JFLAP which was known beforehand from the FABER course 2 3 Review of Simulators To select the best and most usable simulator tests have to be made with each of them The best simulator is the one easiest to use and have enough features to aid the user with By creating different automata types that the current program supports we can get an image of how helpful the program really is Test cases were created for different automata to test each simulator see Table 1 1 ab 2 aWaaWa W a b 3 aa a b a 1 a ab a 2 0012. Conclusion Automaton Simulator Functionality There seem to be few functions included with Automaton Simulator Among other there are lack of conversion between regular expressions and FA and no determination and minimization Tools The debugging is very good when you press a letter into the tape the states change immediately to green when they are active This makes it easy to follow what is happening There is no transition table that shows all previous steps User Friendliness Creating finite automata is straightforward and simple The downside is that it doesn t support using different languages you only have alphabet with a and b It is sometimes hard to know what to do or not like whenever you can add something onto the tape Sometimes it works but if there is anything wrong with your automata the tape will not respond The program does not tell what certain settings mean like when adding values to a PDA transition there are no hints if you have your mouse over push or pop The application lacks a selection tool which makes it very easy to create new states by mistake WA runkK Figure 8 Automaton Simulator with Turing machine that duplicates numbers Design The layout of the application is simple and straightforward Documentation The home website has a documentation page which covers the basics of the program Compatibility The simulator runs with Java 1 3 and is cross platform The applica
3. The application includes automata determination and minimization The program lacks some useful features There is no conversion from automata to grammar or regular expressions User Friendliness Making automata is easy and straightforward There are however some negative features I do not like the popup settings that show up every time you add an item I got into problems creating usual NFA s with lambda transitions I cannot add lambda transitions and using e or eps as epsilon did not work either which is confusing Tools Debugging works well you see what happens and every transition is animated with a moving dot where the active state has a different color The debug output is well printed with the mathematical notation similar to a transition table Design The program could be simpler The toolbar have a couple of functions that changes graphical setting like anti aliasing or changing the background grid which would be better hidden in a graphical options menu Instead there could be a menu there to set the values for a selected state The good is that the debug tool is well made and easy to use Documentation The documentation is sparse and lacks a detailed manual Compatibility The source code uses a Nokia Qt based user interface and Graphviz for automata graphics A Windows binary and source code is available from the home page Getting started with the source code might get problematic for some students and withou
4. 010 3 aa a b ba 1 A A A Aze 2 S AB A aaA a B bBa bb 3 S AB A aAb ab B aaBla Turing 1 Duplicate the number of ones Ex 1111 1111 1111 Machine 2 L a b n gt m gt 0 3 L a b c n gt 0 Table 1 Testcases for different types of automata Each simulator is rated within six different categories These categories are discussed separately for each simulator and a score is given for each simulator These criteria gets a grade from 1 to 5 where 1 is the worst and 5 is the best see Table 2 Functionality What functions are there and how they help the user How many types of automata supported Tools How do the different tools available help the user Mainly aims the automata debug features User Friendliness Is the application user friendly Layout Design How the application is structured and its graphical quality Compatibility Do the application work on any PC Is it difficult to start Documentation Is there a manual or documentation available Functionality documentation and compatibility will discuss which features ex platform independent each simulator has Tools user friendliness and layout will be more what the author thinks about each simulator Thus the review will reflect both what the author thinks about each program and its actual features To get a grade four in Functionality a simulator should handle all automata types plus regular expressions and grammar
5. plus conversion from regular expression or grammar to NFAs Determination and minimization algorithms are also considered A grade five should be more than that Functionality No or few Some functions Most functions All necessary More than all functions available available functions necessary available available functions available Tools Hard to use Hard to use Some difficulties Easy to use Easy to use Debug features Debug less to use Debug is Debug is very not helpful helpful Minor Partially helpful helpful helpful No output output Some output Detailed Detailed output output User Friendly Not user Less user Partially user User friendly Very user friendly friendly friendly friendly Layout Design Inconsistent Inconsistent Consistent Consistent Consistent layout layout layout layout layout Easy to navigate Hard to Insufficient Average Easy to Best graphical navigate graphical quality graphical quality navigate quality Poor graphical Good quality graphical quality Compatibility OS dependent Some cross Cross platform Cross platform Cross platform Difficult to platform Easy to begin on Easy to start Easy to begin on begin with capability atleastone OS on most OS s any OS Documentation No Minor Manual or guide Atleasta Complete documentation documentation showing how the manual documentation tool works covering most and or more issues Table 2 Grading criteria Simulators that prove difficult to use do
6. be set Below is a tape the user can type in while the Turing machine is running During debugging the current state is marked with a yellow color The whole machine can be executed at once or the user can step states using the play button Each transition is set by pressing any letter on your keyboard There are two variables in each transition which is an input value and one action Epsilon is chosen by pressing shift e moving the head is done with the direction keys 26 Conclusion Tuatara Turing Machine Simulator Functionality e This simulator only handles Turing machines e There is no way of converting TM to Grammar or regular expressions Tools Creating Turing machines is simple and fast but transitions are specified differently which is confusing There is an input and an action or write to set at each transition which makes creation of Turing machines more confusing Debugging is easy you select the start point and reset the tape then you can run your program When executing or stepping the Turing machine each stage is colored and the tape is updated until the final stage is reached If something went wrong you are noticed with a warning message for example if the writer gets behind the starting point of the tape User Friendliness The editor feels good to work with but there were few problems during use for example Tuatara could be more helpful explaining how to create transitions Design The layout is similar to what yo
7. be simpler Now you must click on the letters you want in a table os z Grec e I o ena amp Xaa z Or gt a ew i a CAUsessingerDropbox Work Egobb Research siens PetC images Second Test Images OFA 2 complex dfacomplex a pe j Ki EE pl igas a aaaabbaba Boe x Figure 17 PetC with the language L aWaaWa W a b Design States and transitions is not rendered at all while you drag them around having the states moving alongside the mouse while dragging feels more responsive Documentation There is a tutorial available on the home webpage that goes through the basic parts of the application Compatibility This program was currently only available for download as a Windows binary which is not good for non Windows users 25 Simulator Tuatara Turing Machine Simulator Home Page http tuataratmsim sourceforge net Current Version 1 0 Description Tuatara Turing Machine Simulator is written by Jimmy Foulds with founding from the Department of Mathematics at the University of Waikato 7 Features e Supports Turing machines e Uses several Turing machines simultaneously Review File Edit Mode Machine Tape Alphabet Help Figure 18 TTMS with Turing machine States and Transitions can easily be added to the workspace The user can create new automata in the same window Before running your Turing machine both initial final state and the alohabet must
8. grammars a gt aBB b S gt aABC c SSAB AS cc A gt aa aaA A aalA B gt bB A B gt bbBlbc B gt bbB bb B gt bb C gt ccC c BoA Assignment 2 5 Consider the following language L a b a where x gt 0 using the alphabet X a b a Create the Grammar for this language b What type of grammar do you get You can use JFLAP to determine which type you have via the Test menu c Create a PDA from this Grammar Save both the Grammar and the PDA in separate JFLAP files 26 Assignment 3 JFLAP EXERCISES ON RESTRICTION FREE LANGUAGES AND TURING MACHINES Assignment 3 1 Turing machines are more powerful than PDA and JFLAP gets very useful when creating these Every transition has three symbols that you have to specify Read Write and Direction which tells the head what to do next In JFLAP the blank symbol is represented as L ol gt o c ala Read Write Direction What happens in this TM Why is it important to use a tape Show some input using JFLAPs transducer As you would notice empty tapes is accepted how should you prevent that from happening Save your project in a new file and create a TM that fixes that a b C d Ss Assignment 3 2 Create the following Turing machine Describe what this Turing machine does recreate it and test run in JFLAP What language does this Turing machine accept Assignment 3 3 Construct a Turing machine that accepts t
9. into several functions which the user needs to learn how to use them properly CAUsers Inger Dropbox Work Exjobb Research sims Visual Automata Simulator generic generic Visual Automata Simulator E File Edit Machine Run Tape Tools Window Help Enumeration a b add o sjal PEREZ amp Figure 22 Visual Automata Simulator with Turing machine 31 Conclusion Visual Automata Simulator Functionality Converting NFA to DFA is one of the only implemented features For example determination and minimization is not available Pushdown Automata is also not available Tools The debugging feature works well The user can type an input with a corresponding alphabet and by pressing the Debug one step makes the simulator to go one step The problem is that you have to go every time to the upper menu to select the option to go one step think that having a debug output somewhere is preferable to see what exactly happens instead of just only the automata The states either are red or green depending they are in an accepting or rejected state User Friendliness It is easy to create finite automata The Turing machine part of the editor is not similar and is harder to learn on your own There are some misconceptions like Lambda transitions that are not automatically created when adding a blank transition This result in a rejected state although
10. tape As said the program is simple but it is a bit harder to learn and use on your own Design The layout is dated but yet very simple Documentation There is a guide on the webpage that explains the syntax and how to use the application Compatibility The simulator is available as source code and as an applet on the home webpage with instructions With an assignment with Turing machines this program can work well 29 Simulator Visual Automata Simulator Home Page http www cs usfca edu jbovet vas html Current Version Version 1 2 2 Description This application is created by Jean Bovet from the University of San Francisco According to the home website this simulator is created with the inspiration from an automata and object orientation course 1 Features e Supports DFA NFA Turing Machines e Convert NFA DFA e Save to BMP JPEG and more Review When the application starts you begin directly in the editor see Figure 20 Either the user can use a DFA or NFA or by pressing new to change to a Turing machine The toolbar is simple and contains a select state or transition buttons The user can change the automaton type between DFA and NFA The alphabet can be set in the Alphabet textbox and a string can be set as input The user simply press run to test that string CAUsers Inger Dropbox Work Exjobb Research sims Visual Automata Simulator images LORD File Edit Machine Run Tools Window H
11. that should be active once the string is accepted and consumed There can be more than one final state J Initial Change Label Clear Label Clear All Labels Set Name r Automaton Size To run this DFA select nout Step By State then choose an input string to run the automata with 20 Input bel U O O You will see JFLAP s simulation view where you can debug the automaton while it consumes the input string Use the Step button to step trough the string Here the automaton have moved the active state and have consumed all the b characters File Input Test View Convert Help Editor Simulate bbbba Freeze Thaw Trace Remove Once the whole string is consumed the automata should park at the final state and the stack turns green The string is accepted Ejs titled 1 gt File Input Test View Convert Help Editor Simulate bbbba Freeze Thaw Trace Remove Try to use Input Multiple Run instead Which strings are accepted and which ones are rejected 21 Assignment 1 2 Create the following NFA a Write down 4 accepted strings and 4 strings that are not accepted b Which of the following regular languages over the alphabet a b are accepted by the automaton 1 L aba 2 L aba a 3 L a ba ba 4 L a bba baa c Construct a regular expression using JFLAP Use Convert Conv
12. thought that it should be accepted Luckily lambda or epsilon is set as e in the settings menu Design The layout is nice and simple and is very similar to JFLAP States and transitions can be moved around nicely Documentation The home webpage is simple with some images and videos but no mayor documentation or guides Like the lambda transitions it makes it hard to know if the functionality is there or not Compatibility Visual Automata Simulator uses Java and should like JFLAP run well on most platforms While testing the application using Windows 7 the application could freeze without any error message Using this simulator in course assignments has potential with FA but is too complicated for assignments with Turing machines 32 3 2 Simulator Analysis Discussion All of the collected simulators have been tested To make it easier the results is collected for easier overview Most programs had problems with sparse features and documentation which creates limitations that is harder to use JFLAP is the only simulator with a full range of features see Table 3 Most of the programs can at least edit and create two types of automata but very few of them that can convert Regular Expressions or Grammar to a Finite Automata JFLAP can also handle TM which most simulators that aim at DFA and NFA do not have yet LI F Available Partially available Not available Table 3 Automata types available All tests where eas
13. three variables First is the input second pops from the stack and the third variable is push Try to debug the PDA with the step by state feature You will notice that you have a stack that is added and removed from during each step Automaton Size 14 Grammar Grammar is created using a table in JFLAP If you choose grammar as a new project in JFLAP you will have a table where you can edit the grammar Here we have a simple grammar with the language a b where n 2 0 File Input Test Convert Help Editor Table Text Size LHS S gt A A A Create and edit a grammar is simple Create symbols by adding them to the LHS column and rules under RHS then press enter The arrow between the symbols and rules is automatically created Lambda is done by leaving the rule empty then press enter and you will see the lambda symbol there Grammar can be tested by using any of the features under Input One is Brute Force Parse which can test single strings each time Convert Pushdown Automata to Grammar Conversion with PDA is very similar to converting FA but there are differences that are good to know before creating PDA s File Input Test View Convert Help Editor Automaton Size 15 To convert PDA to Grammar in JFLAP a couple of conditions must be met e For each transition pop 1 symbol and push either O or 2 symbols e There must be only one fina
14. Simulators for formal languages automata and theory of computation with focus on JFLAP D Tobias Fransson tfN09001 Wstudent mdh se Institutionen f r Datavetenskap och Elektronik IDE Handledare och examinator Gordana Dodig Crnkovic V ster s 2013 ABSTRACT This report discusses simulators in automata theory and which one should be best for use in laboratory assignments Currently the Formal Languages Automata and Theory of Computation course FABER at M lardalen University uses the JFLAP simulator for extra exercises To see if any other simulators would be useful either along with JFLAP or standalone tests were made with nine programs that are able to graphically simulate automata and formal languages This thesis work started by making an overview of simulators currently available After the reviews it has become clear to the author that JFLAP is the best choice for majority of cases JFLAP is also the most popular simulator in automata theory courses worldwide To support the use of JFLAP for the course a manual and course assignments are created to help the student to getting started with JFLAP The assignments are expected to replace the current material in the FABER course and to help the uninitiated user to get more out of JFLAP SUMMARY JFLAP is the currently used simulator in the Formal languages Automata and Theory of Computation course FABER at Malardalen University The tests are made with nine p
15. anual dfaj File Input Test View Convert Help Editor Simulate bba Simulate bba Step Reset Freeze Thaw Trace Remove Now the last character is about to be consumed This step shows the transition between q0 and q1 If there happen to be multiple paths with same character you will see them grayed out File Input Test View Convert Help Step Reset Freeze Thaw Trace Remove The simulator reached the final state JFLAP manual dfajf File Input Test View Convert Help Editor Step Reset Freeze Thaw Trace Remove To restart the test you can select the reset button to start from the beginning or press the X button in the top right corner to go back to the editor Show Nondeterminism Creating NFA is no different to creating DFA Finite Automata is considered either a DFA or NFA depending if there is lambda transitions or paths with same symbols The previous automaton is a NFA because of the lambda transition where you can access all paths from the q2 state It is possible to let JFLAP determine if the automaton is a non deterministic automaton Select Test then Highlight Non Determinism File Input Test View Convert Help Editor Nondeterminism Nondeterministic states are highlighted This simply shows that the q2 state is non deterministic Convert NFA to DFA JFLAP can convert NFA to DFA This automaton has two nondeterministi
16. c states which could easily be changed back to a DFA r 5 JFLAP nfa2 jff File Input Test View Convert Help Editor Automaton Size Create a NFA and then choose Convert Convert to DFA This will open the conversion view where you either let JFLAP do the work or try yourself to convert it The left view is the original automata and the right one is the new DFA Use the state expander tool to expand the states until the DFA is complete Using the Complete button will automatically create the whole DFA for you The Done button will tell if the DFA is either done or not Once the DFA is complete it will be exported to a new JFLAP window with your converted DFA File Input Test View Convert Help Editor NFA to DFA Regular Expressions Regular Expressions can be typed into JFLAP which can then be converted to an NFA File Convert Help Editor Edit the regular expression below a b bbal Choose Regular Expression in the main menu then just type the expression in the textbox Definitions for Regular Expressions in JFLAP e Kleene Star e Union e Empty String Correctly written expressions can then be converted to a NFA To convert your expression select Convert Convert to NFA The conversion will begin with two states and a transition with your Regular Expression With the D e expressionify Transition tool y
17. ct 7 Load Inputs Run Inputs Clear Enter Lambda View Trace Figure 14 JFLAP with the language a a with multiple debug Creating DFA and NFA both combined as FA in JFLAP is fast and you do not have to set any variables or labels by adding items Users do not have to set any alphabet before debugging which makes this simulator very straightforward By double left clicking any transition the user can easily setup every transition gt Se elle x File Input Test View Convert Help Editor Figure 15 JFLAP with NFA representing the language 001 010 FA PDA and Turing machines are very similar to create and edit with some differences like transitions and which algorithms like automata conversion you can apply 22 Conclusion JFLAP Functionality e JFLAP have enough features for the FABER course and more e Determination and Minimization for automata is available e Images can be made from current automata easily Tools It is easy to debug your creations with one or multiple inputs JFLAP responds well and changes active states to grey when the Step by State feature is selected There should have been some interactive animation for each transition which JFLAP does not have Typing in a single input is possible where the user either gets a rejected or accepted state when done User Friendliness It s easy to create Finite Automata you simply poi
18. e University http www cs colostate edu massey Teaching cs301 RestrictedAccess JFLAP gettingstarted html Finite Automata and Regular Languages Finite Automata The simplest type to begin with is Finite Automata which is the first option from the selection menu In JFLAP both DFA and NFA is created using Finite Automata grato ole File Help Batch Preferences Line automaton Multi Tape Turing Machine Grammar L System Regular Expression Regular Pumping Lemma Context Free Pumping Lemma Now you should have an empty window in front of you You will have a couple of tools and features at your disposal Sieg _ l Pat lt unttied gt e 5 File Input Test View Convert Help Editor kx O Ed MA G Editor k oj 2a 2 A e E pi Automaton Size The toolbar contains six tools which are used to edit automata Attribute Editor Tool change properties and position of existing states and transitions State Creator Tool creates new states Transition Creator Tool creates transitions Deletion Tool deletes states and transitions Undo Redo changes the selected object prior to their history Creating an automaton is easy with the state and transition tools Note that you need to change back to the Attribute Editor Tool first to change states Let s try to add states with the State Creator Tool Second When adding states the
19. e converted to an automaton and back JFLAP has been used worldwide on many automata theory courses and is still under development Links to manuals and resources If you have problems use the provided manual JFLAP User Manual JFLAP s home page also contains a very thorough tutorial of everything the program can do JFLAP Home Webpage www jflap org Recommended reading is JFLAP An Interactive Formal Languages and Automata Package by Susan H Rodger and Thomas W Finley ISBN 9780763738341 Here are as well files for this book http www cs duke edu csed jflap jflapbook files Lab Instructions When you are done with each task save your work in JFLAP as jff files and call them ass1_1 jff after each assignment Also a Word document should be provided if there are any questions asked Save everything in a compressed RAR file with the name laborationX_yourname rar 18 Assignment 1 JFLAP EXERCISES ON REGULAR LANGUAGES AND FINITE STATE AUTOMATA Assignment 1 1 Create this Deterministic Finite Automaton First start JFLAP and select Finite Automaton as a new automaton Use the toolbar to drag and drop states and transitions File Input Test View Convert Help Editor ol c Automaton Size 19 Remember that initial and final states must be set to make the automaton run State q0 is set as the initial state which means the starting state State q3 will be the final state which is a state
20. e toolbar Options like undo and save alongside with graphical fidelity settings are available from the toolbar as well 00 5 001111 Q1 Q3 0 01111 1 Q2 00 1111 ACCEPT Q2 001 111 ACCEPT N NM 14 LACCERT Animation speed 500ms gt V Use animations Generate slideshow Step speed 1 0s V Pretty printing Close Figure 1 Automata Editor with NFA 001 010 10 Each time you add a state or transition you get a dialog where you can set some settings for this item You can safely pass this one and set them later by left click then select Edit The Quick Mark Initial sets the state as an initial state State dialog add Jetzen K il el Label New labell V Automatically generated name Name OO Type State v Dimmed FT Quick mark Initial Figure 2 Settings for added states in Automata Editor The debug window run in front of the editor and gives debug output and the ability to pause the execution The currently active state is rendered in grey which changes during execution The debug or simulation dialog prints out every step which is very easy to understand During tests with NFA I could not find how to create lambda transitions Other than that creating NFA was as easy as DFA and the debug tool did run correctly which makes the simulator able to process some NFAs 11 Conclusion Automata Editor Functionality
21. elp Untitled I FETTER baad bk CH Gel ton DFA Alphabet ab String aaabbb v DE ReadyNew State double clic Select States clic amp drag mouse Move All shift amp drag mouse Contextual Menu ctri clic er Figure 20 Visual Automata Simulator with the language ab 30 By selecting Run then Debug enables you to debug the automata step by step The automaton gets animated where the active transition and state gets red or green depending if the state is final Below is also a console like output where the user can inspect every step C Users Inger Dropbox Work Exjobb Research sims Visual Automata Simulator images Second Test ImagesiDF WS om So File Edit Machine Run Tools Window Help a remaining string aaab states q0 accepting false a remaining string aab states q0 accepting false a remaining string ab states q0 accepting false a remaining string b states q0 accepting false Debugger stopped nc more characters to process Debugger stopped no more characters to process New State double clic Select States clic amp drag mouse Move All shift amp drag mouse Contextus Figure 21 Debugging in Visual Automata Simulator There simulator can handle Turing machines However the notation is difficult to understand Here every TM state is split down
22. emove Delta New Machine Load Machine lt 3 zb Render to File Save Machine lt 3 a gt 6 lt 3 b gt 6 If Al lt 3 gt 6 c7 c7 b s9 Construct Regex Parse Regex ql a lt 3 e a c11 EI Parse String Determinize Minimize Figure 4 The main window in Automata Editor 13 a Automata Editor oye l Symbols a b Add Symbol Remove Symbol States 4 3 2 0 5 1 Add State Remove State Initial 0 Finals 4 Set Initial Set Finals Add Delta Remove Delta New Machine Load Machine Figure 5 Automata Editor with DFA accepting the string abba By pressing Parse Regex you can test the automata with a single input You get either an accepted or rejected massage after the test is complete Figure 6 Parsed from a a b ba a Creating automata without planning is not a good idea You might need to rethink your design on a pen and paper It is easier if you have your automata ready and just input all the states and transitions This makes experimentation hard because the interface is so restrictive It is faster to create regular expressions that you input using the Parse Regex button The program does not remember used expressions so you have to remember them yourself The Preview windows do manage to handle most automata and makes them easy to follow and read Though there is no way to graphically manipulate the result in this preview window Aut
23. ert FA to RE d Construct a Grammar using JFLAP use Convert Convert To Grammar e Try to convert the automaton to a DFA Once you are done JFLAP should export the result to a new JFLAP window Save the resulting DFA as a new JFLAP file 22 Assignment 1 3 JFLAP supports creation of FA from a regular expression First you need to select Regular Expression in the selection menu Just type the expression in the box and then select Convert to FA where you can step trough the conversion until the automaton can be exported to a new window If the automaton is correct it should be possible to convert it back to a regular expression again Use these regular expressions to be converted to a Finite Automaton Note that JFLAP creates a lot of lambda transitions in this part The result can be improved by converting the resulting NFA to a DFA and then minimize the automaton Example DFA created from the Regular Expression 1 0 Convert the following regular expressions to FA a a a b b b 1 1 0 1 c a a b bb a b d ab a ba b 23 Assignment 1 4 Create Regular Grammar and tell which language the grammar generates Then convert Regular Grammar to a Finite Automaton try to do the FA yourself Then save the result H ez ab e ba e gt 10A B bB AS abBibaS AS 0IB BoA B gt bba A gt IIB B I15S 10A Bo 11 Each of these Finite Automata can easily be converted back to a Grammar which you are free to tr
24. es e Supports DFA and NFA e Unfortunately as the creator clearly states on the homepage the application is far from complete Review You can have multiple automatons in the same editor window Here you can create new automata or open an existing one You can simply add new states and transitions States automatically gets their name when they are created You need to specify your alphabet set before you continue The A button in the tooloar opens a menu where you can specify the Alphabet E Ea PT Petc INONAMEI eh Si rt File Edit Run Question Do Window Options Help o eee ai KBR r Or gt a rim Figure 16 PetC with the language 001 010 Below the workspace is a toolbar where you can debug your automaton You simply put in the input string in the textbox and press Run You will see that the program eats the string until a message box pops up with either an accepted or rejected state It works well to create both DFA and NFA 24 Conclusion PetC Functionality With PetC the user can edit more than one automaton PetC is missing any conversion feature and both Determination and Minimization Tools The debug functions can be found beneath the workspace where you edit the automata The debugging is animated with the current state either colored in red or green User Friendliness The editor works as expected it s easy to create more simple automatons Setting the alphabet could
25. fewer features or did not perform any beiter than JFLAP Tests were obvious where simple tasks that JFLAP did very well were tedious in other programs The problem with comparison between automata simulators from the internet is that their functionalities are different and often difficult to match with each other Nevertheless even though some particular functions in some simulators may be better in general JFLAP functionality is superior Given JFLAP as a simulator of choice the manual and assignments are written for use with JFLAP From the manual and assignments the user can learn how to use the program and how to create basic automata and languages Writing this report was useful to learn how to create automata for assignments Also there was testing of software which was a good exercise in studying software and deciding which are best 34 5 FUTURE WORK There is a lot to improve in automata simulation as in most simulator programs tested the interface is often outdated New programs that make such improvements are a good idea to review and consider using in the future Computers and phones with touch screen control are today more common than ever Automata simulation using touch control would be interesting where students and teachers can learn about automata in a more interactive and entertaining way Testing simulators for popular mobile platforms is a good idea and could be an alternative to JFLAP Currently I have not seen anyone ma
26. he first time I also had problems running strings with my creations which other automata simulators accepted easily Like most other simulators the interface is simplified but creating automata is often tedious and time consuming Design Graphics is minimalistic and good looking For some reason states are box shaped and not circles like in other simulators The transitions curve themselves and it is hard to make them look good Documentation There is a textual tutorial on the home page with basic information Compatibility Uses Java and is cross platform But it did crash for me while testing using Windows 7 The program is available on the Sourceforge webpage which have not been updated since 2009 20 Simulator JFLAP Home Page http www jflap org Current Version Version 7 0 Description JFLAP is created by Susan Rogers and her students at Duke University and is the simulator that has been used in the automata course at MDH among others It has a wide range of different automaton types to simulate and a lot of features that help the user to manipulate automata without using pen and paper Features Supports FA PDA TM Grammar RE and more Save image to BMP or JPEG and more Convert NFA DFA Convert RE NFA Convert Grammar NFA Determination and Minimization Review You select your preferred language in the starting menu By start creating FA you simply select Finite Automata in the menu After selecting automa
27. he following languages a L a b where n gt 0 a b b L a b c where n gt 0 a b c c TM that doubles the number of a in a string of ae Ex aaa should be aaaaaa Assignment 3 4 Create a Turing machine that adds two binary strings into one single binary The operands should be binary strings with a plus operator in between Example is that 1010 1001 on the tape should produce the result 10011 on the tape To get you started the program can check each digit on both strings from left to right and check what the result should be from these Symbols can also be set like 1010 1001B at the end of the right operand where the program can write the answer Assignment 3 5 Create a Turing machine that accepts the language L a b m gt n gt 0 28
28. how which transition that not have been used in the grammar yet JFLAP automatically puts labels under states to tell which symbols they represent in the grammar File Input Test View Convert Help itor Convert to Grammar l r lf f Hint Show All What s Left Export As mentioned you can either edit the right side grammar table or click on states to automatically reveal the grammar for each step The Hint reveals which state you should select next Show All automatically creates the grammar for you Once the grammar is complete you can select Export to open a new JFLAP window with your new Grammar don t forgot to save if you want your grammar saved 13 Context Free Grammar and Pushdown Automata Pushdown Automata Creating PDA in JFLAP is just as easy as creating FA but there are some differences First you select Pushdown Automaton in the selection menu which also shows up when selecting new in File 1 Type of PDA Input Multiple Character Input Single Character Input First the program asks if you want to use either Multiple or Single Character Input which means how many characters may be consumed at each step The editor looks exactly like editing Finite Automata This PDA accepts the language L a b where n gt 0 The PDA is tested exactly like FA s Transitions are different where they now consist of
29. king an automata simulator for mobile platforms To improve exercises for the FABER course it is a good idea to create and maintain our own automata simulator that fit our own needs With software we understand we can quickly add the features we need 6 REFERENCES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Visual Automata Simulator http www cs usfca edu jbovet vas html 16 10 12 jFAST finite automata simulator http sourceforge net projects jfast fsm sim 4 1 13 Turing Machine simulator http ironphoenix org tril tm 4 1 13 JFLAP http www jflap org 4 1 13 Automata Editor http automataeditor sourceforge net 4 1 13 Automaton Simulator http ozark hendrix edu burch proj autosim 4 1 13 Tuatara Turing Machine Simulator http tuataratmsim sourceforge net 4 1 13 Automata Editor http max99x com school automata editor 4 1 13 PetC http oeople dsv su se henrikbe petc 4 1 13 Mississippi State University course Introduction to Formal Languages and Automata http www cse msstate edu cse3813 summer10 4 1 13 P Linz An introduction to FORMAL LANGUAGES AND AUTOMATA 5th ed Jones And Barlett P Linz S H Rodger JFLAP Activities for Formal Languages and Automata included CD ROM from 11 J J Cogliati F W Goosey M T Grinder B A Pascoe R J Ross C J Williams Realizing the Promise of Visualization in the Theory of Computing Montana State Universit
30. l state with transitions that pop Z off the stack Trying to convert a PDA that not follows this will result in an error message that shows which transitions should be corrected To start converting select Convert Convert To Grammar This is the conversion screen on the left is the PDA and on the right is the grammar You can either fill the grammar yourself or select each transition to fill out the grammar Note that the grammar will be filled with a lot of useless rules which happens when using brute force File input Test View Convert Help tor Convert to Grammar Hint Show Aa What s Left Export EE Kee ol Sol gt a qlXq0 q0Xq1 ol kal gt a ql Xql ql kal ol Sal gt a ql Xq2 q2Xql ql Sal gt a ql Xq3 q3Xq1 qi Xq2 a ql Xq0 q0Xq2 ql Xq2 gt a ql Sai ql Xq2 ql Xq2 gt a ql Xq2 q2Xq2 ol Xq2 gt a q1Xq3 q3Xq2 qiXq3 gt a qlXq0 q0Xq3 ql Xq3 gt a q1Xq1 q1Xq3 ql Xq3 gt a ql Xq2 q2Xq3 ql Xq3 gt a ql Xq3 q3Xq3 qi Xq2 zb q2Xq2 gt b q2Zq3 gt When all rules are set from every transition you can choose to select Export to transfer the Grammar to a new JFLAP window JFLAP can trim down the useless rules into a readable grammar File Input Test Convert Help Editor Table Text Size LHS aAQ b gt b aAB gt A 16 Restriction Free Languages and Turing Machines Turing Machine A T
31. lar Expressions Assignment 2 The second assignment handles Pushdown Automata and Context Free Grammar Assignment 3 The third assignment handles Turing machines and restriction free languages 37 8 MANUAL AND EXERCISES 8 1 Appendix 1 Manual for JFLAP simulator use in the Formal Languages Automata and Theory of Computation course JFLAP User Manual For JFLAP version 7 0 Content INTRODUCTION EE 2 Ee Eltre EE e 2 EE 2 USING ELA EE EEN 2 ADDITIONAL RESOURCES EEN 2 FINITE AUTOMATA AND REGULAR LANGUAGES ccccecccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccecccccccscces 3 FINT EAT OM En KEE 3 SHOW NON DETERMINISM consi eeneg EE ee 8 CONVERT INE AsO DRA E EE 9 REGULAR EXPRESSIONS EE 10 CONVERT EA TO REGULAR EXPRESSION eege eege eg a so cua Rai E AA Rotel tees 11 CONVERT FATO GRAMMAR EE 12 CONTEXT FREE GRAMMAR AND PUSHDOWN AUTOMIATIA ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccceccs 14 PUSHAD OWN AUTOMAA netuvercatvuewrccretoncdnasuelcnoanwiaaolswemreceutensduatensc cadet SA MSS as arene tanduet laws OR S esto e avise a aaa 14 GRAMMAR EE 15 CONVERT PUSHDOWN AUTOMATA TO GRAMMAR 550400 ee ss sa a AS EE ee Ee 15 RESTRICTION FREE LANGUAGES AND TURING MACHINE cccccccccccscccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccsccccecs 17 TURING IMIAGHIN EE 17 28 Introduction What is JFLAP JFLAP is a progra
32. m that makes it possible to create and simulate automata Learning about automata using pen and paper can be both difficult and time consuming With JFLAP on the other hand you can create automata of a variety of different types and it s easy to change your creation whenever you want JFLAP supports creation of DFA and NFA PDA Turing Machines Grammar Regular Expressions and more Setup JFLAP is available from the homepage www JFLAP org From there press Get FLAP and follow the instructions You will notice that JFLAP have a JAR extension This means that you need Java to run JFLAP With Java correctly installed you can simply select the program to run it You can also use a command console run it from the files current directory with Java jar JFLAP jar Using JFLAP When you first start JFLAP you will see a small menu with a selection of eleven different automata and rule sets Choosing one of them will open the editor where you create chosen type of automata Usually you can create automata containing states and transitions but there is also creation of Grammar and Regular Expression which is made with a text editor Additional Resources Recommended Reading JFLAP An Interactive Formal Languages and Automata Package Rodger Finley ISBN 0763738344 JFLAP assignments for JFLAP An Interactive Formal Languages and Automata Package http www cs duke edu csed jflap jflapbook files Getting Started With JFLAP Colorado Stat
33. not get tested in detail Further inspection will be made if they are useful in any other way by discussing above categories After the review the best suitable simulator will be presented and discussion about how these programs are used either in assignments or the manual is also presented 2 4 The Manual To make studenis more comfortable with our preferred simulator a manual is made This manual explains most of the simulators features and how to use them correctly The manual is very straightforward and easy to pick up if the user should be stuck at any point 2 5 The assignments The assignments based on the preferred simulator program are prepared It is presupposed that the students should be familiar with the basics of formal languages and automata theory These assignments should be enough to get the students a kick start in learning how to use the simulator and be more comfortable in creating different tyoes of automata 3 REVIEW RESULTS 3 1 Simulator Reviews and conclusions Simulator Automata Editor Home Page http automataeditor sourceforge net Current Version v 2 0 Description Automata Editor is an automata editor that utilizes a format called VauCanSon G which is a LaTeX package 5 Features e Create and edit DFA and NFA e Determination and Minimization Review Automata Editor always starts in the editor with no distinction for if either DFA or NFA is used Here you can add states and transitions from th
34. nput characters from the alphabet Every item in the workspace can be changed by right clicking them Initial states are blue and final states are green e I jFAST save SB z Figure 11 JFAST with the language a a You test your automata with the Run button at the right It starts the simulator mode in a full screen overlay unfortunately that mode made the program unresponsive using Windows 7 I tried creating my first automaton ran into several problems Transitions kept disappearing and the automata did not accept my input without explanation The transitions also curve too much they often end up in a mess E jFAST save Lea ZS Figure 12 JFAST with Turing machine that duplicates numbers Since there where so many problems it is hard to do larger projects using JFAST Creating PDA and Turing machines were also harder to do than simple FA 19 Conclusion JFAST Functionality No minimization or determination or automata conversion functions are implemented in JFAST Tools The debugging part crashed for me for some reason which made it hard to test debugging properly User Friendliness JFAST could be good if it did not have all these bugs Transitions disappeared and reappeared at random You must have a start and end state and specify your alphabet to run anything or else a warning message is shown To set the alphabet you need to add each letter separately which I didn t realize t
35. nt and click every state and drag transitions between them Names are added automatically each state Same with PDAs which are created just like FAs Turing machines do use the same interface and look It is easy for beginners to just create an automaton with minor knowledge Some features require some modifications on your automata to work properly which is often noted on the home page For example PDA to Grammar conversion requires the PDA to follow specific rules before it will work Design JFLAP is well structured and have a simplistic layout Creating states and transitions are simple and Straightforward The start menu separates all the different types of automata and languages and selecting one of them gets you to the editor screen which is mostly the same with minor differences The debugging could need some moving animations which it is not available in JFLAP Documentation The JFLAP home page has a very well written guide which is very helpful if you get stuck Compatibility To use JFLAP JavaSE1 4 is needed It is easy to run the jar file that contains the program on any platform that uses Java JFLAP is the best known automata simulators out there and it covers most of the needed material found in an automata course 23 Simulator PetC Home Page hitp people dsv su se henrikbe petc Current Version Version 0 11 Description This is a FSA simulator by Henrik Bergstrom a teacher at the University of Stockholm 9 Featur
36. ol you can use the table to inspect combined transitions from that state The state is removed with The Finalize button 11 L JFLAP lt untitled1 gt File Input Test View Convert Help x Convert FA to RE Remove States Use the collapse state tool to remove nonfinal noninitial states 2 more removals needed KI a 8 Dot Export san BIO Ole WO blo Finalize r Automaton Size When all the necessary steps are made the converted automata contain the regular expression You can also see the complete regular expression above the toolbar which can be exported using Export File Input Test View Convert Help Editor Convert FA to RE ye Generalized Transition Graph Finished 01 000 1 000 1 01 0 Molla 4 Don export 01 000 1 000 1 01 r Automaton Size JFLAP is capable to convert the regular expression to a NFA again If the original automata is a DFA the result might differ because JFLAP add a lot of lambda transitions You might need to convert further to a minimized DFA to get your automata back Convert FA to Grammar When using a Finite Automaton select Convert Convert to Grammar The conversion view will contain your automata on the left and the grammar on the right You are free to edit the grammar yourself or let JFLAP more or less do the work 12 The What s Left option will s
37. omata Editor handles NFA just as well as DFA But do note that Automata Simulator do not tell DFA and NFA apart in any way 14 Conclusion Automata Editor by Max99x Functionality The application can convert regular expressions to automata It lacks a proper editor window to graphically manipulate your automata Determination and Minimization algorithms are available Tools It is possible to debug strings one at a time Lack of any step by state feature makes debugging harder You either get an Accepted or Rejected message after the input string have been used User Friendliness By creating automata you have to specify every state with transitions in a list of states and transitions which takes time and is easy to lose track Though when the work is done the automata is rendered nicely and transitions are separated so they do not overlap each other Using regular expressions to generate finite automata is much more efficient but the user must know how to create regular expressions that are accepted by the program Design The layout is simple and easy to understand but do not help user who is unfamiliar with automata Documentation The documentation is slim The application comes with example automata that the user can look at There are no instructions on how to construct regular expressions Compatibility Automata Editor uses Python and the GraphViz library was not successful in running from source code bu
38. ore than one transition with the same input value Lambda transitions can also be used which enables the automaton to move from one state to another without consuming any input PDA Pushdown Automaton is an automaton that has a stack where the push and pop function is used Because of this some iterative patterns can be evaluated For example As A A gt Which accepts L 0 TM Turing Machine is a more complex automaton that has a tape that can be read and written to The head points at the beginning of the string when the TM executes Every transition has three variables which are read write and the direction CONTENTS TI INTRO DUC TION WEE 6 OU BACKOR OMID EE 6 OBJECTIVE EEN 6 13 PROBLEM EIERE 6 RTI TT OI E 6 2 METHODS BEE 7 2 PREVIOUS VV OR E 7 SECHER 8 253 REVIEWOF TEE uge 8 SE a TEE VA NI EE 9 SREL EE 9 3 REVIEW RESULT Serii EAE d Dea nen ser emai sapides addi iewaaaes anaieaesienah e RU Saca ads das Lan 10 3 1 SIMULATOR REVIEWS AND CONCLUSIONS sosseseerersrsssssrsrsrrrreerrrsrrrrrrrrrrrrr rss rr r Ross R RR RRD RDR RR RR RR KRK rare raras esse Rss sa 10 STOOP Au omota EEN 10 Conclusion Automata ECItOr sersserserrerrerrerrerrerrrer rer neon eo rer Ro Rs RR RR RAR KROK KKR KKR RKS R RSKR RR RRD BKK SR KR DKK RR RR KR son 12 Simuldtor Automata Editor Dy MOXIIK EE 13 Conclusion Automata Editor by MOX99X cccssccsesecnscecssccaseccensccessccescccsseceusesessceassceuseseusens
39. ou can break down the Regular Expression into smaller parts Each transition will contain a sub expression The next step is to link every rule with lambda transitions Add new transition between states that should be connected with the Transition Tool If you are unsure what to do you can select Do Step to automatically make the next step If you want the NFA immediately Do All creates the whole NFA for you File Convert Help Editor Convert RE to NFA Welcome to the converter 1 more resolutions needed amp 27 388 Do Step Do All Export ay 4 Automaton Size 10 You can notice how the conversion differs depending on how the Regular Expression looks For example the expression a b results in a fork were either a or b can be chosen File Convert Help Convert RE to NFA The automaton is complete Export will put it in a new window _ k gt Do Step Do All s Reform Transitions Put empty transitions between states with no transitions 17 more empty transitions needed KI a doit Export Automaton Size Follow the instructions above the toolbar To make the conversion work empty transitions must be added between states that have yet no transition States that either is Initial or Final must be removed which you do with the collapse state tool With the collapse to
40. rograms including JFLAP to see which one that met all our requirements Every simulator was tested with a set of test cases and discussions were made about if the tested automata simulator met given requirements The manual and assignments are created for JFLAP which is found to be the best simulator to be used in the FABER course at MDH PREFACE This report is a B Sc thesis work in computer science It was written at the School of Innovation Design and Engineering IDT at M lardalen University V ster s 2013 Tobias Fransson NOMENCLATURE Alphabet a set of symbols Example a b or 0 1 String a sequence set over an alphabet Example aabbabb Languages is a set of strings Example L a b n gt 0 Grammar a set of rules that formulate strings in a language Example a grammar over the alphabet a b S gt asb SSA Specifies the language L A ab aabb aaabbb a b n gt 0 FA Finite Automaton is a model of computation that consists of a finite number of states and transitions between those states It reads an input string and after number of state transitions either accepts or rejects the string DFA Deterministic finite automaton is a finite state machine that produces a unique computation for each input string From each state on a given input symbol the automaton may proceed into one possible next state NFA Nondeterministic finite automaton each state can have m
41. sessesssesenensenenss 15 Simulator Automaton SimulatOl EE 16 Conciusion Autom ton SINUGO EE 17 Kiefer H EE 18 Weeer ETC EE 20 SOF EEN 21 Conclusion JFLAP E 23 EE EE 24 Conciuson EE 25 Simulator Tuatara Turing Machine UV de TEEN 26 Conclusion Tuatara Turing Machine Simulator EEN 27 Simulator Turno EE ee 28 Conclusion Turing Machine REENEN 29 Simulator Visual Automata Simulator seeerseersserrerrerreererrerr ror rsr renen rr rs Ro RR RR RKA KR RR RR RDR RRD RRD RR RR KKR a 30 Conclusion Visual Automata lee 32 Sd SIMULATOR ANALYSIS DISCUSSION EE 33 4 CONCLUSIONS ON THE CHOICE OF SIMULATOR ccccecccececcccccccccccccscccccccsccccccccccccccccccccccecccecscccscecececes 34 5 FUTURE WORK eet 35 BRE ERE ICE Siac ere 35 TPP PE NICE EEN 37 Kn E a Te Gat DEE 37 JAPP END Th e E 37 8 MANUAL AND EXERCISES tege enee eege EENEG 38 8 1 APPENDIX 1 MANUAL FOR JFLAP SIMULATOR USE IN THE FORMAL LANGUAGES AUTOMATA AND THEORY OF COMPUTATION COURSE EE 8 2 APPENDIX 2 ASSIGNMENTS cssssccsencvccccssscvescusncscensncnensuvnvacanansncssssnscunsnensnensnsacanvorssaususcceusnsveseununessnsnsncacananens 1 INTRODUCTION 1 1 Background Learning about formal languages automata and theory of computation often involves long and tedious constructions of automata grammars derivations of strings and test running of automata that all are error prone At M lardalen University the Formal languages Automata and Theory of Computa
42. shows useful messages about the program Turing machines are created using the programming box Every line uses the following this structure state character new state new character direction State 1 Start Stop Resume Step Speed Slow lt DOOU Load new program Subtracter v Machine name Subtracter Initial tape position 1 gt 0 Initial characters on tape 111111 1111 Programming Clear Program Install Program EA a Entering program Machine programmed successfully Program description Subtracts numbers in unary Input format lt num lt num gt pee 0 GON IND ck oe ink ae DH DH ES Clear Message Box Figure 19 Turing Machine Simulator Creating Turing machines with Turing Machine Simulator from scratch is more complicated than using a graphical editor 28 Conclusion Turing Machine Simulator Functionality The user can create Turing machines using a line by line programming box Tools When running programs the tape is animated well and it is easy to see where on the tape you are You can easily move around with two arrows on the sides of the tape Obviously you do not have a view of how the Turing machine looks like User Friendliness You need to know how to program a Turing machine in Turing Machine Simulator which is time consuming There are a couple of premade Turing machines to study by loading them and press start to see the TM running with the characters on the
43. t proper instructions it is too time consuming 12 Simulator Automata Editor by Max99x Home Page http max99x com school automata editor Current Version 1 0 Description Automata Editor is a simulator created in the language Python It is created by a former student as a project in a Theory of Computation course 8 Features e Create and edit DFA and NFA e Convert NFA DFA e Convert RE NFA e Determination and Minimization This editor does not have a proper graphical interface like JFLAP which means that you have to programmatically insert every item into your automaton Review With Automata Editor you do not get a graphical interface to drag and drop states around You have to specify each item trough adding them or create a regular expression After a proper automaton is specified Automata Editor should then render your automata in a separate Preview window Add and remove symbols means which characters the automata should use The Add and Remove Siate handles states where you can set the initial and final states in the Set Initial and Set Finals buttons The Add and Remove Delta handles the transitions Except for the Preview window the current automaton is represented in a list in the main window Ai trata Ett r Symbols a b Add Symbol Remove Symbol States ql s9 lt 3 c11 c7 s9 gt 6 Add State Remove State Initial ql Finals cll Set Initial Set Finals Delta Add Delta R
44. t there is a Windows binary available which worked well Without a proper editor students may have trouble understanding how this program works 15 Simulator Automaton Simulator Home Page http ozark hendrix edu burch proj autosim Current Version 1 2 Description Automaton Simulator is a simple and open source automata simulator It is created by Dr Carl Burch at Hendrix University 6 Features e Create and edit DFA NFA PDA and Turing machines Review 8 4 Automaton Simulator Lor El amp File Help ww A gt DFA simple test Figure 7 Automata Simulator with the language a a Automaton Simulator directly puts you in the editor window with DFA currently used Here you can edit your automata easily by selecting either the state or transition button and simply add them to the workspace using the mouse When pressing the run button you can write your input in the tape below to automatically move one state The active state is green and an animated dot run through the transitions while jumping states Creating DFA NFA PDA or Turing machines is fast and simple Edit different types of automata might differ some like debugging a Turing machine because you need to edit the tape before you start debugging The application might be little to simple and gives no features whatsoever One important feature missing is a better set of alphabet only a and b seems to be available 16
45. ta type you get the editor page with a toolbar and a workspace to create your automaia J e Se r SE D E S JFLAP 7 0 ol a es L amp JFLAP DFA simple testjf 9 Ga See ue File Input Test View Convert Hel File Help Batch Preferences eens Editor Finite Automaton Mealy Machine Moore Machine Pushdown Automaton Turing Machine Multi Tape Turing Machine L System Regular Expression 4 Regular Pumping Lemma Automaton Size Context Free Pumping Lemma Figure 13 Selection menu and editor view By selecting the state button you can create new states The names on the states are created automatically and by right clicking you can set if initial and final Next to the state tool is the ability to create transitions Transitions can be dragged from one state to the next state or looped 21 By pressing the scroll button on your mouse you can also curve the transitions to make your automata look better By using any options under input you can test run your automata There are four options Test the input with Closure Step by State Fast Run and Multiple Run The Multiple run option lets you test multiple inputs with either a reject or an accepted result S JFLAP DFA simple test File Input Test View Convert Help Editor Multiple Run Input Accept Accept Accept Reject Reject Reje
46. tate machines Requirement was for the simulator to have at least some sort of graphical user interface 2 METHOD S 2 1 Previous Work Similar tests have been done in an earlier exam report was written in 2006 when a simulator called A5 was used in the FABER course at MDH The review came to the conclusion that JFLAP was much better suited for use in the course assignments The question was if some new simulators appeared in the meantime that could be used in the course The creators of the JFLAP simulator are Professor Susan H Rodger of Duke University together with her students JFLAP is the most successful simulator worldwide with over 25 000 downloads since 2003 14 Simulators like JFLAP can be called a multipurpose automata simulator because of the variety of automata they can handle While there are other simulators specified for one or several types of automata it could be a good idea to consider using more than one simulator during a course according to 17 Currently the Activities CD ROM for JFLAP is available from the Linz book 12 that contains several assignments with JFLAP files included The assignments are easy to begin with and get more in depth later on There is a course called Introduction to Formal Languages and Automata at Mississippi State University that have homework using both traditional methods and JFLAP 10 These assignments are taken from the Linz book which is the same as the book used in the FABER course
47. tion course FABER has been using a simulator called JFLAP 4 for the course exercises Using this automata simulator program helps students with experimenting with automata and grammars and getting a better idea about how they work It is also much easier to control and compare solutions 1 2 Objective The objective of the present work is to test a collection of automata simulators that is available on the internet Every simulator should be able to simulate all or some of Finite Automata Pushdown Automata and or Turing machines The program should be easy to use and have documentation well enough for anyone familiar with automata theory The related objective is to create assignments for the course that uses JFLAP or a preferred simulator Also a manual for the preferred simulator should be created that the students can use during the course 1 3 Problem formulation There are many applications found on the internet that can simulate automata but are they any better than the currently used JFLAP Which of these are better suited in laboratory assignments with automata How to create good laboratory assignments by using JFLAP for use in a Formal Languages Automata and Theory of Computation course 1 4 Limitations This report presents the results of the tests of simulators that handle either one or more of DFA NFA PDA and or Turing machine types of automata Tests have not been done with any frameworks or libraries that handle automata or s
48. tion is very simple and debugging is very easy to use which is useful for most assignments 17 Simulator JFAST Home Page http sourceforge net projects jfast fsm sim Current Version 1 3 Description The simulator is written by Timothy M White that first made this simulator as his B S in computer science at Villanova University By that time it only did handle DFA but White has been developing the program since then and now the application has more features 2 Features e Supports DFA NFA PDA TM and State Machines e Save image to PNG or JPEG Review You get straight to the editor window once the program starts By using new in the file menu you can select the automata type you prefer O Create A New Automaton Choose Automaton Type NFA Pushdown Automaton Turing Machine State Machine Cancel Figure 9 The selection menu in JFAST You have to specify the alphabet before you create and run your automata The button Set input Alphabet specifies the alphabet You press any letter and select the plus button which adds that letter to the alphabet set used in the current automaton Set Alphabet _ 2s J O Set Automaton Alphabet Alphabet Elements New Symbol Accept Figure 10 Alphabet setup in JFAST 18 The state and transition buttons in the upper toolbox creates states and transitions When creating a transition an options menu shows up to let the user set i
49. u find in most simulators You can have many Turing machines in the same window and with one tape for each instance Documentation There is little information about the program on the home webpage but do not come with any manual Compatibility Tuatara comes in plain Java source code that you have to compile only got it working well using NetBeans 7 0 1 using Windows 7 after a while Getting started with the source code could be troublesome for some Using this simulator with Turing machines related assignments would work but they don t follow the same rules as found in the course book or the lectures 27 Simulator Turing Machine Simulator Home Page http ironphoenix org tril tm Current Version 1 0 Description A web based simulator for Turing machines It is created by Suzanne Britton which has the applet on her own website 3 Features As the name says it does Turing machines where you program your own Turing machine The user can step and pause during the execution of the active program and the tape is updated every step Programs can be saved and loaded into the simulator Review Load New Program loads a created program which is the Turing machine see Figure 19 The box under Programming is the currently loaded program which can be run by pressing Start in the top corner The speed of the execution and Stepping can be set with the buttons at the top of the window The red box is the tape The console right below
50. uring machine uses a tape that can be written and removed to by the head For every transition there are three variables to set First one is what value is expected to be under the head Second is if the first is correct what should be written under the head Third and last is the direction the head should take the head can go left L right R or stay S In JFLAP is the blank symbol Create this Turing machine below which duplicates the number of ones on the tape mem i Lin Slay File Input Test View Convert Help Automaton Size when testing your Turing machine you can see the tape Stepping trough updates the currently active state alongside the tape s content In this example the tape starts with the string 1111 where the TM steps trough and changes each 1 to an x To Know how many extra 1 to write x will act as a symbol for each extra 1 to be written The TM stops once the computation is done the tape should contain the result with the head in its starting position 4 JFLAP TMtestjff File Input Test View Convert Help tor Simulate 1111 step Reset Focus Defocus Freeze Thaw Trace Remove 17 8 2 Appendix 2 Assignments JFLAP EXERCISES A few words of introduction about JFLAP JFLAP is an automata simulator that supports DFA NFA PDA Turing machines and more JFLAP also supports Regular Expressions and Grammar which can b
51. y Montana Tech of the University of Montana S Reading J Lim S H Rodger ncreasing Interaction and Support in the Formal Languages and Automata Theory Course Computer Science Department Duke University 35 15 R Reis N Moreira A Almeida GUltar and FAgoo Graphical interface for automata visualization editing and interaction DCC FC amp LIACC Universidade do Porto 16 GRAPHVIZ open source graph visualization software htto www graphviz org 4 1 13 17 W Yurcik M L Cobo C I Chesnevar Using Theoretical Computer Simulators for Formal Languages and Automata Theory Department of C S and Engineering Univ Nacional del Sur 36 7 APPENDICES The following appendices are found in section 8 MANUAL AND EXERCISES is explained in this section 7 1 Appendix 1 Even though JFLAP is provided with a manual we produced a condensed version of the manual suitable for classroom use Explaining all features would make the guide too long which is unnecessary For example features like the Mealy and Moore machines will not be discussed A student that have done work with FA and also have read this guide should not have any problems using other features of JFLAP as well 7 2 Appendix 2 The assignments are based on the use of JFLAP Assignments introduce the student to JFLAP and its features by creating different types of automata Assignment 1 The first assignment goes through FA with DFA and NFA Grammar and Regu
52. y for yourself Assignment 1 5 a Use this Regular Language to make a Nondeterministic Finite Automata a b c L aawbbwcc w a b c w is even After the NFA is made find the Grammar for this NFA b Now create a new FA NFA or DFA with this language x a b L ab a ba What is the minimal DFA for this language Save both the automaton and grammar Languages should be saved as a Word document 24 Assignment 2 JFLAP EXERCISES ON CONTEXT FREE LANGUAGES AND PUSHDOWN AUTOMATA Assignment 2 1 Pushdown Automaton PDA is an automaton that also handles a stack Unlike regular Finite Automata PDA s have a Pop and a Push symbol which handles the stack during execution RIO a st ei I en Ou Ka TS a FI Create a PDA that accepts strings that contains the language L a cb where x gt 0 using the alphabet gt a b c Assignment 2 2 Create each PDA with at least five test results with the following languages over alphabet a b a Create the PDA from the Figure b L a b where n gt 0 c L a b c where n gt 0 d L W cW2 Wi W gt es a b where W Wo3 25 Assignment 2 3 Consider the following Pushdown Automaton a What language does this PDA accept b Extend this automata to accept simple expressions like 1 0 1 That is expressions with 1 and 0 and the operator Assignment 2 4 Construct PDA that accepts the following
53. y automatically get a name assigned to them which can be changed using the Attribute Editor Tool Transitions are easily dragged between states with the mouse using the Transition Creator Tool Automaton Size This automaton only accepts strings containing b but end with a To test this automaton you can use any of the available tools under the Input menu The fastest in this case is to use Input gt Fast Run A menu where you can set your input string pops up Type the string bba and select OK The program shows all the transitions that are done when consuming the input string pn If you want to test multiple inputs at once you can select the Multiple Run option If you wish to individually review single runs can be accessed by selecting the View Trace which gives a view similar to the Fast Run option Ir Table Text Size Accept Input Result Accept Accept Accept Reject Reject Reject Reject Reject A Load Inputs Run inputs Clear Enter Lambda View Trace To debug the automata itself Step by Closure or Step by State can be selected For each step the automata highlights the currently active state By stepping you press the Step button Editor The first character consumed Notice that the first letter is grayed out and the currently active state have changed 2 JFLAP m
54. y to create in JFLAP Automata Editor Automaton Simulator and Visual Automata Simulator work well to edit automata Simulators like JFAST did not work well because of the number of bugs that where found during the tests see Table 4 and 5 bl e Tei kc lad a friendliness gee Editor ester pere Max eel ee FP Sim Grade from 1 to 5 where 1 is the worst and 5 is the best JFAST 3 1 M JFLAP E fa E Table 4 Grades for each simulator JFLAP is still in development with a new version coming soon with more improvemenis There is a higher possibility that improvements will be released more regularly JFLAP have better documentation which most programs lacks Important is that JFLAP is very simple and users can use the software with ease just by using it 33 ier PPP ar ao Tests partially successful Auto Ed by E 7 Max ests unsuccesstu Sim Pec ls 3 jo s msm JE Mo il Table 5 Test cases for each automaia type JFLAP do have all the best perks and is the best all round choice in comparison of the other simulators There is no reason to pick any other program because they have not enough documentation or features Using JFLAP for all the course work will be both more efficient and helping students than slowing them down by roughly implemented software 4 CONCLUSIONS ON THE CHOICE OF SIMULATOR JFLAP is the definitive choice when choosing automata simulators in a desktop environment Other candidates either have
Download Pdf Manuals
Related Search