# Class 13: Reprising Proof and Algorithms

None.
Homework
Printout the homework and answer the questions on that paper.

A note on languages that can't be accepted by finite automata
Just to clear something up before we go on. We've seen so many examples of languages that are accepted by deterministic or non-deterministic finite automata, that we might be inclined to think that any language can be accpeted by a finite automaton. In fact, most languages cannot ... it's just that we've been focusing on languages that can. You should be pleasantly surprised when a lanugage turns out to be acceptable by an finite automaton. Anyway, let's look at a simple language that can't be accepted by a finite automaton just to see what the limitations are.

Suppose I wanted to construct a finite automaton to accept the languages {akbk | 0 ≤ k ≤ 1}, {akbk | 0 ≤ k ≤ 2}, and {akbk | 0 ≤ k ≤ 3}. It turns out not to be so hard .. although a bit tedious.

 {akbk | 0 ≤ k ≤ 1} {akbk | 0 ≤ k ≤ 2} {akbk | 0 ≤ k ≤ 3}

Presumably you see the writing on the wall: the language of strings of the form akbk 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 {akbk | 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 {akbk | 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!

Proof
In this class, as we've gone over many times, proof always ends up being an algorithm. You have a thoerem that claims that such and such a class of languages can be accepted by a DFA? You prove the claim by giving an algorithm that generates the machine for each language in the class. However, while we've had lots of practice following algorithms, and even devising them on our own, we've had no real practice in looking at a proposed theorem and figuring out which algorithm we'll need to devise in order to have a proof. When writing programs, you should always start with a clear idea of what task the program is supposed to accomplish - i.e. a specification for the program. Similarly, before devising an algrothim, you should have a specification. What kind of input should it take, what kind of output should it produce - i.e. what's the property you're looking for in your output. Let's look at an example:

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.

In-class Problems
The following excercises were done in-class. You're given the statement of a proposed theorem, and you're supposed to write the specification of the algorithm that would prove the theorem. We're looking for the specification only, not the actual algorithm.

1. Proposed Theorem If languages L1 and L2 are both accepted by nondeterministic finite automata, then L1 ∪ L2 is accpeted by a nondeterministic finite automaton.

Proof requires an algorithm with specification: ?

2. Proposed Theorem If language L is accepted by a deterministic finite automaton, then L* is accepted by a deterministic finite automaton.

Proof requires an algorithm with specification: ?

3. Given a language L ⊆ Σ*, let Prek(L) denote the language of all length k prefixes of strings in L. For example, if L = {abbc, ca, bacc, a} then Pre2(L) = {ab,ca,ba}.
Proposed Theorem If language L is accepted by a nondeterministic finite automaton, then for any k > 0 Prek(L) is accepted by a nondeterministic finite automaton.

Proof requires an algorithm with specification: ?

4. Proposed Theorem For any k > 0 and alphabet Σ, the language of all strings over Σ of length at least k is accepted by a non-deterministic finite automaton.

Proof requires an algorithm with specification: ?

Christopher W Brown