Suppose I wanted to construct a finite automaton to accept the languages {a^{k}b^{k} | 0 ≤ k ≤ 1}, {a^{k}b^{k} | 0 ≤ k ≤ 2}, and {a^{k}b^{k} | 0 ≤ k ≤ 3}. It turns out not to be so hard .. although a bit tedious.
{a^{k}b^{k} | 0 ≤ k ≤ 1} | {a^{k}b^{k} | 0 ≤ k ≤ 2} | {a^{k}b^{k} | 0 ≤ k ≤ 3} |
Presumably you see the writing on the wall: the language of strings of the form a^{k}b^{k} for k up to some bound can be accepted by some finite automaton, but the number of states keeps growing as the bound grows. If you're clever you should be able to see how many states would be needed if k was bounded by, for example, 100. But what about the language {a^{k}b^{k} | 0 ≤ k}? In other words, what if we didn't have any upper bound on k? Well then we'd need infinitely many states, and that's precisely what we're not allowed to have with a finite automaton! And that, though it's not a proof, is why {a^{k}b^{k} | 0 ≤ k} cannot be accepted by a finite automaton.
It turns out to be pretty easy to do this kind of thing. For example, if L is a language let's let double(L) denote the language of doubles of strings in L, i.e. double(L) = { ww ∈ Σ^{*} | w ∈ L}. Then it turns out that double(L) cannot necessarily be accepted by a finite automaton, even if L can. For example if L = {w ∈ {a,b}^{*} | |w| is even}, then double(L) cannot be accepted by any finite automaton. Same problem as before: a machine would need infinitely many states to "remember" the first half of the string to make sure the second half matched for strings of any size. How about strings over the alphabet {a,b,:} such that the strings of a's and b's betwen :'s are in srted order? Also not acceptable with a finite automaton!
Anyway, the moral of the story is that when we prove that, for instance, the Kleene Star of a language acceptable by a NDFA is also acceptable by a NDFA, we should surprised and impressed!
Proposed theorem: If a language L is accepted by a nondeterministic finite automaton, then L is accpeted by a nondeterministic finite automaton.
Proof requires an algorithm with specification:
Input: Nondeterministic Machine M = (Q,Σ,Δ,s,W)
Output: Nondeterministic Machine M' such
that L(M') = L(M)
Notice, I haven't given the algorithm here, only the specification of the algorithm. If I can provide an algorithm that meets this specification, I've proved the theorem. Hopefully it's clear to you why such an algorithm would be a proof (quotes from the theorem statement are in red):
If a language L is accepted by a nondeterministic finite automaton then there is a machine that accepts it, which we'll call M. We run our algorithm with M as input, and get back a machine M' that accepts L(M) = L. Thus, L is accepted by a nondeterministic finite automaton.
Proof requires an algorithm with specification: ?
Proof requires an algorithm with specification: ?
Proof requires an algorithm with specification: ?
Proof requires an algorithm with specification: ?