For every $i$ we define $\Sigma_i=${$1, 2, ..., i$} and a language over said $\Sigma_i$: $L_i=${$w\in \Sigma_i^*| \exists \sigma \in \Sigma_i :\sigma$ does not appear in $w$}

And I'm asked to prove that for all $i>2$, $L_i$ has an NFA with $i+1$ vertices.

I've had the idea of implementing it as a chain of vertices where each vertex has $|\Sigma_i|$ transitions to a "pit" vertex, with no out-going edges, and due to being non-deterministic, if a word contains the specific character we wish to not exist in our word,it will choose the edge leading to the pit, thus not accepted by the NFA.

I'm certain that the main issue here is understanding the definition deeply, which I could not establish this kind of understanding as of now, only superficial.

  • 1
    $\begingroup$ What's an NDA? If you mean a NFA, then use an initial state plus one state for each symbol $\sigma \in \Sigma_i$. The meaning of the states is as following: if you are in state $\sigma$ (among others, since this is a NFA) then you never encountered $\sigma$ in the portion of the input string read so far. The transitions follow from this definition and consists of $\varepsilon$-transitions from the initial state, plus a transition from each state $\sigma$ to itself for all symbols in $\Sigma_i \setminus \{ \sigma \}$ All states are final states. (There is no need for a "pit" state in a NFA). $\endgroup$
    – Steven
    Apr 24, 2023 at 17:49
  • $\begingroup$ I see, I also encounterd this exmaple after further exploration. Thank you very much! $\endgroup$
    – Aishgadol
    Apr 24, 2023 at 18:09


Your Answer

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

Browse other questions tagged or ask your own question.