Research Article
Closure Properties of Prefix-free Regular Languages
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 52 - Issue 8 |
| Published: August 2012 |
| Authors: Meenu Lochan, Sunita Garhwal, Ajay Kumar |
10.5120/8220-1645
|
Meenu Lochan, Sunita Garhwal, Ajay Kumar . Closure Properties of Prefix-free Regular Languages. International Journal of Computer Applications. 52, 8 (August 2012), 6-9. DOI=10.5120/8220-1645
@article{ 10.5120/8220-1645,
author = { Meenu Lochan,Sunita Garhwal,Ajay Kumar },
title = { Closure Properties of Prefix-free Regular Languages },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 52 },
number = { 8 },
pages = { 6-9 },
doi = { 10.5120/8220-1645 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A Meenu Lochan
%A Sunita Garhwal
%A Ajay Kumar
%T Closure Properties of Prefix-free Regular Languages%T
%J International Journal of Computer Applications
%V 52
%N 8
%P 6-9
%R 10.5120/8220-1645
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Regular languages are closed under union, intersection, complementation, Kleene-closure and reversal operations. Regular languages can be classified into infix-free, prefix- free and suffix-free. In this paper various closure properties of prefix-free regular languages are investigated and result shows that prefix-free regular languages are closed under union and concatenation. Under complementation, reverse, Kleene-closure and intersection operations prefix-free regular languages are not closed.
References
- Han Y. S. , Salomaa K. , Wood D. , 2007, " State complexity of Prefix-free Regular Languages", HKUST Theoretical Computer Science Center Research Report HKUST-TCSC-2006-02.
- Han Y. S. , Salomaa K, 2009, "State complexity of basic operations on suffix-free regular languages", Theoretical Computer Science 410, 2537-2548.
- Han Y. S. , Wang Y. , Wood D. , 2005, "Prefix-Free Regular-expression Matching" Springer-Verlag Berlin Heidelberg, LNCS 3537, 298-309.
- Han Y. S. , Wood D. , 2007, "Outfix-free Regular Languages and Prime Outfix-free decomposition", Fundamenta Informaticae XX, 1-17.
- Han Y. S. ,Wood D. , " Overlap-free Regular Languages", Springer-Verlag, LNCS 4112, Berlin Heidelberg, COCOON 2006, 469-478.
- Kari J. , 2011, "Automata and formal languages", University of Turku.
- Mishra K. L. P. and N. Chandrasekaran, 1998, "Theory of Computer Science (Automata Language and. Computation) ", PHI, Second edition.
- Peter Linz, 2009, "An Introduction to Formal Languages and Automata", Narosa publishers, fourth edition.
- Sheng Yu, 2001, "State Complexity of Regular Languages", Journal of automata, Languages and Combinatorics, 6(2).
- Ullman, J. , J. E. Hopcroft and R. Motwani, 2001, "Introduction to Automata Theory, Languages, and Computation", Pearson Education Inc.
Index Terms
Keywords