Class 12: Algorithms on Nondeterministic Finite Automata

Reading

Sections 2.2 of Theory of Computing, A Gentle Introduction

Homework

1. The following machine accepts the language of strings over {a,b,c} whose first two letters are the same as the last two letters.
   
   transform it into a machine that accepts the strings accepted by the original machine, but with their first character deleted.
2. Prove that if L ⊆ Σ^* is accepted by a nondeterministic finite automaton then the language {w ∈ Σ^* | there is an x ∈ Σ for which xw ∈ L} is accepted by a nondeterministic finite automaton. In other words, prove that the language of all strings you get by deleting the first character of a string from L is accepted by a nondeterministic finite automaton.

A Mystery Algorithm on Nondeterministic finite automata

Consider the Mystery Algorithm below:

Input: Machines M1 = (Q1,Σ1,Δ1,s1,W1) and M2 = (Q2,Σ2,Δ2,s2,W2), where Q1 ∩ Q2 = ∅
Output: M = (Q1 ∪ Q2 &cup {s}, Σ1 ∪ Σ2, Δ1 ∪ Δ2 ∪ {(s,e,s1),(s,e,s2)}, s, W1 ∪ W2), where s ∉ Q1 and s ∉ Q2 (i.e. s is a new state)

1. What 5-tuple does this algorithm produce for the input machines given below?

   M1 = ({p0,p1}, {a,b}, {(p0,a,p1),(p1,a,p0)}, p0, {p1}) and M2 = ({q0,q1}, {a,b}, {(q0,b,q1),(q1,b,q0)}, q0, {q0})

2. Draw the diagram for your answer to part 1.

3. Give a concise english description of what the Mystery Algorithm accomplishes in general (i.e. for any two input machines).

From the above excercise you (hopefully!) figured out that the Mystery Algorithm is actually the Union Algorithm, in other words: Given input machines M1 and M2 it produces a machine M such that L(M) = L(M1) ∪ L(M2). So, now we've proved something about languages accepted by nondeterministic finite automata.

Theorem: If L1 and L2 are languages accepted by nondeterministic finite automata, then L1 ∪ L2 is also accepted by a nondeterministic finite automaton.

Concatenation of Languages and a review of set constructor notation

Often we're interested in strings that can be decomposed in certain ways. For example, verbs in english can often be broken up into a root and an ending, like talks or warned or leans. Given the set of roots R = {talk, warn, lean} and the set of endings E = {s, ed}, our possiblities are P = {talks, talked, warns, warned, leans, leaned}. When we form a new set of strings this way, we say that P is the contatenation of R and E. Languages, remember, are simply sets of strings, so we talk about contatenating two languages to form a new language. Each string in the new language is the contatenation of a string from the first language with a string from the second language.

