We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

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