# Proving these are/are not regular

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?

-

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$.

-
Yes, I have studied the connection between finite state automata and regular languages. In class we often have the choice of building an NFA or DFA instead of writing a proof. It would be trivial to write a DFA that starts or ends with "00". This seems too easy. But I still don't know how to write the formal proof. – Austin Henley Feb 29 '12 at 7:26
@Austin: Okay, I’ve added a bit to cover the other two problems. – Brian M. Scott Feb 29 '12 at 7:39
Thank you very much! After reading over 2) a few more times I should be golden. – Austin Henley Feb 29 '12 at 7:48
I think it would be easier to work with DFAs for (3) and (4). Then we don't need add states or transitions, just assign a different starting state in (3) and modify the set of accepting states in (4). – Henning Makholm Feb 29 '12 at 20:40
@Henning: I don’t see how you’re going to do that. I used an NFA because it seemed very slightly less complicated: with a DFA I’d have done exactly what I did with the NFA and added a ‘dump’ state for the $1$ transitions out of the new states. – Brian M. Scott Feb 29 '12 at 23:45

$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)

-
For 3) and 4), like I mentioned in a comment on Brian's answer, its trivial to write a DFA for it. How would I write the proof though? – Austin Henley Feb 29 '12 at 7:32
For (3) and (4) you seem to have misread the problem statement in the same way Brian did. The machine should not be altered to recognize two extra $0$s, but to _pretend_ that it has recognized $0$'s that are not in the input. – Henning Makholm Feb 29 '12 at 23:57
@Henning: Ah, yeah I misread that. Thanks. – Brandon Carter Mar 1 '12 at 2:34
L = {an bm | n > m} is not regular language.


Yes, the problem is tricky at first few try and deserve vote-up.

Pumping Lemma a necessary property of regular language is tool for formal proof that language is not regular language.

Formal definition: Pumping lemma for regular languages

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three sub-strings), satisfying the following conditions:

|y| ≥ 1
|xy| ≤ p
for all i ≥ 0, xyiz ∈ L


Suppose, if you choose string W = an bm where (n + m) ≥ p and n > m + 1. Choice of W is valid but this choice you are not able to show that language is not regular language. Because with this W you always have at-least one choice of y=a to pump new strings in language by repeating a for all values of i (for i =0 and i > 1).

Before I writing my solution to proof the language is not regular. Please understand following points and notice: I made bold every string w and all i in formal definition of pumping lemma above.

Although with Some Sufficiently large W in language you are able to generate new string in Language but NOT possible WITH ALL! There are many possible choices for W(below in my proof) with that you can't find any choice of y to generate new string in language for all i >=0. So because every Sufficiently large W not able to generate new string in language hence language is NOT regular.


read: what pumping lemma formal definition says

Proof: using pumping lemma

Step (1): Choose string W = an bm where (n + m) ≥ p and n = m + 1.

Is this choice of W is valid according to pumping lemma?

Yes, such W is in language because number of a = n > number of b =m . W is in language and sufficiently large >= p.

Step (2): Now chose a y to generate new string for all i >= 0.

And no choice is possible for y this time! Why?

First, it is essay to understand that we can't have b symbol in y because it will either generate new strings out of pattern or in resultant string total number of b will be more than total number of a symbols.

Second, we can't chose y = some a's because with i=0 you would get a new string in which number of a s will be less then number b s that is not possible in language.(remember number of a in W was just one more then b so removing any a means in resultant string N(a)=N(b) that is not acceptable because n>m)

So in we could find some W those are sufficiently large but using that we can't generate new string in language that contradict with pumping lemma property of regular language hence then language {an bm | n > m} is not a regular language indeed.

-

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.

-