Is it possible to design a DFA for these languages? $$\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$$
 A: 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.
