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 56
- Downloads 0
Analysis of Student Ability in Solving PISA-Like Math Problems: a case study in SMPN 8 Banda Aceh, Indonesia
The Programme International for Student Assessment (PISA) has become a tool in determining the quality of education in a certain country. Unfortunately, Indonesian students still have difficulties in solving PISA problem...
Automated Detection and Counting of Red Blood Cell using Image Processing Techniques.
The major issue in clinical laboratory is to produce a precise result for every test especially in the area of Red Blood Cell (RBC) count. R ed blood cell (RBC) count in a blood test used...
Role of Co - Operative Bank in Agriculture: A Case Study Of District Mohali, Punjab
The purposes of the study are to identify the beneficiaries of co - operative banks’ agricultural credit and to assess the impact for bank fin ances and the borrower - farmers. The impact has me...
A study on Retailing of Leather Products in Vellore District
Using survey method, the present study aims at finding out the marketing activities carried o ut by the retailers of leather products, the price range, which their customers prefer, factors c...
A Probabilistic Inventory Model with Two-Parameter Exponential Deteriorating Rate and Pareto Demand Distribution
Although the deterioration is one of the main problems that have been investigated in the inventory systems science the last twenty years ago but Most deteriorating inventory studies focused on deterministic models. This...