0
$\begingroup$

I have read that the NFA size (i.e., the number of states) is linear in the number of characters in the regular expression. This holds even in the presence of character repetitions.

I would like to know why is it so?

If I have a pattern like this , [b-d]at then the number of states will be just 4 incase of NFA ? Size of DFA for this regular expression will also be 4?

$\endgroup$
  • $\begingroup$ Please elaborate? $\endgroup$ – Yuval Filmus Oct 23 '13 at 8:37
  • $\begingroup$ What is a pattern set? Perhaps you are talking about converting a regular expression to an NFA? $\endgroup$ – Shaull Oct 23 '13 at 8:39
  • $\begingroup$ @Shaull pattern-set is referring to regular expression $\endgroup$ – Xara Oct 23 '13 at 8:41
2
$\begingroup$

What is meant by NFA size is linear in the number of characters in the patternset is that there exists constants $A,B$ such that every pattern of length $n$ is accepted by some NFA of size at most $An+B$. This is proved by structural induction on the patternset, and is a rather straightforward exercise.

Without knowing the constants $A,B$, you can't predict what the general claim gives you for any particular pattern. If you work out the proof, you will get values for $A,B$, and then you will be able to obtain a bound on the NFA size for your sample pattern; that bound probably would be worse than $4$. DFA size could be much bigger. For example, for an alphabet of size $n$, the set of all words not containing all characters has a description of size $O(n^2)$, but has DFA size $2^n$ (NFA size is $n$ or $n+1$, depending on the definition).

$\endgroup$
0
$\begingroup$

There is indeed an algorithm to convert a regular expression to a NFA of size linear in the size of the regexp, but this result holds for regular expressions defined in formal language theory. I am not so sure about the corresponding result for regexps used in programming languages, even if one considers only regexps representing regular languages. In particular, if you allow expressions of the form

     a\{n\}     (Matches 'a' repeated exactly n times.)

like in the POSIX Basic Regular Expressions, the result you mention does not hold anymore, since the size of a NFA accepting $\{a^n\}$ will be at least $n$, while the length of the expression a\{n\} will be $5 + log_{10} n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.