Computation Theory: Module 1 Finite Automata

Introduction:

This is the start of the theoretical portion of reverse engineering.  For this portion you will need to have a basic understanding of logical arguments and some ideas about mathematical proofs.  If you are unsure if you have the necessary background my suggestion is to start reading until you get lost.  When you get lost think about where you’re getting lost at and review the proper material to help you find your way.  If you don’t know why you’re getting lost or don’t know where to look for material to help contact me and I will do what I can to aid you.

Getting Started:

I am going to recommend reading the book Introduction to the Theory of Computation by Michael Sipser for this portion of our education.  I decided to use this book as a reference because it shows up in many computer science courses on computation and complexity.  There is also a nice introduction to mathematical problem solving and proofs in the beginning of the book.

We are going to start with Chapter 1 of the book and go through the entire text.  I will try to motivate each new topic by how it relates to reverse engineering.  The first topic, finite automata, plays a role in compiler design which we will need to understand in great detail.  With that in mind lets get started.

Finite Automata:

We have a formal definition for finite automaton from the text:

A finite automaton is a 5-tuple (Q, Σ, δ, q₀, F) with the following properties:

• Q is a finite set of states.
• Σ is a finite alphabet.
• δ: Q x Σ → Q is the transition function.
• q₀ ∈ Q is the start state.
• F ⊆ Q is the set of accept states.

A 5-tuple is a collection of five objects.  Lets break this definition down by matching it up to a finite automaton state diagram.

The set of states Q = {S₁, S₂}.  The alphabet Σ = {0, 1}.  The start state q₀ = S₁ denoted by the arrow from the left with no source. The accept states F = {S₁} denoted by the dual circles.  The transition function is telling us where each arrow goes based on the starting state and the alphabet.  As a reminder Q x Σ means one entry from Q and one entry from Σ and δ will give us back an element of Q.  Lets take S₂ from Q and 0 from Σ, then δ(S₂, 0) = S₁. Because if we start at state S₂ and follow the arrow labeled 0 starting at S₂ the arrow takes us to S₁.

We should now be able to construct a state diagram given a formal definition, and a formal definition given a state diagram.

Exercise:  Let M be a finite automaton with the following definition: Q = {A, B}, Σ = {a, b}, q₀ = A, F = {A, B}, δ(A, a) = A, δ(A, b) = B, δ(B, b) = A, δ(B, a) = B draw the corresponding state diagram.

Properties of Finite Automata:

Now that we know what a finite automata is lets talk about some properties.  If a sequence of elements of the alphabet Σ ends at the accept state the string is accepted.  If not then the string is rejected.  In our example above the string 111 would be accepted, as would all finite strings of all 1’s.  This is because all of the strings would loop back to S₁ over and over again. On the other hand if we had the string 10111111 the string would be rejected.  We would loop once on S₁ then transition to S₂ and loop there until the end of the string. Because S₂ is not an accept state the string is rejected.

The set of all possible strings that will end on S₁ is called the language of the machine. From the exercise before this section we know that any string consisting of a’s and b’s will be accepted by M since F = {A, B}. Thus the language of M is the set of all possible strings of a’s and b’s. The language a machine accepts is always unique.

Exercise: Create a state diagram of at least three states and three alphabet elements.  Label the start state and the accept states and the transitions between the states.  Once you have created the diagram write the formal definition of the finite automata.  Then determine what language the automata will accept.

Bonus Exercise:  See if you can prove if the language of a finite automata has to be finite or can it be infinite?

The illustration in this post comes from wikipedia.