2
$\begingroup$

We can establish some lower bounds for DFAs recognizing specific languages. For example, we can show that there exists a language $L_n$ such that every DFA recognizing it has at least $2^n $ states. The proof is based on a simple distinguishing set of size $2^n$, such that for every two distinct members of this set, there exists a string $z$ such that appending $z $ to these strings results in different outcomes (one string is in the language and the other is not).

Now, I'm curious if there is a similar method for NFAs. For example, can we have a language $L_n $ such that every NFA for it needs at least $2^n $ states? This probably requires some method used in NFA minimization, as the distinguishability relationship used for showing lower bounds for DFAs is related to DFA minimization. Maybe my intuition is wrong, so can anyone provide an example of such a language and briefly explain the methods showing that this language cannot have any NFA with fewer than $2^n $ states?

As @shaull stated in the comment, the language could be a singleton $\{a^{2^n}\}$ and we need more conditions. For the second restriction, we are looking for a language whose reverse can be recognized by an NFA with $n$ states. Therefore, an example in this case probably couldn't be trivial, as most trivial examples are symmetric and thus closed under reverse.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Your question is not clear enough: certainly we can find such a family of languages, e.g., the singleton $L_n=\{a^{2^n}\}$. What I suspect you mean is that there is also some other condition. For example, in the DFA case, we can find such languages that also have a small NFA. Then things become interesting. $\endgroup$
    – Shaull
    Commented Jun 21 at 17:27
  • $\begingroup$ Are you referring to this argument? It is just a specific example. As @Shaull, suggested you can easily construct languages that need to have a linear chain of length at least $2^n$ even in NFAs. $\endgroup$
    – codeR
    Commented Jun 21 at 17:53
  • 1
    $\begingroup$ @Shaull, thanks for mentioning that. I have edited the question to be more specific. $\endgroup$
    – Zapp Brannigan
    Commented Jun 22 at 15:26

1 Answer 1

Reset to default
3
$\begingroup$

Following your edit: NFAs are closed under reversal in $O(1)$. Indeed, take an NFA with $n$ states, then you can obtain an NFA for the reverse by reversing the transitions and swapping the accepting states with the initial states.

Therefore, there is no such example as what you seek.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You are correct :( Can I consider another restriction so that we have a PDA for it with O(n) states? The question I asked is now very trivial :( $\endgroup$
    – Zapp Brannigan
    Commented Jun 22 at 15:36
  • $\begingroup$ PDA? Or still NFA? PDAs are far more complicated. It's not clear to me what you're trying to achieve exactly. A natural blowup in NFAs is in complementation: there is a family of languages that have an NFA of size $n$, but the NFA for the complement is exponential. $\endgroup$
    – Shaull
    Commented Jun 22 at 15:42
  • $\begingroup$ Yes, that's great. Its complement having at least exponential blowup is a good condition. Can I add it to the question now? $\endgroup$
    – Zapp Brannigan
    Commented Jun 22 at 15:44
  • 1
    $\begingroup$ No need. Just look at the answers here:cs.stackexchange.com/questions/11802/… $\endgroup$
    – Shaull
    Commented Jun 22 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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