In: Computer Science
Prove that {anbamba2m+n:n,m≥1} is not regular using pumping lemma
To prove that
is not regular, use the pumping lemma for regular languages as
follows.
Let the pumping length be
. Consider the word
which has length at least p, which is in the language as per the
definition of the language with
.
Consider any breakup of the word
. Then xy must consist of only 'a's from the first block, otherwise
it's length will exceed p. Hence
. Now consider the pumped down word
. Then this word has
, but the number of 'a's in the last block is
. As
, this means
, hence
. This means that the word w' doesn't satisfy the property to be in
the language, hence
.
This proves the language is not regular using the pumping lemma for regular language. Comment in case of any doubts.