Abstract A Collection of Tools for Making Automata Theory and Formal Languages Come Alive.pdf

A Collection of Tools for Making Automata Theory and Formal Languages Come Alive Anna O. Bilska, Kenneth H. Leider, Magdalena Procopiuc, Octavian Procopiuc, Susan H. Rodger, Jason R. Salemme and Edwin Tsang Duke University, Durham, NC rodger@ Abstract We present a collection of new and enhanced tools for exper- imenting with concepts in formal languages and automata theory. New tools, written in Java, include JFLAP for cre- ating and simulating finite automata, pushdown automata and Turing machines; Pa?te? for parsing restricted and unre- stricted grammars and transforming context-free grammars to Chomsky Normal Form; and PumpLemma for proving specific languages are not regular. Enhancements to previ- ous tools LLparse and LRparse, instructional tools for pars- ing LL(1) and LR(1) grammars, include parsing LL(2) gram- mars, displaying parse trees, and parsing any context-free grammar with conflict resolution. 1 Introduction The majority of computer science courses have a hands-on approach, since they have a natural programming compo- nent. In the introductory courses, students learn a program- ming language and write programs to experiment with the language. In many later courses, students work on program- ming projects related to the topic, such as writing compo- nents of an operating system, or using libraries to solve sci- entific computing problems. Theoretical computer science courses, algorithms and formal languages, are an exception, traditionally taught with no programming assignments, but rather students write homework assignments using pencil and paper and do not receive feedback until the assignments are graded. With the development of algorithm animation tools such as AACE [5], Xtango [11], and Zeus [4], algorithms courses are demonstrating animations of algorithms and data struc- tures during lectures [8], which the students can recreate out- side of lectures. For example, inserting elements into a red- black tree and watching the changes (rotations) to