کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436865 690046 2007 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Comparing the size of NFAs with and without ε-transitions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Comparing the size of NFAs with and without ε-transitions
چکیده انگلیسی

The construction of an ε-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 ε-free NFA with up to Ω(n2⋅|Σ|) transitions for an NFA with n states and alphabet Σ. To determine the largest asymptotic gap between the minimal number of transitions of NFAs and their equivalent ε-free NFAs has been a longstanding open problem. We show that there exist regular languages Ln that can be recognized by NFAs with O(nlog2n) transitions, but ε-free NFAs need Ω(n2) transitions to accept Ln. Hence the standard conversion cannot be improved drastically. However, Ln requires an alphabet of size n, but we also construct regular languages Kn over {0,1} with NFAs of size O(nlog2n), whereas ε-free NFAs require size for every c<1/2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 380, Issues 1–2, 21 June 2007, Pages 100-114