Is it possible to design a DFA for these languages?

57 Views Asked by At

$$\mathcal{L}_1 = \{1^{\cdot n}w\mid,n\geq1, w \text{ has }n\text{ or more 1's}\}$$

$$\mathcal{L}_2 = \{1^{\cdot n}w\mid,n\geq1,w \text{ has }n\text{ or fewer 1's}\}$$

I am thinking that there shouldn't be a way for the DFA to know when to stop treating the string as $1^{\cdot n}$ and a way to remember the number of 1's seen.

I know that '111111' is both an accepted and unaccepted string depending on what $w$ we select, so for this purpose, we assume that a string is rejected only if there is no $w$ we can choose to accept it.

I got $$\mathcal{L}_1 = 1\cdot\Sigma^*\cdot1\cdot\Sigma^*$$

but I am unsure about $$\mathcal{L}_2$$

1

There are 1 best solutions below

0
On

As you have noted, $\mathcal L_1 = 1 \{0,1\}^* 1 \{0,1\}^*$, so it is regular.

To show that $\mathcal L_2$ is not regular, we can use the pumping lemma.

The pumping lemma states that if $\mathcal L$ is a regular language, then there exists an integer $p \ge 1$ such that any word of $\mathcal L$ can be decomposed in the form $xyz$ with $|xy| \le p$ and $|y| \ge 1$, in such a way that $xy^nz$ is also a word of $\mathcal L$ for every $n \ge 0$.

Since the reverse of a regular language is also regular, we can restate the pumping lemma as (or obtain a corollary stating that) for any regular language $\mathcal L$, there exists an integer $q \ge 1$ such that every word of $\mathcal L$ can be decomposed in the form $uvw$ with $|vw| \le p$ and $|v| \ge 1$, in such a way that $uv^nw$ is also a word of $\mathcal L$ for each $n \ge 0$.

Now, suppose that $\mathcal L_2$ is regular. Then there exists $q \ge 1$ satisfying the condition stated above. Now consider the string $s = 1^q0^q$, which is a word of $\mathcal L_2$. Decomposing $s$ as $s = uvw$ in accordance with the restated pumping lemma, we see that $v = 1^r$ for some $r \ge 1$ (since $|vw| \le q$ and $|v| \ge 1$). But then, $uv^nw = 1^q0(1^{nr})1^{q - r} = 1^q01^{(n - 1)r + q}$ is also in $\mathcal L_2$. We can choose $n$ large enough so that $(n - 1)r + q > q$, resulting in a word that cannot be in $\mathcal L_2$, which is a contradiction. Therefore, $\mathcal L_2$ is not regular.