proof by contradiction

• Previous message: Mark \(The WannaBe\): "Testing for acceptance of Kleene closure of alphabet"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Sun, 17 Oct 2004 18:00:18 +0200

Hi

I have tried to come up with a wannabe attempt of "proof by contradiction".
Being able to do proofs of this kind seems to be an art from the dark land
of computer science where a wannabe cannot walk. But I will fight my
wannabeness and try to do my best anyway. Again I have taken a problem from
"Introduction to Automata Theory, Languages, and Computation" by Hopcroft et
al. it is the exercise 4.3.5. The problem is given between the
lines, --#--#--, and my wannabe answer is given between the lines, --*--*--.

--#--#--
Give an algorithm to tell, for two regular languages L1 and L2 over the same
alphabet SIGMA, whether there is any string in SIGMA* that is in neither L1
nor L2.
--#--#--

--*--*--
Let M1 be a DFA accepting L1 and let M2 be a DFA accepting L2. Let n_1 be
the number of states in M1 and let n_2 be the number of states in M2. Let
n_1>= n_2.

An algorithm to solve this problem would loop through all s strings w from
SIGMA* in the range 0<=|w|<2n_1-1 and for each selected string in this range
test if neither M1 nor M2 accepts the string. If just one such string is
found where neither M1 nor M2 accepts then the loop ends and return true
otherwise the algorithm returns false.

The reasoning for it is enough to test all strings in the range
0<=|w|<2n_1-1 goes like this. The longest possible path in a DFA M having n
states where each state is visited only once is n-1. The longest possible
cycle in M where each state is visited only once is n. To test if two
languages are equivalent including all possible cycles you would need to
test all strings w of SIGMA* up to length 2n-1 (this is the sum of the
longest possible path, n-1, and the longest possible cycle, n, where each
state is visited only once during the cycle, meaning that at best every
transition have been traversed one time). The lower bound 0 is to test if
neither M1 nor M2 accepts the empty string.

We will prove that it is enough to test strings of length up to 2n_1-1 by
using proof by contradiction. Let M1 and M2 be defined as above. Assume that
M1 and M2 accepted the same strings w of SIGMA* in the range 0<=|w|<=2n_1-1
but that there exists a string x from SIGMA* of length |x|> 2n_1-1 where M1
accepts but not M2.

We know that for strings in the range 0<=|w|<=2n_1-1 then M1 and M2 are
equivalent, i.e. we know that if we start in the start state of M1 and M2
then no matter which path we follow in M1 to an accepting state then there
will be an equivalent path in M2 to an accepting state. We know that strings
w from SIGMA* of length 0<=|w|<=2n_1-1 will traverse all possible paths,
including cycles, of the M1 and M2 at least 1 time. But since x is in M1 and
not in M2 with a length |x|>2n1-1 then there must a unique traversal of
transitions to an accepting state in M1 which have not been traversed by any
string w of SIGMA* in the range 0<=|w|<=2n_1-1, but that is in contradiction
with that every path had transition had been traversed at least once in the
range 0<=|w|<=2n_1-1. So we have shown by prove by contradiction that we
only need to test in the range 0<=|w| <=2n_1-1.

Because we choose n_1>=n_2 then the same reasoning applies for M2 as well.
--*--*--

Is this wannabe attempt of a proof by contradiction making any sense? I am
sure that I did something wrong and I guess there is a more straight way to
prove what I have tried to prove. I have tried to follow the rules i.e.
assume the opposite of what I want to be true and then show that this leads
to a contradiction. In the proof I implicitly use the fact that if there for
every path leading to an excepting state in DFA A exists an equal path in
DFA B leading to an accepting state and vice versa then A and B are
equivalent, but I do not know if I succeeded in using that knowledge
appropriately.

Kind regards
Mark (The WannaWannaBe of Computer Science)

• Previous message: Mark \(The WannaBe\): "Testing for acceptance of Kleene closure of alphabet"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]