Proving these are/are not regular

Question

In my computing class we just finished studying regular languages. I didn't do as well as I had hoped on my work so I was wanting more insight on the correct way to go about these proofs. My professor did give me some feedback, which I will include, but I didn't quite understand it.

I was asked to prove that these are/are not regular. $\Sigma = \{0, 1\}$ And for the first two, I can assume this is not regular: $\{0^{n}1^{n} \mid n \ge 0\}$, $\{ww \mid w \in \{0, 1\}^*\}$

1) $\{0^{i}1^{j} \mid i,j \ge 0\text{ and }i \ne j\}$

2) $\{0^{n}1^{m} \mid n \ge 2m \ge 0\}$

For both of these, I tried to use the pumping lemma to show that neither of them are regular. For 1) I attmpted to show contradiction by pumping until $i=j$, however this was incorrect. My professor said that 1) is easier to prove without using pumping lemma. He wrote something like this on the board for 1)

$L_{1} = \{0^*1^*\}$

$L_{2} = \{0^{n}1^{n}\}$

$\{0^*1^*\} \cap \overline{L} = \{0^{n}1^{n}\}$

But I don't understand it, can someone please elaborate? On the second, I attempted to pump until $2m$ was greater than $n$, thus contradiction. My answer on this was marked incorrect without any feedback.

Let $L$ be a regular language for the following two and I had to prove $L_{1}$ and $L_{2}$. (Please note, these are zeros in the following two problems, not the letter "o")

3) $L_{1} = \{w \mid 00w \in L\}$

4) $L_{2} = \{w \mid w00 \in L\}$

For both of these I [incorrectly] showed that they are proven to be regular by closure of the union property. I thought the $w00$ meant concatenation between $w$ and $00$. What does it actually mean and how would I attempt these proofs?

Answer 1

Here’s what he was thinking for (1). You know that the language $L_1$ is regular. If your language $L$ were regular, its complement $\overline{L}$ would also be regular. Moreover, the intersection of two regular languages is regular, so $L_1\cap\overline{L}$ would be regular. But $L_1\cap\overline{L}=L_2$.

Proof: Clearly $L_2\subseteq L_1\cap\overline{L}$. On the other hand, if $w\in L_1\cap\overline{L}$, then $w\in L_1$, so $w=0^n1^m$ for some $n,m\ge 0$. Moreover, $w\in\overline{L}$, so $w\notin L$, and therefore $n=m$. $\dashv$

Thus, $L_2$ would have to be regular. But you almost certainly proved in class or in the text that $L_2$ is not regular: it’s just about the simplest example of a context-free language that isn’t regular.

For (2) I assume that you meant the language to be $L=\{0^n1^m:n\ge 2m\ge 0\}$. Let $p$ be the pumping length, and let $w=0^{2p}1^p$. The pumping lemma guarantees that we can write $w$ as $xyz$, where $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for all $k\ge 0$. Then $xy$ is contained in the first $p$ letters of $w$, so $y=0^i$ for some $i>0$, and $xy^0z=0^{2p-i}1^p\notin L$, since $2p-i\not\ge 2p$. Remember, you can also pump down to $k=0$; people often forget this.

For (3) and (4), $w00$ and $00w$ do mean the concatenation of $w$ and $00$ (in the two possible orders), but I don’t see how you got a union out of this. The union of two languages is the set of words that belong to at least one of the two languages; concatenation is a different animal altogether. Before I suggest an approach to these, I need to know whether you’ve already studied the connection between finite state automata and regular languages; if you have, that’s probably the easiest way to approach these two questions.

Added: For (3), you know that there is an NFA that recognizes $L$. I don’t know exactly what formalism you use for NFAs, so I’ll specify it as $M=\langle\Sigma,S,s_0,\delta,A\rangle$, where $\Sigma$ is the alphabet, $S$ is the state set, $s_0$ is the initial state, $\delta$ is the transition function, and $A$ is the set of acceptor states. Let $t$ and $u$ be two new states not in $S$, and let $S'=S\cup\{t,u\}$. $\Sigma$ and $A$ remain unchanged. The new initial state is $u$. The changes to $\delta$ are minor: $u$ has a $0$ transition to $t$, $t$ has a $0$ transition to $s_0$, and all of the original transitions remain unchanged. The resulting NFA clearly accepts $L_1$.

From what you said in the comment, I expect that you can probably do $L_2$ yourself on the basis of this model.

Added: The solution above for (3) is actually based on a misreading of the questions: the NFA that I produced recognizes $\{00w:w\in L\}$, not the $L_1$ of the problem. In other words, I was prepending $00$ to each word of $L$ instead of recognizing the words that appear as suffixes to $00$ in words in $L$. As has been pointed out several times in the comments, modifying a DFA that recognizes $L$ to recognize $L_1$ instead is very straightforward.

If the DFA recognizing $L$ is $M=\langle\Sigma,S,s_0,\delta,A\rangle$, just change the initial state from $s_0$ to $$\delta(\delta(s_0,0),0)\;,$$ the state reached by $M$ after two $0$ transitions from $s_0$, and you’ll have a DFA that recognizes $L_1$. To recognize $L_2$, just change the set $A$ of acceptor states to $$A'=\{s\in S:\delta(\delta(s,0),0)\in A\}\;,$$ the set of states from which two $0$ transitions take you to an acceptor state of $M$.

Answer 2

$1)$ Remember that regular languages are closed under complement and intersection. So if $L$ were regular, then so would $\{0^* 1^*\} \cap \lnot L$ (I guess your teacher denotes $\lnot L$ by $\overline{L}$) because each of those languages are regular. But $\{0^* 1^*\} \cap \lnot L = \{0^n 1^n\}$ which is not regular, hence your original assumption must be incorrect. Thus $L$ cannot be regular.

$2)$ Consider what happens when $m = 0$.

$3)$ and $4)$ Since $L$ is a regular language, there exists some deterministic finite state machine $M$ such that $M$ recognizes $L$. How could you alter $M$ to recognize 2 extra $0$'s at the beginning and end of each acceptable word? (EDIT: See Henning's comment below, this solves a different problem. The basic idea [altering a DFA] is still applicable though)

Answer 3

I think (1) and (2) are simplest to do directly using DFAs, without pumping or intersection.

In both cases, when $p\ne q$ (and $p$, $q$ are not too small), the set of words that can legally follow $0^p1$ is different from the set of words that can legally follow $0^q1$. Therefore, a finite automaton that recognizes the language will have to end up in different states after reading $0^i1$ for all $i$, which means that it cannot be finite.

For (3), take a DFA for $L$ and change the starting state to be the state the original automaton ends up in after reading 00. (If there is no such state, the sought-after language is empty, which is trivially regular).

For (4), take a DFA for $L$ and change the set of accepting states to the set of states that can reach a previously-accepting state in exactly two 0-transitions.