To give a formal definition of the concatenation of two languages we need to recall our set constructor notation, which looks like { A | B }, where the { means "the set of all" and the | means "such that".

For languages L1, L2 ⊆ Σ^*, the contatenation of L1 and L2 (denoted L1L2) is { xy ∈ Σ^* | x ∈ L1 and y ∈ L2}. In other words, L1L2 is the set of all strings of the form xy such that x ∈ L1 and y ∈ L2.

So, for example, if L1 = {aa, ba, c} and L2 = {cc, cb, c}, L1L2 = {aacc, aacb, aac, bacc, bacb, bac, ccc, ccb, cc}. Concatenation of infinite lanugages also makes sense with our definition. For example, if L1 is the language of strings of a's of even length and L2 = {bb, cc}, then:

L1L2 = {bb, cc, aabb, aacc, aaaabb, aaaacc, aaaaaabb, aaaaaacc, ... }

Can you see how bb and cc ended up in the concatenation of L1 and L2? Well, e (the empty string) satisfies our definition of L1. So e concatenated with bb gives bb, and e concatenated with cc gives cc.

A Concatenation Algorithm

Without having defined the concatenation of languages, we looked at examples of tying two machines M1 and M2 together to produce a machine for L(M1)L(M2). Now, can you define an algorithm that does this in general, i.e. for any two machines? So, I want an algorithm that matches the following specification:

Input: Machines M1 = (Q1,Σ1,Δ1,s1,W1) and M2 = (Q2,Σ2,Δ2,s2,W2), where Q1 ∩ Q2 = ∅
Output: Machine M such that L(M) = L(M1)L(M2)

If you think back to specific examples from last lecture, you hopefully see the general strategy. Add e-transitions from the accepting states of M1 to the start state of M2. The start state of the new machine will be M1's start state, and the accepting states are the accepting states of M2. We can describe this formally as:

Input: Machines M1 = (Q1,Σ1,Δ1,s1,W1) and M2 = (Q2,Σ2,Δ2,s2,W2), where Q1 ∩ Q2 = ∅
Output: Machine M = (Q1 ∪ Q2, Σ1 ∪ Σ2, Δ, s1,W2), where Δ = Δ1 ∪ Δ2 ∪ {(q,e,s2) | q ∈ W1}

My claim is that L(M) = L(M1)L(M2). Following our previous discussion, we'll assume this claim is self-evident enough from our experience with this algorithm. To be strictly, formally correct, however, we'd have to prove it. If you accept my claim, then we have the following thoerem:

Theorem: If L1 and L2 are languages that are accepted by nondeterministic finite automata, then L1L2 is

Kleene Star *

One is often interested in strings that are formed by repeatedly concatenating strings from a given language. For example, if you wanted a string of doubled characters, e.g. aabbbbaacc, what you're looking for is a string that's made up of repeated copies of elements of the language {aa,bb,cc}. The operation of "repeated concatenation" from a given language is called the Kleene Star of a language. Somewhat informally, we'll say that the Kleene Star of language L (denoted L^*) is a string of the form x₁x₂ ... x_n-1x_n, where each of the x_i's is in L. Typically, you see this defined in a very different way ... a way that is particularly conducive to proof by induction.

1) e ∈ L^*
2) if x ∈ L^* then xy ∈ L^* for every y ∈ L

A definition like this is called a recursive definition, and it is basically a set of rules generating all the elements of L^*. A few examples will, hopefully, make Kleene Star clear to you:

• {ab}^* = {e,ab,abab,ababab,abababab,...}
• {001,100}^* = {e,001,100,001001,001100,100001,100100,...}
• {1,0,::}^* = {e,1,0,::,11,10,1::,00,01,0::,::::,::1,::0,...}
• {Stop,Go}^* = {e,Stop,Go,StopStop,StopGo,GoStop,GoGo,...}

So, the Kleene Star of a language is the set of all strings consisting of zero or more elements of the language concatenated together.

An algorithm for Kleene star

Hopefully you can see that an algorithm that takes a machine M and produces a machine accepting L(M)^* is not too tricky ... although it might be a tad trickier than you thought, because you need to accept the empty string, even if the original machine doesn't. One way to do this is to have e-transitions from the final states of the original machine back to its start state. This way, we can run the machine repeatedly while processing a string. Of course we won't necessarily accept the empty string with this scheme. Just making the initial state accepting doesn't work, though, because it might lead you to accept some strings you shouldn't. Instead, we add an e-transition to a new state, and that will be our final state. See if you can produce this algorithm on your own before looking at my solution.

Algorithm Kleene Star
Input: Machine M = (Q, Σ, Δ, s, W)
Output: M' = (Q ∪ {$}, Σ, Δ ∪ {($,e,s)} ∪ {(q,e,$) | q ∈ W}, s, {$}), where $ ∉ Q, i.e. $ is a new state

Now, I claim that L(M') = L(M)^*. I really ought to prove it, of course. However, for the moment why don't you just try it on an example or two and convince yourself that it really works.

What do we know about NonDeterministic Finite Automata?

So what do we know about languages accepted by NonDeterministic finite automata? We know that:

1. the union of two languages accepted by nondeterministic finite automata is accepted by a nondeterministic finite automaton
2. the concatenation of two languages accepted by nondeterministic finite automata is accepted by a nondeterministic finite automaton
3. the Kleene Star of a language that's accepted by an automaton is accepted by an automaton

How does this compare to deterministic finite automata? We don't about contatenation or Kleene star for deterministic finite automata. And while for deterministic machines we know about intersection and complement, we have no idea about those for nondeterministic machines. So, clearly there are some gaps in our understanding of both kinds of machines. The one thing I know for sure, however, is that if a language can be accepted by a deterministic finite automaton it can also be accepted by a nondeterministic finite automaton. Can you see why?