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