Computation Theory: Module 2 Computation and Operations

Introduction:

In the last module for computation theory we went over what a finite automaton is.  We also learned two representations for them, the formal definition and a state diagram.  We set up what the language of a finite automaton M is and what it means for M to accept or reject a string.  In this module we are going to go over what we mean by computation and some operations on the languages of finite automata.

Computation:

Let M be a finite automata.  In the last module we stated that M accepts a string if that string ends on an accept state of M.  That’s not the whole story though.  Lets break down how a string interacts with M even more.

First we need to consider how the string relates to M.  Let Σ = {0, 1} be the alphabet of M.  Can we say that an arbitrary string will be valid for M as long as it is only 0’s and 1’s?  Think about that for a second and think about what could go wrong if you allow any string of 0’s or 1’s.  After you’re satisfied you’ve thought about it thoroughly keep reading.

Given a string s = 10001 lets consider what’s actually happening.  We begin at the start state q0  and the first question should be is there a transition δ(q0, 1) defined?  If not then s is not a valid string for M.  We need to have a defined transition from whatever state we are on to another state at each stage of s for the string to be valid for M.

If each step of s is a valid transition then we have a sequence of states in M that is defined by the string s.  In the case of our string s if we have a sequence of states S0S1S2S3S4 such that for each state Si is in the set of states Q, if S0 = q0 and S4 is an accept state then M accepts s.  Which in plain language states that if we begin at the start state, each transition defined by s is a valid transition, and we end at an accept state then M accepts the string s.

M recognizes a language L if L = {s | M accepts s}.  That is M recognizes L if L is a set containing strings that M accepts and only strings that M accepts.

Definition: A language is called a regular language if some finite automata 
recognizes it

Operations On Finite Automata:

Now we are going to discuss what operations we can perform on the languages of finite automata.  Try to formulate what is meant by an operation on finite automata languages.  Think about that for a little bit before continuing.

Consider two integers, 3 and 2.  We have the operations from basic mathematics: addition, subtraction, multiplication, and division.  These operations are defined on integers and so we may use them with 3 and 2.  We want to be able to do the same sort of thing with finite automata.  At the basic level we are going to treat a language of a finite automata as a single entity and combine it with a language of another finite automata (or even itself).  Just like 3 + 2 = 5 is combining 3 and 2 to make a new integer 5.

Given two languages A and B we define the following operations:

  • Union: A ∪ B = { s | s ∈ A or s ∈ B}
    • This means that given any string in A ∪ B the string is in the language A or the string is in language B.
  • Concatenation: A ο B = {rs | r ∈ A and s ∈ B}
    • This means that given any string w in A ο B we can decompose w into a string r from A followed by a string s from B.
  • Star: A* = {s1s2 . . . sk | k > 0 and sj ∈ A for all j}
    • This means that we take k strings from the language A and tack them on the end of the previous string.

Exercises:

Reading the definition of the operations isn’t enough to get a thorough understanding of what is happening.  So your exercises are to take the following finite automaton definitions and see if you can determine the languages for each.   Then once you are comfortable with the languages apply each operation to them and see what you come up with.

Let M1 be the finite automaton with the following definition: Q = {S0, S1, S2}, Σ = {0, 1, 2}, {δ(S0, 0) = S2, δ(S0, 1) = S0, δ(S0, 2) = S1, δ(S1, 0) = S0, δ(S1, 1) = S2, δ(S1, 2) = S1, δ(S2, 0) = S2, δ(S2, 1) = S0, δ(S2, 2) = S1}, q0 = S1, F = {S1, S2}.

Let M2 be the finite automaton with the following definition: Q = {R0, R1, R2}, Σ = {a, b, c}, {δ(R0, a) = R2, δ(R0, b) = R0, δ(R0, c) = R1, δ(R1, a) = R0, δ(R1, b) = R2, δ(R1, c) = R1, δ(R2, a) = R2, δ(R2, b) = R0, δ(R2, c) = R1}, q0 = R1, F = {R1, R2}.

Before you do anything would you say that M1 and M2 are different finite automata or that they are the same?  Now draw the state diagram for each and see if that changes your view any.

Conclusion:

There are some subtle concepts in this module.  Such as looking at a complex collection and treating it as a single entity we can perform operations on.  This is a common theme in mathematics.  It takes some getting used to but the more you work with that concept the more natural it becomes.

I encourage you to get in the habit of dealing with the formal definitions rather than relying on the state diagrams.  State diagrams are great tools for visualizing things but they aren’t a tool for making a formal argument.

Lastly work with the concepts and structures we are discussing.  Make your own finite automata definitions, diagrams, languages, operations, etc.  This will increase your understanding of the structure.  You will make mistakes and things won’t work how you think they should sometimes.  But you will learn more from that than you will from reading what I have written.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s