[Math] Give a language L over alphabet $\{0,1\}$ such that the following criteria are met:

Question

---

If we let the regex $R=(0+1)(0+1)(0+1)$

and we let the DFA be as follows:

Does this work? Every state is accepting (and thus max length of string is 3), and if it's more, then it goes to a dead state.

If this works, I don't understand the point of the second condition, "any DFA that accepts L has atleast 9 states". Is my solution wrong?

Answer 1

I hope it can help you

the question is asking for $\underline{a\, language} $

such that:

1. L contains at least one string of length 3 but none longer ,

2. any DFSA that accepts L has at least 9 states (including a dead state) .

   • your solution is wrong because you found a DFA with less than 9 states for your language.but the question is asking for $\underline{a\, language} $ such that minimal DFA for L has 9 states.

---

(Distinguishable Strings) Let $L$ be a language over an alphabet $Σ$. We say that two strings $x$ and $y$ are distinguishable with respect to $L$ if there is a string $z$ such that $xz \in L$ and $yz\notin L$ or vice versa.

---

(Distinguishable Set of Strings) Let $L$ be a language. A set of strings $\{x_1 , . . . , x_k \}$ is distinguishable if for every two distinct strings $x_i$,$x_j$ we have that $x_i$ is distinguishable from $x_j$.

---

Lemma: Let $L$ be a language, and suppose there is a set of $k$ distinguishable strings with respect to $L$. Then every DFA for $L$ has at least $k$ states. $.^{[1]}$

---

$\{u\in\{0,1\}^* :|u|\le 3 \}=\{\epsilon,0,1,01,10,00,11,001,011,010,100,101,110,000,111\}$

now we use lemma to find language $L$:

if $\,L=\{0,1,00,11,010,111,000,010,011,100\}$ then we can find $D$ (Distinguishable Set of Strings)

$$D=\{\epsilon, 0,1,01,10,00,11,010,101\}$$ D is a set of 9 distinguishable strings with respect to $L$ so every DFA for L has at least 9 states.

DFA diagram that accepts L ("few state as possible"):

---

^[1] Proof: If $L$ is not regular, then there is no DFA for $L$, much less a DFA with less than $k$ states. If $L$ is regular, let $M$ be a DFA for $L$, let $x_1, . . . , x_k$ be the distinguishable strings, and let $q_i$ be the state reached by $M$ after reading $x_i$. For every $i\ne j$, we have that $x_i$ and $x_j$ are distinguishable, and so $q_i\ne q_j$ because of Lemma . So we have $k$ different states $q_1,...,q_k$ in $M$, and so $M$ has at least $k$ states.

---

Notes on State Minimization