View Proposal

---

Proposer

Radu Mardare

Title

Teaching tool for studying Finite Automata and Regular Languages

Goal

Develop a teaching tool for Finite Automata and Regular Languages that integrate visual support and encode various dedicated algorithms

Description

Finite automata (FA), in the form of deterministic finite automata (DFA) and non-deterministic finite automata (NFA), are a class of fundamental computational devices that recognize Regular Languages. They are intensively used in the practise of computer science, and they have been studied repeatedly in our courses. The aim of this project is to produce a teaching app that can help the students studying and manipulating FAs. The app should propose an appropriate interface where the students can design and work with FAs. There are many possible operations on FAs that can be automatized, such as: - The graphical construction of a DFA or NFA and its mathematical specification - Given a DFA or NFA, the simulation of computations on particular inputs - The determinization of a NFA - Computing operations with FA – Union, Concatenation, Star, Intersection, Complement - Computing the regular expression that characterizes the language recognized by a FA - Construct a FA that recognizes a given regular expression - Construct a FA for the reversal of the language recognised by a given FA - Minimizing a DFA

Resources

Background

Basic knowledge of Automata Theory as presented, for instance in M.Sipser "Introduction to Automata Theory"

Url

Difficulty Level

Moderate

Ethical Approval

None

Number Of Students

3

Supervisor

Radu Mardare

Keywords

finite state automata, regular languages, models of computation

Degrees

Master of Engineering in Software Engineering
Master of Design in Games Design and Development
Master of Science in Computing (2 Years)
Master of Science in Information Technology (Software Systems)
Master of Science in Software Engineering