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?

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≤ 0See 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, abaab, 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!!