Research Article
A Structural Construction of a Deterministic Position Automaton
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 67 - Issue 23 |
| Published: April 2013 |
| Authors: O. V. Shanmuga Sundaram, N. Murugesan |
10.5120/11534-7273
|
O. V. Shanmuga Sundaram, N. Murugesan . A Structural Construction of a Deterministic Position Automaton. International Journal of Computer Applications. 67, 23 (April 2013), 13-17. DOI=10.5120/11534-7273
@article{ 10.5120/11534-7273,
author = { O. V. Shanmuga Sundaram,N. Murugesan },
title = { A Structural Construction of a Deterministic Position Automaton },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 67 },
number = { 23 },
pages = { 13-17 },
doi = { 10.5120/11534-7273 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A O. V. Shanmuga Sundaram
%A N. Murugesan
%T A Structural Construction of a Deterministic Position Automaton%T
%J International Journal of Computer Applications
%V 67
%N 23
%P 13-17
%R 10.5120/11534-7273
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Every regular expression can be transformed into a Non-deterministic Finite Automaton (NFA) with or without - transitions. A well known algorithm called subset construction technique is used for conversion of NFA into DFA. In this paper, initially, the construction of the position automaton is given for the same. Also, the algorithm to convert this Position Automaton into DFA using subset construction technique is discussed.
References
- Bruggermann-Klein A. , Regular expressions into finite automata, Theoretical Comput. Sci. , 120:197 – 213, 1993.
- Champarnaud, J. M. , Quardi F. , and Ziadi D. , Normalized expressions and finite Automata, Intern. Journ. Of Alg. And Comp. , 17(1):141-154, 2007.
- Champarnaud J. M. , and Ziadi D. , Canonical Derivatives, Partial Derivatives and Finite Automaton Constructions, Theoretical Computer Science, 289:137-163, 2002.
- Chang C. H. , and Paige R. , From Regular Expressions to DFA's using Compressed NFA's, Theoretical Computer Science, 178, 1997, 1 – 36.
- Glushkov V. M. , The Abstract Theory of Automata, Russian Mathematical Surveys 16(1961), 1-53.
- Hromkovic J. , Seibert S. , and Wilke T. , Translating Regular Expressions into Small Epsilon-free Nondeterministic Automata, Journal. Computer. System Sci. , 62(4):565-588, 2001.
- Hopcroft J. E. , Rajeev Motwani and Ullman J. D. , Introduction to Automata theory, Languages and Computation, Narosa Publishing House, New Delhi, 1987.
- Hugo Gouveia, Nelma Moreira and Rogerio Reis, Small NFAs from Regular Expressions: Some Experimental Results, arXiv: 1009. 3599v1
- McNaughton R. , and Yamada H. , Regular expressions and state graphs for automata, IEEE Trans. on Electronic Computers, 9(1):39-47, 1960
- Murugesan N. , Principles of Automata theory and Computation, 2004, Sahithi Publications.
- Murugesan N. , and Shanmugasundaram O. V. , Construction of State diagram of a regular expression using Derivatives, www. m-hikari. com/ams/ams-2012/ams. . . /sundaramAMS21-24-2012. pdf, Applied Mathematical Sciences, Vol. 6, 2012, no. 24, 1173 – 1179.
- Saradhi Varma G. P. , and Thirupathi Rao B. , Theory of Computation – Formal Languages and Automata Theory, Scitech Publications (India) Pvt. Ltd. , Chennai, 2005, 2. 18 – 2. 19.
Index Terms
Keywords