(iii) We don’t know the decomposition of w into xyz, but since | |
xy m
≤ ,
xy must consist entirely of a’s. Moreover, y cannot be empty.
(iv) Choose i = 0. This has the effect of dropping | y | a’s out of the
string, without affectng the number of b’s. The resultant string has
fewer a’s than b’s, hence does not belong to L.
Therefore L is not regular.
Ì Exam ple 1.8.2: Prove that L a b n k
n
n k
=
>
≥
{
:
}
and
0 is not regular.
Solu tion
(i) We do not know ‘m’, but assume there is one.
(ii) Choose a string w a b
n k
=
, where n > m, so that any prefix of
length ‘m’ consists entirely of a’s, and k = n – 1, so that there is just
one more a than b.
(iii) We do not know the decomposition of w into xyz, but since
| |
,
xy m
≤ xy must consist entirely of a’s. Moreover, y cannot be
empty.
(iv) Choose i = 0. This has the effect of dropping | y | a’s out of the
string, without affecting the number of b’s. The resultant string
fewer a’s than before, so it has either fewer a’s than b’s, or the
same number of each. Either way, the string does not belong to L,
so L is not regular.
Ì Exam ple 1.8.3: Show that L a n
n
= { : is a prime number} is not
regular.
Solu tion
(i) We don’t know m, but assume there is one.
(ii) Chose a string w = a
n where n is a prime number and
| |
xyz n m
= > +1. (This can always be done because there is no
largest prime number). Any prefix of w consists entirely of a’s.
(iii) We do not know the decomposition of w into xyz but since | |
,
xy m
≤
it follows that | z | > 1. As usual, | y | > 0.
(iv) Since | | , | | .
z
xy
>
>
1
1. Choose i xz
=| |. Then |
| | | | | | |
xy z
xz
y xz
i
=
+
= +
( | | ) | |.
1 y xz
Since (1 + | y |) and | xz | are each greater than 1, the product must
be a composite number.
Therefore |
|
xy z
i is a composite number.
Hence L is not regular.
DFA and NFA
95