Computation - Automaton to Patterns

A brief Summary

So far we have seen 3 ways in which to talk about a language over given alphabet. These are:

1. Set-theory


2. Regular Expressions (patterns)


3. NFAs and DFAs (automatons)

Regular Expressions is the best way to talk about a language if we wish to communicate our language to a computer. Yet, for some problems, an automaton is the easiest thing to come up with.

However, how are automatons and regular expressions connected?

A connection is made!

Say for example we have a certain DFA for a given language, here we say take a look at the algorithm that takes this DFA and creates a regular expression from it!

Sometimes we don’t always need to have an algorithm because a pattern is easily established just from looking at the automaton:



As you can hopefully, clearly see, this automaton describes the language of a word that must begin with the letter ‘a’, and then may have an arbitrary number of ‘b’’s. A pattern that describes the same language is:

• ab*

Yet, if this had been a far more complicated automaton – sadly – then we have to use a horribly long algorithm.

Note: if you are given an NFA and told to find the pattern, find the DFA equivalent first!

The Algorithm

I think its time to have a look at an example, yes? Well, take a look at the following automata:



Ugh, that just looks horribly doesn’t it?  We have 2 accepting states, as well as transitions criss-crossing everywhere.

For the algorithm to work, we have to find all the words that make the automata finish in one of the 2 accepting states. Therefore we can say:

• When starting in state 0 we finish in state 0. This is called ζ_L→00.


• When starting in state 0 we finish in state 2. This is called ζ_L→22.

From this we have made an equation. Namely the fact that the language ζ recognized by the automaton is:

• ζ = ζ_0→0 U ζ_0→2

This simplifies things a little. Now all we have to do is to calculate 2 languages. To simplify this further, what we do is to ‘remove’ one of the states from the equation.

For example, to get ζ_0→0 we can do one of the following:

• We don’t use state 2 at all,


• We go from state 0 to state 2. Loop round to state 2 as often as needed, and then return back to state 0.

So what we’ve done is to remove state 1 from the equation.

Let’s get back to the real question at hand now. Let’s say that all words that follow a path that goes from state 0 to state 0 whilst only using states 0 and 1 (but not state 2) make up the language ζ_0→0^{≤ 1}. This means that any word that follows a path from state 0 to state 0 satisfies one of the following:

• It is either an element of ζ_0→0^{≤ 1},


• It is an element of ζ_0→2^{≤ 1} · (ζ_2→2^{≤ 1})* · ζ_2→0^{≤ 1}

From this, believe it or not, we have an equation! This equation is related to the ζ_0→0 above:

ζ_0→0 = ζ_0→0^{≤ 1} U ζ_0→2^{≤ 1} · (ζ_2→2^{≤ 1})* · ζ_2→0^{≤ 1}

Lets explain where this comes from. But, before we do, note that ζ_0→0 is actually ζ_0→0^{≤ 2}. From this we can show 3 things:

• ζ_j→i^{≤ k}

In this case, ‘j’ is the state we start in, ‘I’ is the state we have to end in, whilst ‘k’ is the states that we are only allowed to use. If we compare the above to ζ_0→0^{≤ 2} then we get:

• j = 0


• i = 0


• k = 2

So, when we need to create the equation for ζ_0→0^{≤ 2}, we have to do ‘k-1’, that is, we are not allowed to use state k. This is helpful for when it is hard to properly read of a pattern, and you need to split a language up even further. From this we can say that:

• ζ_j→i^{≤ k} = ζ_j→i^{≤ k-1} U ζ_j→k^{≤ k-1} · (ζ_k→k^{≤ k-1})* · ζ_k→i^{≤ k-1}

If you look carefully, you can see how this relates to the above equation for ζ_0→0.

OK, so let’s start to apply this algorithm to the given automaton. Firstly, we shall use the equation for ζ_0→0.

• ζ_0→0^{≤ 1}. Defines the language that says: “get from state 0 to state 0, only using states 0 and 1.” The quick and simple answer is – we can’t. Therefore we have:
  ζ_0→0^{≤ 1} = {ε}


• ζ_0→2^{≤ 1}. Defines the language that says: “get from states 0 to 2, using only states 0 and 1.” This can be done in 2 ways, either directly with letter ‘b’, or via state 1 using ‘ab’ and ‘cb’. Therefore we have:
  ζ_0→2^{≤ 1} = {b, ab, cb}
  
  


• ζ_2→2^{≤ 1}. As you can probably see, this is a little more complicated. In order to find the language here, we need to apply the algorithm again, but this time apply it to ζ_2→2^{≤ 1}. This means we have: ζ_2→2^{≤ 1} = ζ_2→2^{≤ 0} U ζ_2→1^{≤ 0} · (ζ_1→1^{≤ 0})* · ζ_1→2^{≤ 0}See the pattern yet? Anyway, from this we can show that:ζ_2→2^{≤ 0} = {b, ab}
  ζ_2→1^{≤ 0} = {aa, ac, c}
  ζ_1→1^{≤ 0} = {ε}
  ζ_1→2^{≤ 0} = {b}
  
  This gives use the fact that:
  
  ζ_2→2^{≤ 1} = {b, ab} U {aa, ac, c} · {ε}* · {b}
  ζ_2→2^{≤ 1} = {b, ab} U {aa, ac, c} · {ε} · {b}
  ζ_2→2^{≤ 1} = {b, ab, aab, acb, cb}
  
  and then finally we have:
  
  


• ζ_2→0^{≤ 1}. This defines the language of going from state 2 to 0, only using states 0 and 1. Here we can just simply read this one of as {a}.

Now that we have all of this, we can do finish of the equation. So now we can show that:

ζ_0→0 = ζ_0→0^{≤ 1} U ζ_0→2^{≤ 1} · (ζ_2→2^{≤ 1})* · ζ_2→0^{≤ 1}

ζ_0→0 = {ε} U {b, ab, cb} · {b, ab, aab, acb, cb}* · {a}

ζ_0→0 = ζ (ε) U ζ (b|ab|cb) · (ζ (b|ab|aab|acb|cb))* · ζ (a)

ζ_0→0 = ζ (ε|(b|ab|cb)(b|ab|aab|acb|cb)*a)

This now leaves the final part of the initial equation: ζ_0→2^{≤ 2}. Here, since k=i, we can just simplify the algorithm to:

ζ_0→2^{≤ 2} = ζ_0→2^{≤ 1} · (ζ_2→2^{≤ 1})*

The best thing here is that these 2 sub equations have already been calculated for us! So we can just say here:

ζ_0→2^{≤ 1} = {b, ab, cb}

ζ_2→2^{≤ 1} = {b, ab, aab, acb, cb}

Which gives us:

ζ_0→2 = {b, ab, cb} · {b, ab, aab, acb, cb}*

ζ_0→2 = ζ ((b|ab|cb)(b|ab|aab|acb|cb)*)

Now, at long last! Here is the language that is recognized by the given automaton:

ζ = ζ_0→0 U ζ_0→2

ζ = ζ (ε|(b|ab|cb)(b|ab|aab|acb|cb)*a) U ζ ((b|ab|cb)(b|ab|aab|acb|cb)*)

ζ = ζ (ε|((b|ab|cb)(b|ab|aab|acb|cb)*a)|((b|ab|cb)(b|ab|aab|acb|cb)*))

ζ = ζ (ε(b|ab|cb)(b|ab|aab|acb|cb)*(ε|a))

So the pattern that fives the same language is:

ε(b|ab|cb)(b|ab|aab|acb|cb)*(ε|a)

Finally.. this one is over! Next is Patterns to automata!!