Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Union-freeness of Regular Languages

International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 50 - Number 4
Year of Publication: 2012
Sukhpal Singh Ghuman
Ajay Kumar

Sukhpal Singh Ghuman and Ajay Kumar. Article: Union-freeness of Regular Languages. International Journal of Computer Applications 50(4):6-8, July 2012. Full text available. BibTeX

	author = {Sukhpal Singh Ghuman and Ajay Kumar},
	title = {Article: Union-freeness of Regular Languages},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {50},
	number = {4},
	pages = {6-8},
	month = {July},
	note = {Full text available}


A regular language can be converted into an equivalent union-free regular language. Every non-union-free regular expression can be decomposed into an equivalent union-free regular expression, but it may not be unique. In this research paper, an algorithm is designed for determining whether a regular expression is union-free or not and the same is implemented in . NET.


  • Mishra K. L. P. and N. Chandrasekaran, 1998, " Theory of Computer Science (Automata Language and. Computation) ", PHI, Second edition.
  • Nagy, B. ,2004 , "A normal form for regular expressions ", In Eighth International Conference on Developments in Language Theory, CDMTCS Technical Report 252, Auckland, 51–60.
  • Nagy, B, 2010, "On Union-complexity of Regular Languages", 11th IEEE International Symposium on Computational Intelligence and Informatics, Hungary, 177-182.
  • Nagy, B. , 2006, "Union-free languages and 1-cycle-free-path-automata", Publicationes mathematicae Debrecen 68, 183– 197.
  • Peter Linz, 2009, "An Introduction to Formal Languages and Automata", Narosa publishers, fourth edition.
  • Sergey Afonin and Denis Golomazov, 2009, "On Minimal Union-Free Decompositions of Regular Languages", Third International conference, Lata, Spain, 83-92.
  • Sinisa Crvenkovic, Igor Dolinka and Zoltan Esik, 2001 "On Equations for Union-Free Regular Languages", Information and Computation, 164, 152-172.
  • Ullman, J. , J. E. Hopcroft and R. Motwani, 2001, "Introduction to Automata Theory, Languages, and Computation", Pearson Education Inc.