Date: Wed, 08 Jan 1997 20:36:50 GMT Server: NCSA/1.4.2 Content-type: text/html
CSE 322 Winter 1996: Assignment 9 Solution Set
Let where
for all
,
,
Behavioral Lemma:
For all ,
,
,
, and
,
if and only if
and
.
Assume L is regular, and let
be a DFA that accepts L. Suppose Q contains n states.
Consider the computation of M on any string of length n or more.
Because there are only n total states, some state will be visited more
than once during the computation. For example, when M processes the
string
, the computation looks like this:
for some ,
, and
.
Because we visit the same state twice, we can remove
from the string and still end in the same state:
This means that . However,
. Also, note that
since
and
,
2n+1 must be greater than j-i. This means that
. So
falls strictly between
and
, two consecutive perfect squares.
Therefore,
is not a perfect square and
. This is a contradiction,
so L must not be regular.