[PDF] [PDF] Simulators for formal languages, automata and theory of

[PDF] LABORATORY MANUAL

LIST OF EXPERIMENTS Expt No Title of experiment Corresponding CO 1 About JFLAP C 219 1 2 Deterministic Finite Automata (DFA) C 219 1 3

[PDF] FIFTH SEMESTER CSE 2015-16 Theory of Computation

Introduction to Formal Languages, Automata Theory and Computation: K Experiment No 11: Experiments on simple fundamental units like half adder, full 

[PDF] Laboratory Manual of For - Jawaharlal Nehru Engineering College

Program to convert Non-deterministic finite automaton (NFA) to Deterministic Strictly observe the instructions given by the teacher/Lab Instructor Instruction for  

[PDF] Automata Theory _4th Sem_ - VSSUT

of a Deterministic Finite Automata, How a DFA Processes Strings, Simpler one of the most practical models of computation, since there is a trivia A finite table ( occasionally called an action table or transition function) of instructions

[PDF] Automata Theory and Applications - UT Austin Computer Science

Stochastic Finite Automata: Markov Models and HMMs * Programs to do that also rely on the theory of context-free languages that we present in Part III Of course, practical string search engines need to be small and deterministic

[PDF] Simulators for formal languages, automata and theory of

were made with nine programs that are able to graphically simulate automata and formal JFLAP is also the most popular simulator in automata theory courses worldwide Which of these are better suited in laboratory assignments with

[PDF] Introduction To Theory Of Computation Lab Manual

1 oct 2014 · Introduction to the theory of computation third edition - Michael Sipser Lucas Neves Download PDF Download Full PDF Package This paper A 

[PDF] Chapter 3 Automata Theory

as the concept of computation which lies at the heart of automata theory On the other hand eral practical techniques and applications, such as taking advantages of compiler compilers a text or executes the instructions of a source code

[PDF] theory of computation pdf

[PDF] theory of quadratic equation

[PDF] theory of semiotics ferdinand de saussure pdf

[PDF] therapeutic drug monitoring pdf

[PDF] therapeutic drug monitoring ppt

[PDF] therapeutic drug monitoring principles

[PDF] therapeutic drug monitoring review

[PDF] thermal model of a house

[PDF] thermostat simulink

[PDF] thesis about british and american english

[PDF] thesis on android application development

[PDF] thesis outline example

[PDF] thirty years war essay question

[PDF] thirty years war essay thesis

[PDF] thirty years war political causes

Simulators for formal languages, automata and

theory of computation with focus on JFLAP

Tobias Fransson

tfn09001@student.mdh.se

Handledare och examinator: Gordana Dodig-Crnkovic

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 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 programs 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

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 = {anbn; n>0}

Grammar a set of rules that formulate strings in a language.

Example: a grammar over the alphabet {a,b}

S aSb

S Specifies the language: L = { Ȝ, ab , aabb , aaabbb , .. } = {anbn; n0} 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 more 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:

A (A)

A ()

Which accepts L = {(), (()), ((())), ..}.

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

1. INTRODUCTION .............................................................................................................................................. 6

1.1 BACKGROUND ............................................................................................................................................... 6

1.2 OBJECTIVE ................................................................................................................................................... 6

1.3 PROBLEM FORMULATION ................................................................................................................................. 6

1.4 LIMITATIONS ................................................................................................................................................. 6

2. METHOD(S) ..................................................................................................................................................... 7

2.1 PREVIOUS WORK ........................................................................................................................................... 7

2.2 COLLECTION OF SIMULATORS ............................................................................................................................ 8

2.3 REVIEW OF SIMULATORS ................................................................................................................................. 8

2.4 THE MANUAL ............................................................................................................................................... 9

2.5 THE ASSIGNMENTS ......................................................................................................................................... 9

3. REVIEW RESULTS........................................................................................................................................... 10

3.1 SIMULATOR REVIEWS AND CONCLUSIONS .......................................................................................................... 10

Simulator: Automata Editor ..................................................................................................................... 10

Conclusion: Automata Editor .................................................................................................................... 12

Simulator: Automata Editor by Max99x .................................................................................................... 13

Conclusion: Automata Editor by Max99x .................................................................................................. 15

Simulator: Automaton Simulator .............................................................................................................. 16

Conclusion: Automaton Simulator ............................................................................................................ 17

