2014 | OriginalPaper | Chapter
Kleene Closure on Regular and Prefix-Free Languages
Authors : Galina Jirásková, Matúš Palmovský, Juraj Šebej
Published in: Implementation and Application of Automata
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the Kleene closure operation on regular and prefix-free languages. Using an alphabet of size 2
n
, we get the contiguous range from 1 to 3/4·2
n
of complexities of the Kleene closure of regular languages accepted by minimal
n
-state deterministic finite automata. In the case of prefix-free languages, the Kleene closure may attain just three possible complexities
n
− 2,
n
− 1, and
n
.