Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Many thanks in advance.

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
+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 '13 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 '13 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 '13 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 '13 at 3:00
1  
@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 '13 at 3:31
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.