1
$\begingroup$

I've faced this question in my homework and I couldn't provide elegant proof for it.

We're given $\Sigma_n=\{1,\dots,n\}$ and a language: $$L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\sigma(w)=0\}$$ That is a language that consists of letters from $\Sigma_n$ but doesn't contain all the letters.

Question: We're asked to prove that there is no $DFA$ with less than $2^n$ states that accepts $L_n$.

Note: It's given that there is $NFA$ with $(n+1)$ states that accepts $L_n$.

Improve this question
$\endgroup$
4
  • $\begingroup$ Have you learned "Myhill–Nerode theorem"? Have you read the proof for it? $\endgroup$
    – John L.
    Commented Mar 18, 2022 at 20:26
  • $\begingroup$ Yea I did, I tried actually to use it but it was hard at some point. $\endgroup$
    – Mohamad S.
    Commented Mar 18, 2022 at 20:28
  • $\begingroup$ Suppose $n=1$. List all different equivalence classes, where each class can be represented by a (shortest) string in it. Do the same for $n=2$. You may see the pattern. $\endgroup$
    – John L.
    Commented Mar 18, 2022 at 20:33
  • 1
    $\begingroup$ @JohnL. Thanks John, I appreciate your tip, I will try to follow it and understand how the proof works. $\endgroup$
    – Mohamad S.
    Commented Mar 18, 2022 at 20:41

1 Answer 1

Reset to default
3
$\begingroup$

You can use the Myhill-Nerode theorem for the given task. You must provide at least $2^n$ prefixes $p_i\in \Sigma_n^*$ belonging to the different equivalence classes, e.g. s.t. for every two prefixes $p_i$, $p_j$ there exists a suffix $s_{i,j}$ s.t. $p_i s_{i,j}\in L_n$ and $p_j s_{i,j}\notin L_n$ or vice versa.

Given your task, such prefixes correspond to all possible subsets of the alphabet $\Sigma_n$. There are $2^n$ such subsets, and the strings containing all the letters from the chosen subset $S_i$ and no other letters definitely satisfy the Myhill-Nerode equivalence class criterion. Given two words $p_i$, $p_j$ corresponding to the subsets $S_i$ and $S_j$, s.t. $S_i\not\subseteq S_j$, the suffix $p_k$ corresponding to the set $S_k=\Sigma_n\setminus S_i$ discerns $p_i$ and $p_j$, since $p_i p_k\not\in L_n$ and $p_j p_k\in L_n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I reviewed your answer and I have a question. What about the case where we're given two words $p_i ,\ p_j$ corresponding to the subsets $S_i$ and $S_j$, s.t. $S_i \subseteq S_j$? $\endgroup$
    – Mohamad S.
    Commented Mar 21, 2022 at 16:36
  • $\begingroup$ If the subsets $S_i$ and $S_j$ are not equal, then $S_i\subseteq S_j$ simply implies $S_j\not\subseteq S_i$, and the symmetric reasoning holds. $\endgroup$
    – Tonita
    Commented Mar 21, 2022 at 18:24
  • $\begingroup$ Oh right, thanks for the explanation. $\endgroup$
    – Mohamad S.
    Commented Mar 21, 2022 at 19:38

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.