regular language (or not)

Question

I have the language $L = \{ abc^nbc^mba\ |\ m,n \in N, n \geq m \}$ Could this ever be regular? How can we keep track of $n$ and $m$? I have no way to use memory in my Finite Automata so this cannot possibly be regular? Or am I way off here? No matter how I construct at FA I cannot come over the fact that at any time I wish to loop for $c$ I cannot decide how many times I should be able to do so.

Answer 1

HINT: Your intuition is correct: $L$ is not regular. This is easily proved using the pumping lemma for regular languages.

Suppose that $L$ is regular, and let $p$ be the pumping length. Let $w=abc^pbc^pba$. Then we can write $w=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. In particular, taking $k=0$ we see that $xz\in L$.

• Show that no matter how $x$ and $y$ are chosen so that $|xy|\le p$, $|y|\ge 1$, and $xy$ is an initial segment of $w$, the word $xz$ is not in $L$.

This contradiction shows that $L$ is not regular after all.