# Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?

Show if $$L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$$ is regular or not.

My attempt:

I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of regular languages is regular".

Assuming $$L$$ is regular. I already know that $$S=\{ab^* c^*\}$$ is regular. I'll now look at the intersection $$L \cap S$$.

$$(\{a^mb^nc^n \mid m,n \geq 0\}\cap \{ab^* c^*\}) \cup (\{b,c\}^*\cap \{ab^* c^*\})$$ $$\{ab^nc^n \mid n \geq 0\} \cup \emptyset = \{ab^nc^n \mid n \geq 0\}$$

Which is not regular according to Pumping lemma. Is this idea correct?

• Yes your idea is correct and is a good way to go. Just a detail: $S$ should be defined as $S = ab^*c^*$, not $S = \{ab^*c^*\}$ (or maybe $S = \{a\}\{b\}^*\{c\}^*$ if you want to show the difference between regular expression and language). Commented Mar 20, 2021 at 19:34
• @Nathaniel yes, I should better write like you suggested. Thank you. (If you had an answer I'd tick it) Commented Mar 20, 2021 at 22:10
• I just confirmed your thoughts, it's okay if I don't get an upvote :-) Commented Mar 21, 2021 at 0:29
• We discourage "Please check whether my answer is correct" questions, as they are unlikely to be useful to others in the future.
– D.W.
Commented Mar 21, 2021 at 2:31
• @D.W. But if I don't include my own work, people will tell me to do so or say something like "If you don't include your own work, it looks like you're looking for someone to do your homework" Commented Mar 21, 2021 at 12:04

If $$L$$ is regular then there is a constant $$p$$ such that any word $$uwv \in L$$, where $$|w| \geq p$$, can be decomposed as $$uxyzv$$ so that (i) $$|xy| \leq p$$, (ii) $$y \neq \epsilon$$, (iii) $$uxy^tzv \in L$$ for all $$t \geq 0$$.
Using this, let us prove that your language is not regular. Let $$p$$ be the constant promised by the lemma. Take the word $$ab^pc^p$$, where $$u = a$$, $$w = b^p$$, $$v = c^p$$. According to the lemma, we can decompose $$w = xyz$$ in such a way that $$y \neq \epsilon$$ and $$uxy^tzv \in L$$ for all $$t \geq 0$$. However, if $$y = b^q$$ then $$uxy^0zv = ab^{p-q}c^p \notin L$$, since $$q \neq \epsilon$$.