Two Tape Automata
Supervisor: Michael Hoffmann (mh55)
Prerequisites
This project requires familiarity with the module CO2011 and also knowledge of programming (as may be found in CO1003 and CO1004, or in equivalent modules).
Aims of Project
Finite state automata were introduced in the module CO2011. A two tape finite state automaton can read two taped either synchronously or asynchronously. In the project we will focus on the former one.
There are several interesting operation on these automata. For example converting a two tape automaton to a normal finite state automaton by restricting the 2nd tape. These operation are important in designing algorithm in recent research projects.
The idea of this project would be to build a tool that would simulate operation on two tape automata. Analysing which data structure for two tape automata would give which complexity bounds for the above operations.
Challenges presented by the project
The challenges of this project can be found in the following areas
- Handling of data in different formats and their conversion
- Understanding and implementing of advanced operation involving two tape automata
- Implementation and visualisation of efficient algorithms
Learning Outcomes
The student will:
- Learn some advanced material (such as the method of combining 2 two tape automata to one.).
- Construct a tool for representing two tape automata and operations on them.
- Design a tool for simulating the action of a two tape automaton.
- Combine these tools into a general purpose tool for two tape automata.
Nature of End-Product
A tool allowing to create two tape automata and perform operations on them.
Project Timetable
Semester One
Review finite state automata. Research some further material on two tape automata and related subjects. Specify the tools to be implemented. Decide on the data structure. Prototyping simple displays of automata.
Semester Two
Design, implement and test the system. Analysis the findings (decidability/complexity). Improve the algorithm.
References
J E Hopcroft and J E Ullman.
Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).
