The Different Ways to Describe Regular Languages by Using Finite Automata and the Changing Algorithm Implementation

Authors: Abdulmajid Mukhtar Afat

Abstract:

This paper aims at introducing finite automata theory, the different ways to describe regular languages and create a program to implement the subset construction algorithms to convert nondeterministic finite automata (NFA) to deterministic finite automata (DFA). This program is written in c++ programming language. The program reads FA 5tuples from text file and then classifies it into either DFA or NFA. For DFA, the program will read the string w and decide whether it is acceptable or not. If accepted, the program will save the tracking path and point it out. On the other hand, when the automation is NFA, the program will change the Automation to DFA so that it is easy to track and it can decide whether the w exists in the regular language or not.

Keywords: Finite Automata, subset construction DFA, NFA.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1337495

References:

[1] Jhone E.Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to automata theory, languages and computation. By Addison- Wesley 2nd Edition, 2001.
[2] Tarek Majid. Theory of Cmputation. Amman- Jordan 1st Edition2005.
[3] S.P. Eugene Xavier. Theory of Automata, Formal Languages and Computation. By New Age International (P) Ltd, 2005.
[4] Finite Automata. Available at https://www.cs.rochester.edu/u/nelson/ courses/csc_173/fa/fa.html (Accessed Sep 2014).
[5] Formal language. Available at https://www.princeton.edu/~achaney/ tmve/wiki100k/docs/Formal_language.html (Accessed Sep 2014).