Simulator: JFAST ....................................................................................................................................... 18

Conclusion: JFAST ..................................................................................................................................... 20

Simulator: JFLAP ...................................................................................................................................... 21

Conclusion: JFLAP .................................................................................................................................... 23

Simulator: PetC ........................................................................................................................................ 24

Conclusion: PetC ...................................................................................................................................... 25

Simulator: Tuatara Turing Machine Simulator .......................................................................................... 26

Conclusion: Tuatara Turing Machine Simulator ........................................................................................ 27

Simulator: Turing Machine Simulator ....................................................................................................... 28

Conclusion: Turing Machine Simulator ..................................................................................................... 29

Simulator: Visual Automata Simulator ..................................................................................................... 30

Conclusion: Visual Automata Simulator ................................................................................................... 32

3.2 SIMULATOR ANALYSIS DISCUSSION ................................................................................................................... 33

4. CONCLUSIONS ON THE CHOICE OF SIMULATOR ........................................................................................... 34

5. FUTURE WORK ............................................................................................................................................. 35

6. REFERENCES.................................................................................................................................................. 35

7. APPENDICES ................................................................................................................................................. 37

7.1 APPENDIX 1 ............................................................................................................................................... 37

7.2 APPENDIX 2 ............................................................................................................................................... 37

8. MANUAL AND EXERCISES ............................................................................................................................. 38

8.1 APPENDIX 1. MANUAL FOR JFLAP SIMULATOR USE IN THE FORMAL LANGUAGES, AUTOMATA AND THEORY OF COMPUTATION

8.2 APPENDIX 2. ASSIGNMENTS ...............................................................................................................................

6

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

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 state machines. Requirement was for the simulator to have at least some sort of graphical user interface. 7

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. 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]. 8

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).

DFA 1. a*b

2. aWaaWa; W = {a,b}*

3. aa*(a+b)a

NFA 1. a+ab*a

2. (001*)|(010*)

3. aa(a+b)*ba

PDA 1. A = (A), A = (), A = e

2. S ĺĺaaA | a, B ĺ bBa | bb

3. S ĺĺĺ aaB|a

Turing

Machine

1. Duplicate the number of ones, Ex 1111 ĺ 1111 1111

2. L = {anbm}, n > m > 0

3. L = {anbncn}, n > 0

Table 1 Test cases 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

Determination and minimization algorithms are also considered. A grade five should be more than that.

9

Criteria Grade 1 Grade 2 Grade 3 Grade 4 Grade 5

Functionality No or few

functions available

Some functions

available

Most functions

available

All necessary

functions available

More than all

necessary functions available

Tools Hard to use

Debug features

not helpful

No output

Hard to use

Debug less

helpful Minor output

Some difficulties

to use

Partially helpful

Some output

Easy to use

Debug is

helpful

Detailed

output

Easy to use

Debug is very

helpful

Detailed output

User Friendly Not user

friendly

Less user

friendly

Partially user

friendly

User friendly Very user friendly

Layout Design Inconsistent

layout

Hard to

navigate

Poor graphical

quality

Inconsistent

layout

Insufficient

graphical quality

Consistent

layout

Average

graphical quality

Consistent

layout

Easy to

navigate Good graphical quality

Consistent layout

Easy to navigate

Best graphical

quality

Compatibility OS dependent,

Difficult to

begin with

Some cross

platform capability

Cross platform

Easy to begin on

at least one OS

Cross platform

Easy to start

s

Cross platform

Easy to begin on

any OS

Documentation No

documentation Minor documentation

Manual or guide

showing how the tool works

At least a

manual covering most issues

Complete

documentation and/or more

Table 2 Grading criteria

Simulators that prove difficult to use do 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 students 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 types of automata. 10

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

Create and edit DFA and NFA

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 the toolbar. Options like undo and save alongside with

graphical fidelity settings are available from the toolbar as well.

Figure 1 Automata Editor with NFA (001*)|(010*)

11

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 sets the state as an initial state. 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 which is very easy to understand.

Figure 3 Automata Editor with debug output

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 . 12

Conclusion: Automata Editor

Functionality

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 ZLWKODPEGDWUDQVLWLRQV,FDQQRWDGGODPEGDWUDQVLWLRQVDQGXVLQJquotesdbs_dbs17.pdfusesText_23