Lower bound states for NFAs: seeking examples and methods

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.

• 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. Commented Jun 21 at 17:27
• 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. Commented Jun 21 at 17:53
• @Shaull, thanks for mentioning that. I have edited the question to be more specific. Commented Jun 22 at 15:26

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.
• 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. Commented Jun 22 at 15:42