# Computation – Automaton to Patterns

September 9, 2009 Leave a comment

**A brief Summary**

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

- Set-theory
- Regular Expressions (patterns)
- 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→0}0. - When starting in state 0 we finish in state 2. This is called ζ
_{L→2}2.

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
*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}.

**ζ**. 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→0}^{≤ 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 ‘_{0→2}^{≤ 1}*b*’, or via state 1 using ‘*ab*’ and ‘*cb*’. Therefore we have:

ζ_{0→2}^{≤ 1}= {*b, ab, cb*}**ζ**. 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}_{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:

**ζ**. 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 {_{2→0}^{≤ 1}*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!!