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

Answer 2

First of all, the DFA on the picture doesn't correspond to the regex $(0+1)(0+1)(0+1)$, since e.g. the empty word doesn't fit the regex pattern but it is accepted by the DFA. For the regex to be compatible with the picture it should be: $(\varepsilon+0+1)(\varepsilon+0+1)(\varepsilon+0+1)$.

Second, both the language defined by the regex and the language defined by the DFA satisfy the first condition of the exercise but not the second. The second condition says there must not exist a DFA with less than 9 states which accepts your language. Your DFA has 5 states and accepts the language, so it's not correct.

To solve this exercise I believe you should use the Myhill-Nerode theorem. It states that for a regular language $L \subseteq \{ 0, 1 \}^*$ the least possible number of states in a DFA accepting $L$ is the number of equivalence classes of the following relation: for $u, v \in \{ 0, 1 \}^*$

$$u \sim_L v \quad \text{ if } \quad (\forall w \in \{ 0, 1 \}^*) \big[ uw \in L \Leftrightarrow vw \in L \big]$$

So the language $L$ will satisfy the second condition if and only if you can find $9$ words in $\{ 0, 1 \}^*$ pairwise unrelated with respect to $\sim_L$.