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 75
- Downloads 0
Performance Appraisal Management In Aviation Industry
Now day’s aviation industry plays a vital role in global economy. It’s a key factor between air and land based transportation of goods and passengers. It is a part of internatio nal supply chain networks....
Analyzing the role of non-seasonal discounts in consumer expenses for a small market environment
Here we consider the observed changes in the consumer expenses in a district of Albania following market sales discount. By calculating latent variable as the usefulness of the discounts offered we interpret the net expe...
The Hundred Differences between Islamic and Conventional Banking Systems
Islamic Banking is a cat chphrase now to many of the policy makers in the globe. Neither receipt nor payment of interest in this system questions its survival. Astoundingly, it has proved itself as a more effective syste...
Effect of Route Reflection on IBGP Convergence and an approach to reduce convergence time
Request for Comments (RFCs) for Border gateway Protocol (BGP) suggest that the network topology using BGP must have full mesh of IBGP sessions to avoid routing loops . Routing loop is a condition where packets are...
Adequate Battery Energy Storage System
This paper explain a review on adequate battery energy storage system. A Competent BESS(Battery Energy storage system) for buffer system is studied for the reason that a gradual diminishing in...