Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430749 | Journal of Computer and System Sciences | 2008 | 15 Pages |
Abstract
We construct regular languages Ln, n⩾1, such that any NFA recognizing Ln needs transitions. Here nsc(Ln) is the nondeterministic state complexity of Ln. Also, we study trade-offs between the number of states and the number of transitions of an NFA. We show that adding one additional state can result in significant reductions in the number of transitions and that there exist regular languages Ln, n⩾2, where the transition minimal NFA for Ln has more than c⋅nsc(Ln) states, for some constant c>1.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics