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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Technique to Remove Indistinguishable State with Unreachable State and Dead State from Deterministic Finite Automata

by Dipanshu Rastogi, Ravinder Singh
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 94 - Number 1
Year of Publication: 2014
Authors: Dipanshu Rastogi, Ravinder Singh
10.5120/16311-5540

Dipanshu Rastogi, Ravinder Singh . Technique to Remove Indistinguishable State with Unreachable State and Dead State from Deterministic Finite Automata. International Journal of Computer Applications. 94, 1 ( May 2014), 35-40. DOI=10.5120/16311-5540

@article{ 10.5120/16311-5540,
author = { Dipanshu Rastogi, Ravinder Singh },
title = { Technique to Remove Indistinguishable State with Unreachable State and Dead State from Deterministic Finite Automata },
journal = { International Journal of Computer Applications },
issue_date = { May 2014 },
volume = { 94 },
number = { 1 },
month = { May },
year = { 2014 },
issn = { 0975-8887 },
pages = { 35-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume94/number1/16311-5540/ },
doi = { 10.5120/16311-5540 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:16:28.848977+05:30
%A Dipanshu Rastogi
%A Ravinder Singh
%T Technique to Remove Indistinguishable State with Unreachable State and Dead State from Deterministic Finite Automata
%J International Journal of Computer Applications
%@ 0975-8887
%V 94
%N 1
%P 35-40
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper presents a new technique for efficiently calculating and remove indistinguishable states in finite-state automata. A central problem in automata theory is to minimize a given Deterministic Finite Automaton (DFA). DFA minimization is an important topic because it can be applied both theoretically and practically, in for instance compilers. Minimizing a DFA increases its efficiency by reducing its amount of states and it also enables us to determine if two DFAs are equivalent. A DFA(deterministic finite automata) have some redundant state that means this type of state doesn't participant for generating useful strings. And these types of state are called dead state, unreachable state or indistinguishable state. In deterministic finite automata, it is not easy to determine dead state, unreachable state or inaccessible state and it is necessary for removing unreachable state and dead state from DFA(deterministic finite automata). And removing unreachable state and dead state from deterministic finite automata is very necessary to generating useful string. We can generate minimize deterministic finite automata after removing unreachable state, dead state and indistinguishable state. But it is very difficult to removing these type of state from DFA. Then first we will choose useful state. This paper also explaining about how useful automata package simulator and java formal languages for new technique.

References
  1. Alfred V. Aho, "Constructing a Regular Expression from a DFA", Lecture notes in Computer Science Theory, September 27, 2010, Available at http://www. cscolum bia. edu/ ~aho/cs3261/lectures.
  2. S. H. Rodger. Jap web site, 2011. www. jflap. org .
  3. Hao Wang, Student Member, IEEE, Shi Pu, Student Member, IEEE, Gabe Knezek, Student Member, IEEE, and Jyh-Charn Liu, Member, IEEE, MIN-MAX: A Counter-Based Algorithm for Regular Expression Matching, IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 24, NO. 1, JANUARY 2013.
  4. Domenico Ficara, Member, IEEE, Andrea Di Pietro, Student Member, IEEE, Stefano Giordano, Senior Member, IEEE, Gregorio Procissi, Member, IEEE, Fabio Vitucci, Member, IEEE, and Gianni Antichi, Member, IEEE, Differential Encoding of DFAs for Fast Regular Expression Matching, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 3, JUNE 2011.
  5. Domenico Ficara, Member, IEEE, Andrea Di Pietro, Student Member, IEEE, Stefano Giordano, Senior Member, IEEE, Gregorio Procissi, Member, IEEE, Fabio Vitucci, Member, IEEE, and Gianni Antichi, Member, IEEE, Differential Encoding of DFAs for Fast Regular Expression Matching, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 3, JUNE 2011.
  6. Jean-Charles Delvenne and Vincent D. Blonde, Complexity of Control on Finite Automata, IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 51, NO. 6, JUNE 2006.
  7. Attila Csenki, Flowgraph Models in Reliability and Finite Automata: IEEE TRANSACTIONS ON RELIABILITY, VOL. 57, NO. 2, JUNE 2008.
  8. R. W. Butler, "Reliabilities for feedback systems and their saddle point approximation," Statistical Science, vol. 15, pp. 279–298, 2000.
  9. Gruber H. and Holzer, M. , "Provably shorter regular expressions from deterministic finite automata", LNCS, vol. 5257, pages 383–395. Springer, Heidelberg (2008).
  10. H. Gruber and J. Johannsen, "Optimal lower bounds on regular expression size using communication complexity", In Proceedings of the 11th International Conference Foundations of Software Science and Computation Structures, volume 4962 of LNCS, pages 273–286, Budapest, Hungary, March–April 2008.
  11. M. Procopiuc, O. Procopiuc, and S. Rodger, Visualization and Interaction in the Computer Science Formal Languages Course with JFLAP, 1996 Frontiers in Education Conference, Salt Lake City, Utah, p. 121-125, 1996
Index Terms

Computer Science
Information Sciences

Keywords

Automata Deterministic finite automata Unreachable State Dead State.

Powered by PhDFocusTM