Machine M1 | Machine M2 |
Machine M3 accepting L(M1) | Machine M4 accepting L(M2) |
Hypothesis: If a language L is accepted by some finite automaton, there exists a finite automaton that accepts L.
Proof: Consider the following algorithm:
Input: Machine MI claim that it's obvious that the language accepted by M' is the complement of the language accepted by M, i.e. I claim that L(M') = L(M). So, going back to our hypothesis, give the name M to the machine accepting L. From input M, the above algorithm produces machine M' that accepts L, which proves the hypothesis.
Output: Machine M' produced by making all the accepting sates of M non-accepting and making all the non-accepting states accepting.
This isn't quite a proof that a pedantic mathematician would accept, because we haven't proved our claim that the machine M' produced by our algorithm accepts L(M). On the other hand, while the hypothesis is not what most people would consider self-evident, the correctness of the algorithm is. So for most people, the algorithm is enough of a proof. If you don't find it convincing, here's a proof that the algorithm does what I say it does:
Proof that the algorithm produces machine M' that accepts L.
Since the states, start state and transitions of M and M' are the same, after processing a given string w both machines will end up in the same state, let's call it "qi". If qi is an accepting state in M it is non-accepting in M', and if qi is a non-accepting state in M it is accepting in M'. Thus, the two machines make opposite decisions for any input string w, which proves that L(M') = L(M).
There are a few important points here. First of all, notice that how much proof is required depends on what is "self-evident", and that might change from one person to the next. In the end, proof is all about convincing someone. Secondly, the process that we just went through is what most of this course is going to be about: notice a pattern, make a hypothesis, prove the hypothesis. In fact, most proofs will look like the above: the proof is an algorithm and --- if you're picky/precise enough --- a proof of the algorithm's correctness.
Machine M5 accepting the intersection of L(M3) and L(M2) | Machine M5 rearranged to look cleaner! |
Machine: M3 M2 M5 -- -- ---- In state: q1 p1 -------> q1p1 | | | Reads: c c c | | | V V V Moves to: q2 p0 q2p0Can you see how the accepting states were selected? Once again, the way we accomplished this makes us think that we could do the same for any two machines, which leads us to the following:
Hypothesis: If languages L1 and L2 are accepted by finite automata, there exists a finite automaton that accepts the intersection of languages L1 and L2.
We could prove this the same way we proved our hypothesis concerning complement languages, by describing an algorithm that would take two machines as input and provide as output a new machine that accepted the intersection of the languages accepted by the two input machines. However, we're going to have to do some more work before we're able to define complex algorithms like this precisely.