# NFA's number of states

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?

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

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).
     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$.