Proof:
Assume would be regular. We will show that this leads to
contradiction using the pumping lemma.
Now by the pumping lemma there is an such that we can split each
word which is longer than
such that the properties given by the
pumping lemma hold. Consider
, this is certainly longer
than
. We have that
and we know that
,
hence
can only contain as, and since
it must
contain at least one a. Now according to the pumping lemma
but this cannot be the case because it contains at least one a
less but the same number of bs as
.
Hence, our assumption that is regular must have been wrong.
It is easy to see that the language
Proof:
We apply the same strategy as above. Assume is regular then there
is a number
such we can split all longer words according to the
pumping lemma. Let's take
this is certainly long enough. By the
pumping lemma we know that we can split
s.t. the conditions of
the pumping lemma hold. In particular we know that
![]() |
![]() |
|||
![]() |
![]() |
|||
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
||
![]() |
![]() |
|||
![]() |
![]() |
We conclude is not regular.
Given a word
we write
for the word read backwards. I.e.
. Formally this can be defined as
![]() |
![]() |
|
![]() |
![]() |
Hencce our assumption
is regular must be wrong.
The proof works for any alphabet with at least 2 different
symbols. However, if contains only one symbol as in
then
is the laguage of an even
number of
s and this is regular
.