Conversion of Regular Expression in To Finite Automata
Journal Title: International Journal of Scientific Research and Management - Year 2015, Vol 3, Issue 5
Abstract
Regular expressions are used to represent certain set of string in algebraic manner . This paper describes a method for constructing a minima deterministic finite automaton (DFA) from a regular expression. It is based on a set of graph grammar rules for combining many graphs (DFA) to obtain another desired graph (DFA). The graph grammar rules are presented in the form of a par sing algorithm that converts a regular expression R into a minimal deterministic finite automaton M such that th e language accepted by DFA M is same as the language described by regular expression R. The proposed algorithm removes the dependency over the neces sity of lengthy chain of conversion, that is, regular expression → NFA with ε - transitions → NFA without ε - t ransitions → DFA → minimal DFA. Therefore the main advantage of our minimal DFA construction algorithm is its minimal intermediate memory requirements a nd hence, the reduced time complexity. The proposed algorithm converts a regular expression of size n in to its minimal equivalent DFA in O(n.log2n) time. In addition to the above, the time complexity is further shortened to O (n.logen) for n ≥ 75.
Authors and Affiliations
Neha, Abhishek Sharma
Keywords
Related Articles
- EP ID EP216723
- DOI -
- Views 66
- Downloads 0
The Bring Into Operation for Airborne /Airship Ad Hoc Network (AAHNET)
Airborne/Airship Ad Hoc Ne twork works as plane node where the self organizing networks are defined as. Ad - Hoc Network just two basic nodes can be made anywhere and with any need that dynamic network infra...
An Empirical Analysis of the Effect of Deregulation of Money Market Operations on the Performance of the Nigerian Economy
Financial markets are vital components of the financial system of any nation. The importance of these markets in any modern economy is enormous. It is in the ligh t of the importance placed on money market operations tha...
Use of nanotechnology for clean and safer future environment
Nanotechnology is the most promising technology in modern science. This technology deals with the study and practical applications of different materials of nano - scale dimension. The chemical reactivity of a material i...
Effectiveness of laser therapy over topical desensitising agents in the treatment of dentinal hypersensitivity - A systematic review
AIM: To analyze the available scientific evidence on the effectiveness of laser therapy compared to the topical desensitizing agents in the treatment of dentinal hypersensitivity. Materials and methods : A broad literatu...
Communication A Tool To Build Relationship Quality: Evidence From Indian Retail Banks
The purpose of this paper is to study the effect of communication on relationship quality dimensions such as trust and commitment in retail banks. Data were gathered from the retail bank customers in Che...