# Proving this language is not regular

Let

$$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$

I have been trying to get a start on this proof for a long time now with no success. What would be a good approach to proving this language is not regular? Is it even possible to prove this? Why is this language problematic to disprove using Pumping Lemma?

I appreciate any help with this.

-

Let $R$ be the regular language generated by the regular expression $bc^*d^*$; then

$$L\cap R=\left\{bc^nd^n:n\ge 0\right\}\;.$$

If $L$ were regular, $L\cap R$ would also be regular. But you can use the pumping lemma to prove that $L\cap R$ is not regular in much the same way you use it to prove that $\left\{c^nd^n:n\ge 0\right\}$ is not regular.

The problem with trying to use the pumping lemma directly on $L$ is that if $i\ne 1$, there is no restriction on $j$ and $k$. Suppose that the pumping length is $p$, and you try to pump with $w=bc^pd^p$. The pumping lemma gives you the usual decomposition $w=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. It’s entirely conceivable that $x$ is the empty string and $y=b$, in which case you can’t get a contradiction: $xy^kz=b^kc^nd^n$ is in $L$ for all $k$.

Added: One of the most familiar non-regular languages is $L_D=\left\{c^nd^n:n\ge 0\right\}$, and the definition of $L$ has some similarity to this, so I immediately thought of trying to use the non-regularity of $L_D$ to prove the non-regularity of $L$. I know that the class of regular languages is closed under intersection, so I know that if I can find a regular language $R$ such that $L\cap R$ is not regular, then $L$ cannot be regular either. My first hope, then, would be to find a regular $R$ such that $L\cap R=L_D$, since I know that $L_D$ isn’t regular. Unfortunately, I can’t quite do this: the part of $L$ that looks as if it might cause trouble for regularity is $\left\{bc^nd^n:n\ge 0\right\}$, every word of which has that $b$ at the front. Still, this part of $L$ looks an awful lot like $L_D$; let’s assume for the moment that it’s enough like $L_D$ that I’ll be able to show without too much trouble that it’s not regular, and let’s ask whether it’s the intersection of $L$ with some regular language.

I want a regular language $R$ such that $L\cap R$ contains just the members of $L$ that have exactly one $b$, so $R$ must contain only words that start with a single $b$. I know that all words of $L$ are in the regular language described by the regular expression $b^*c^*d^*$, so why not just restrict it further to the language described by $bc^*d^*$? That’s certainly regular, and intersecting $L$ with it removes all words of $L$ that start with more than one or no $b$’s. What’s left is exactly $\left\{bc^nd^n:n\ge 0\right\}$.

And now, finally, I worry about whether I can actually show that this language is not regular; a little thought convinces me that the pumping lemma can be used almost exactly as it can with $L_D$.

If you happen to know that regular languages are preserved under homomorphisms, you avoid the pumping lemma altogether by applying to the homomorphism that $\left\{bc^nd^n:n\ge 0\right\}$ the homomorphism that sends $b$ to the empty word and $c$ and $d$ to themselves; this sends $\left\{bc^nd^n:n\ge 0\right\}$ to $L_D$, and since $L_D$ is not regular, $\left\{bc^nd^n:n\ge 0\right\}$ cannot be regular either, and hence $L$ cannot be regular.

-
+1 Thanks for the reply! Very helpful example. I have a question, how does it make sense to define the intersection of L and R? what is the logic behind that? –  Epsilon Jan 29 at 2:46
@MHZ: $L$ and $R$ are just sets, so we can certainly talk about their intersection. In fact they are both subsets of $\{a,b,c\}^*$, so their intersection is even a language over the same alphabet. Are you asking why this particular intersection occurred to me? –  Brian M. Scott Jan 29 at 2:48
Yes, can you please explain your thought process of seeing that we need to prove that the following language is not regular: L={bicjdk∣i≥0,j≥0,k≥0, if i=1 then j=k} and coming up with a whole new language defined as L intersection R to help disprove? –  Epsilon Jan 29 at 2:53
@MHZ: Oops! I just discovered that I mistyped throughout my answer: I had $a,b$, and $c$ instead of your $b,c$, and $d$. I’ve fixed that; take another look and see if it makes better sense now. If you still wonder how I came up with $R$ and $L\cap R$, we can go into it then. –  Brian M. Scott Jan 29 at 3:00
@MHZ: Let me add that to my answer, since it might get a little long. Give me a few minutes. –  Brian M. Scott Jan 29 at 3:31
show 1 more comment