Jack Williamson Undergraduate Dissertation 2017/18

PDA To CFG Tool

Supervised by K.Bogdanov

Abstract

In automata theory, finite-state machines are a mathematical model of computation, which are comprised of one or more states and transitions between such states. They can be used in the modelling and analysis of systems, whether it is hardware or software. A Push-down automata is one such example of a finite state machine which makes use of a stack. A Context-free grammar is used to describe how to construct all possible strings in a given formal language. A Context-free grammar contains production rules which can be recursively substituted until a string is produced. In Automata theory, it can be proven that every Push-down automata has an equivalent Context-free grammar which defines it and the process of doing so appears in various automata and formal language literatures. The purpose of this software is to aid in the learning and visualisation of this process; the conversion of a Push-down automata into an equivalent Context-free grammar. This process entails the production of a drawing tool, allowing the user to create a Push-down automata. Then, the Pushdown automata must be altered to adhere to certain preprocessing requirements. From this altered Push-down automata, production rules can be produced to form a lengthy context-free grammar. Finally, this lengthy context-free grammar must be simplified to leave a concise context-free grammar which defines the language of the original Push-down automata the user created.