CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A Structural Construction of a Deterministic Position Automaton

by O. V. Shanmuga Sundaram, N. Murugesan
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 67 - Number 23
Year of Publication: 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 },
issue_date = { April 2013 },
volume = { 67 },
number = { 23 },
month = { April },
year = { 2013 },
issn = { 0975-8887 },
pages = { 13-17 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume67/number23/11534-7273/ },
doi = { 10.5120/11534-7273 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:26:13.518312+05:30
%A O. V. Shanmuga Sundaram
%A N. Murugesan
%T A Structural Construction of a Deterministic Position Automaton
%J International Journal of Computer Applications
%@ 0975-8887
%V 67
%N 23
%P 13-17
%D 2013
%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
  1. Bruggermann-Klein A. , Regular expressions into finite automata, Theoretical Comput. Sci. , 120:197 – 213, 1993.
  2. Champarnaud, J. M. , Quardi F. , and Ziadi D. , Normalized expressions and finite Automata, Intern. Journ. Of Alg. And Comp. , 17(1):141-154, 2007.
  3. Champarnaud J. M. , and Ziadi D. , Canonical Derivatives, Partial Derivatives and Finite Automaton Constructions, Theoretical Computer Science, 289:137-163, 2002.
  4. Chang C. H. , and Paige R. , From Regular Expressions to DFA's using Compressed NFA's, Theoretical Computer Science, 178, 1997, 1 – 36.
  5. Glushkov V. M. , The Abstract Theory of Automata, Russian Mathematical Surveys 16(1961), 1-53.
  6. 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.
  7. Hopcroft J. E. , Rajeev Motwani and Ullman J. D. , Introduction to Automata theory, Languages and Computation, Narosa Publishing House, New Delhi, 1987.
  8. Hugo Gouveia, Nelma Moreira and Rogerio Reis, Small NFAs from Regular Expressions: Some Experimental Results, arXiv: 1009. 3599v1
  9. McNaughton R. , and Yamada H. , Regular expressions and state graphs for automata, IEEE Trans. on Electronic Computers, 9(1):39-47, 1960
  10. Murugesan N. , Principles of Automata theory and Computation, 2004, Sahithi Publications.
  11. 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.
  12. 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

Computer Science
Information Sciences

Keywords

Regular expressions Position automaton subset construction DFA NFA

Powered by PhDFocusTM