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 69
- Downloads 0
Rising NPAs and S tart U p India I nitiative : A P ossible V enture
The Indian banking sector has been facing serious problems of raising Non - Performing Assets (NPAs). The NPAs has a direct bearing on the growth and profitability of banks. The NPAs are one of the major concerns for sch...
RECYCLING OF MUNICIPAL SOLID WASTE FOR ELECTRCITY GENERATION AND GREEN EARTH
Waste generation is increasing everywhere. Hence improved waste management is an essential element to make the resource efficient. Municipal Solid Waste (MSW), generated if not properly managed,...
A Study on Spiritual Quotient Among College S tudents In Coastal Town of Mangalore, Karnataka State .
The present study aims to assess the spiritual quotient of college students in Mangalore City. Two collegewere selected by simple random sampling. About 100 students were selected from each o...
Pap Smear Versus Colposcopy For Diagnosis Of Precancerous Lesions Of Cervix
Background : Cervical cancer presents as major cause of morbidity and mortality especially in developing countries like India. Various screen ing programs are implemented for its early detection...
Network Security: Attacks, Tools and T echniques
Network security is main issue of this generation of computing because many types of attacks are increasing day by day. Establishing a network is not a big issue for network administrators but protecting...