Advertisement
Published in:
2011 | OriginalPaper | Chapter
Chrobak Normal Form Revisited, with Applications
Author : Paweł Gawrychowski
Published in: Implementation and Application of Automata
Publisher: Springer Berlin Heidelberg
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
It is well known that any nondeterministic finite automata over a unary alphabet can be represented in a certain
normal form
called the Chrobak normal form [1]. We present a very simple conversion procedure working in
$\mathcal{O}(n^3)$
time. Then we extend the algorithm to improve two trade-offs concerning conversions between different representations of unary regular languages. Given an
n
-state NFA, we are able to find a regular expression of size
$\mathcal{O}(\frac{n^2}{\log^2 n})$
describing the same language (which improves the previously known
$\mathcal{O}(n^2)$
size bound [8]) and a context-free grammar in Chomsky normal form with
$\mathcal{O}(\sqrt{n\log n})$
nonterminals (which improves the previously known
$\mathcal{O}(n^{2/3})$
bound [3]).