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
Implementation of Feature Selection Using Correlation Matrix in Python

Ahmad Farhan AlShammari
Random Articles
Reseach Article

Algorithm to Generate DFA for AND-operator in Regular Expression

by Mirzakhmet Syzdykov
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 124 - Number 8
Year of Publication: 2015
Authors: Mirzakhmet Syzdykov
10.5120/ijca2015905557

Mirzakhmet Syzdykov . Algorithm to Generate DFA for AND-operator in Regular Expression. International Journal of Computer Applications. 124, 8 ( August 2015), 31-34. DOI=10.5120/ijca2015905557

@article{ 10.5120/ijca2015905557,
author = { Mirzakhmet Syzdykov },
title = { Algorithm to Generate DFA for AND-operator in Regular Expression },
journal = { International Journal of Computer Applications },
issue_date = { August 2015 },
volume = { 124 },
number = { 8 },
month = { August },
year = { 2015 },
issn = { 0975-8887 },
pages = { 31-34 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume124/number8/22125-2015905557/ },
doi = { 10.5120/ijca2015905557 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:13:52.099909+05:30
%A Mirzakhmet Syzdykov
%T Algorithm to Generate DFA for AND-operator in Regular Expression
%J International Journal of Computer Applications
%@ 0975-8887
%V 124
%N 8
%P 31-34
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

For the past time a number of algorithms were presented to produce a deterministic finite automaton (DFA) for the regular expression. These algorithms could be divided into what they used as an initial data from which to produce DFA. The method to produce DFA from non-deterministic finite automaton (NFA) by a subset construction could be generalized for extended regular expressions, including intersection, negation and subtraction of the regular languages. In this article the modified algorithm of subset construction is presented; this algorithm produces a unigram DFA for the regular expression with extensions (specifically AND-operator).

References
  1. K. Thompson. Regular expression search algorithm. Comm. ACM, 11 (6) (1968), pp. 419–422.
  2. M.O. Rabin, D. Scott. Finite automata and their decision problems. IBM J. Res. Develop., 3 (2) (1959), pp. 114–125.
  3. Samuel C. Hsieh. Product Construction of Finite-State Machines. Proceedings of the World Congress on Engineering and Computation Science, Vol. I (2010), pp. 141-143.
  4. Kai Wang, Jun Li. Towards Fast Regular Expression Matching in Practice. Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM (2013), pp. 531-532.
Index Terms

Computer Science
Information Sciences

Keywords

Algorithm Deterministic Automaton Extension Intersection Subset Construction.

Powered by PhDFocusTM