| Popis: |
The construction of an @e-free nondeterministic finite automaton (NFA) from a given NFA is a basic step in the development of compilers and computer systems. The standard conversion may produce an @e-free NFA with up to @W(n^[email protected]?|@S|) transitions for an NFA with n states and alphabet @S. To determine the largest asymptotic gap between the minimal number of transitions of NFAs and their equivalent @e-free NFAs has been a longstanding open problem. We show that there exist regular languages L"n that can be recognized by NFAs with O(nlog"2n) transitions, but @e-free NFAs need @W(n^2) transitions to accept L"n. Hence the standard conversion cannot be improved drastically. However, L"n requires an alphabet of size n, but we also construct regular languages K"n over {0,1} with NFAs of size O(nlog"2n), whereas @e-free NFAs require size [email protected]?2^c^@?^l^o^g^"^2^n for every c |
Full Text from ScienceDirect