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 46
- Downloads 0
Computational Investigation for Secondary Structure Prediction
P rotein structure prediction play a key role in every living organisms All living organisms are made up of cells and each cell in its turn consists of certain protein consequences which exercise an impor...
Design of Unique Auto Disconnect Password Generation for Public Wi - Fi Routers
WI - FI has emerged as the single most popula r wireless network protocol of the 21st century. While other wireless protocols work better in certain situations, WI - FI technology is used in many organizations...
A Critical Review of Stealth Technology on The Ships And Submarine
Unlike the submarine, the surface ship remains permanently exposed on the surface of the sea. This makes special, and extremely stringent, demands on the vessel’s stealth properties. In the design of...
Comparative Performance Evaluation Of Himachal Pradesh Co - Operative Bank And Kangra Central Co - Operative Bank
Co - operative structure is a very important part of our financial system especially in rural financing. On grass root level a lot of cooperative societies’ function, which help in solving the financial needs of the...
Conservation o f Freshwater Fish Biodiversity: A Challenge for Rajasthan
Fish biodiversity is associated with deserts around the globe. Freshwater fishes have suffered from the resultant altered flow regime, together with other threats including habitat degradation and alien species. Impacts...