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 ≤ 3} 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!
that we want to "convert" to a deterministic machine? The clever way to go about it is to keep track of all the different possible states you could be in for every new character you read.
| When we start, q0 is the only possible state. |  |
||
| When you're in q0 and you read a, you could either go to q0 or q1. |  |
When you're in q0 and you read b, you could only go to q0. |  |
| When you're in q0 or q1 and you read a, you could go to either q0 or q1. |  |
When you're in q0 or q1 and you read b, you could go to either q0 or q2. |  |
| When you're in q0 or q2 and you read a, you could go to either q0 or q1. |  |
When you're in q0 or q2 and you read b, you could only go to q0. |  |
Each state of this machine is labeled with all the possible states from the original nondeterministic machine that we could be in. So if we've read aab, the fact that we're in state {q0,q2} tells us that we could be in either state q0 or q2 of the original machine, depending on which computation path we took. Now, the definition of acceptance for nondeterministic machines is that at least one of the computational paths leaves you in an accpeting state. Thus, our only accepting state would be {q0,q2}, since it's the only state that includes an accepting state from the original machine. So, our final machine is:
Input: a nondeterministic finite automaton
M = (Q,Σ,Δ,s,W), which has no
e-transitions
Output: a deterministic finite automaton M'
such that L(M') = L(M). M' is given by:
M' =
(2Q,Σ,δ, {s}, {R ∈
2Q | R ∩ W ≠ ∅})
, where
δ(H,x) =
{q ∈Q | (p,x,q) ∈ Δ for some p
∈ H}