SCRS Conference Proceedings on Intelligent Systems
Algorithm Design for Deterministic Finite Automata for a Given Regular Language with Prefix Strings
Authors: Rashandeep Singh and Gulshan Goyal
Publishing Date: 11-10-2021
ISBN: 978-93-91842-08-6
Abstract
The field of automata theory is one of the most important areas in the field of Computer Science and Engineering that deals with how efficiently a problem can be solved on a model of computation using an algorithm. There exists a variety of formal languages like regular, context free, context sensitive, etc. These formal languages are described as set of specific strings over a given alphabet and can be described using state or transition diagrams. The state/transition diagram for regular languages is called a finite automaton which is used in the lexical analysis phase of compiler design for recognition of tokens. The construction of finite automata is a complicated and challenging process as there is no fixed mathematical approach that exists for designing of DFA and handling the validations for acceptance or rejection of strings. Consequently, it is difficult to represent the DFA’s transition table and graph. The present paper proposes an algorithm for designing of deterministic finite automata (DFA) for a regular language with a given prefix. The proposed method further aims to simplify the lexical analysis process of compiler design.
Keywords
Automata; Deterministic Finite Automata; Formal language; Prefix strings; Regular language
Cite as
Rashandeep Singh and Gulshan Goyal, "Algorithm Design for Deterministic Finite Automata for a Given Regular Language with Prefix Strings", In: Raju Pal and Praveen Kumar Shukla (eds), SCRS Conference Proceedings on Intelligent Systems, SCRS, India, 2021, pp. 133-142. https://doi.org/10.52458/978-93-91842-08-6-11