Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/227193
Title: Design and development of algorithms for converting parallel regular expressions to deterministic finite automata
Researcher: Kumar, Ajay
Guide(s): Verma, Anil Kumar
Keywords: Finite Automata
Parallel Regular Expressions
University: Thapar Institute of Engineering and Technology
Completed Date: 2013
Abstract: Regular expressions are widely used in various applications such as XML schema languages, compiler designs, model checking, bio-informatics, virus detection systems, intrusion detection systems, finite state based testing, text processors and as a programming tool for multifarious scripting languages such as PHP and PERL, etc. A regular expression extended by intersection and shuffle operators do not increase the expressive power of the regular expression, but succinctness due to the inclusion of these additional operators are difficult to handle with the standard operators. In one form or another, the additional operator shuffle appears in different forms of computer science, namely process algebra, multipoint communication, XML schema RELAX NG, computational resource reduction, and concurrency of processes. This dissertation focuses on the design of algorithm s for the conversion of regular expressions with additional operators to the finite automaton. Firstly, we develop an algorithm for the conversion of parallel regular expressions to non- deterministic finite automata using the follow-position of symbols presenting in the parallel regular expressions. It has also been proven that parallel regular expressions cannot be converted into deterministic finite automata directly. In the worst-case scenario, 2m+1 number of states are required for the construction of the non- deterministic finite automaton, where m represents the number of instances of alphabets in a parallel regular expression. In earlier existing approaches, the number of states of the non-deterministic finite automaton in the worst case is equal to 22jrj..3C, where jrj and C represent respectively the length and number of concatenation in a parallel regular expression. Secondly, we explore and design a sound and complete algorithm for the conversion of semi-extended regular expressions to deterministic finite automata.
Pagination: xiii, 120p.
URI: http://hdl.handle.net/10603/227193
Appears in Departments:Department of Computer Science and Engineering

Files in This Item:
File Description SizeFormat 
file10(chapter 7).pdfAttached File170.55 kBAdobe PDFView/Open
file11(chapter 8).pdf46.21 kBAdobe PDFView/Open
file12(references).pdf67.26 kBAdobe PDFView/Open
file1(title).pdf34.21 kBAdobe PDFView/Open
file2(certificate).pdf415.52 kBAdobe PDFView/Open
file3(preliminary pages).pdf478.37 kBAdobe PDFView/Open
file4(chapter 1).pdf116.55 kBAdobe PDFView/Open
file5(chapter 2).pdf210.54 kBAdobe PDFView/Open
file6(chapter 3).pdf128.42 kBAdobe PDFView/Open
file7(chapter 4).pdf202.92 kBAdobe PDFView/Open
file8(chapter 5).pdf120.55 kBAdobe PDFView/Open
file9(chapter 6).pdf143.58 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.