The Finite State Machines And Cellular Automata Philosophy Essay

To design a machine that works according to its own will in a mechanical way or responds automatically is known as Automata Theory. Artificial Intelligence (AI) is the part of computer science which focuses on creating machines and software that can take on behaviors that humans consider intelligent.

Artificial Intelligence is mainly implemented in Cellular Automata and Time Automata. Cellular Automata has created Artificial Intelligence implemented in several machines used in our daily life like computers, cell phones, cars etc. and even an artificial life in the “The Game of Life” Automata. Complex Finite State Machines can also have Artificial Intelligence. They are widely used in software to validate user input. We have discussed implementation of Artificial intelligence in the following types of automata:-

Cellular Automata consists of “cells” in one or two dimensions (rows & columns) and a set of “rules”. Each cell changes its state on the basis of neighboring cells and the set of rules.

Augmentation of the finite automata with the timing constraints is called Timed Automata. It accepts timed words, i.e., time is associated in each symbol. The non- negative numbers are used in time domains.

Turing machine are conceptual mathematical entities that are consist of a tape, a read-write head, and a finite-state machine.

A Finite State Machine (FSM) is a model of behavior using states and state transitions. A transition is a state change triggered by an input event, i.e. transition maps some state-event pairs to other states.

Automata (Introduction)

The word Automata is derived from a Greek word ‘Automation’ which means to design a Machine. We may refer to it as:

A self operating machine or mechanism.

One that responds in a mechanical way.

To design a machine that works according to its own will in a mechanical way or responds automatically is known as Automata Theory.

Following are the major types of automata

Finite Automata

Push Down Automata

Turing Machine

Cellular Automata

Timed Automata

Artificial Intelligence (Introduction)

Artificial Intelligence (AI) is the part of computer science which focuses on creating machines and software that can take on behaviors that humans consider intelligent. The skill to make intelligent machines has intrigued humans since ancient times and now with the dawn of the computer and 50 years of constant research in AI programming techniques, the vision of intelligent machines has become a reality. Scientists are creating systems which can copy human thought, understand human speech, beat the best human chess player in the world, and countless other facts by no means possible before.

Honda ASIMO uses sensors and intelligent algorithms to avoid obstacles and navigate stairs [2].

File:Honda ASIMO Walking Stairs.JPG

Figure Honda ASIMO [3]

KISMET is at MIT Museum. It is a robot which has rudimentary social skills.

File:Kismet robot at MIT Museum.jpg

Figure KISMET at MIT [4]

Automata & Artificial Intelligence

Artificial Intelligence is mainly implemented in Cellular Automata and Time Automata. Cellular Automata has created Artificial Intelligence implemented in several machines used in our daily life like computers, cell phones, cars etc. and even an artificial life in the “The Game of Life” Automata. The execution core of a computer processor also uses cellular automata to successfully change its states simultaneously from fetch, decode and execute states.

Complex Finite State Machines can also have Artificial Intelligence. They are widely used in software to validate user input, for example email addresses. Robots are good example of Artificial Intelligence, which can perform many tasks and even show emotions.

We will be discussing implementation of Artificial intelligence in the following types of automata:-

Cellular Automata

Timed Automata

Turing Machine

Finite State Machines

Cellular Automata

Cellular Automata was described by John von Neuman and Stanislaw Marcin Ulam in 1940. The definition of automata is “The dynamic systems which are discrete in space and time, operate on uniform regular lattice and are characterized by local interactions are called Cellular Automata”.

Cellular Automata consists of “cells” in one or two dimensions (rows & columns) and a set of “rules”. Each cell changes its state on the basis of neighboring cells and the set of rules. Cellular Automata which have cells in only rows are One-Dimensional cellular automata and Cellular Automata which have both rows and columns are Two-Dimensional cellular automata.

5.1 One-Dimensional Cellular Automata

One-Dimensional cellular automata have cells arranged in rows. Each cell has a left and a right neighbor. Each cell can be initialized on one of the several states. The number of states depends upon the automation. The cells can change states over time, but all the cells have to change their states simultaneously.

Figure One Dimensional Cellular Automata

The Cellular Automata provides a set of rules which provides a guide line the cells to change their states. When the states are being changed, each cell gathers the information on the states of its neighboring states. Then on the basis of its own state, its neighboring cells states and the set of rules, it determines its new state.

5.2 Firing squad synchronization problem

The firing squad synchronization problem is a problem in computer science first proposed by John Myhill in 1957 and published in 1962 by Edward Moore. The problem is solved by One-Dimensional Cellular Automata.

Consider n number of lieutenants arranged in a line. At time t equal to zero, each lieutenant is initialized to a starting state, except for the first one on the far left, who is the captain. The state of each lieutenant at each separate time-step t greater than zero is dependent on its state and the state of its two neighbors at time t minus one. In addition to this, if a lieutenant and its neighbors are in the idle state, then the lieutenant will remain idle at the next time-step. The problem is to define a finite set of states and state transition rules for the lieutenants such that all lieutenants enter firing state at the same time and for the very first time. [5]

The solution to this problem is given in the following points:-

Propagate two waves down the line of lieutenants.

A fast wave and a slow wave, the slow wave is moving three times as slower than the fast wave.

The fast wave bounces off from the other end of the line of lieutenants and meets the slow wave in the centre of the line.

The two waves then tear into four waves, a fast and slow wave moving in both directions from the centre, and then splitting the line into two equal parts.

This procedure continues to subdivide the line until each division is of length 1 i.e. each cell. At this moment every lieutenant fires. This solution requires 3n units of time for n lieutenants.

Figure Firing squad problem

5.3 Two-Dimensional Cellular Automata

Two-Dimensional Cellular Automata consists of cells arranged in rows and columns. Each cell has four or eight neighbors. As in One-Dimensional Cellular Automata, each cell can be initialized on one on n number of state (where n is any number). The cells change their states on the basis of their own state, neighboring cells states and the set of rules.

Figure Two Dimensional Cellular Automata

5.4 Game of Life

The Game of Life is a ‘cellular automaton’ invented by British Mathematician John Horton Conway in 1970 [6]. A well-known example of cellular automata.

The Game of Life involves only two states, “live” or “dead”. Each live cell can die because of loneliness or overcrowding of live cells. Each dead cell can live if it has a specific number of live cells surrounding it. Following are the set of rules for Game of Life Automata:-

Each cell is “live” or “dead”

Transition rules

N = number of live neighbors among the 8

If N is less than or equal to 1 (N <=1) → death (loneliness)

If N is equal to 2 (N = 2) → no change

If N is equal to 3 (N = 3) → birth

If N is greater than or equal to 4 (N >= 4) → death (overcrowding)

Example

Let us consider that grey colored cell is live cell and white colored cell is dead cell.

When a live cell has only one neighboring live cell it dies in the next state.

When a live cell has two neighboring live cells it remains alive in the next state (no change).

When a dead cell has three neighboring live cells then the dead cell becomes alive in the next state (birth).

When a live cell has four neighboring live cells it dies in next state (overcrowding).

Timed Automata

Time Automata was developed by Nancy Lynch and Frits Vaandrager. Augmentation of the finite automata with the timing constraints is called Timed Automata. It accepts timed words, i.e., time is associated in each symbol. The non- negative numbers are used in time domains.

Automation A over clocks C is

A = ( L, Io, E, I )

WHERE

L is set of locations

Io is the initial location

E is the set of edges between locations

I is the set of invariants on locations

EXAMPLE

Consider a light switch which is only one button. When we press the button once it turns on to low light. When it is pressed twice quickly it goes to high light. On low light if the button is not pressed quickly the light is turned off. If we make a Finite State Machine without timing constraints we will get a Nondeterministic Finite State Machine [1].

Figure FSM of light button problem

Solution to this problem is given in the following points

We add a real- valued clock x

When the button is pressed first time, x is equal to zero (x=0) and the light is at low light.

When the button is pressed second time, if x is less than or equal to three (x<=3) the light goes bright, else when x is greater than three (x>3) the light goes off.

Figure Timed Automata of light button problem

Turing Machines

In the era of 1930s-1950s many researchers worked over what was calculable, and what wasn’t. The father of computing and artificial intelligence a British mathematician Alan Turing, wanted to search for an answer to this problem. He constructed the theory of Turing machine. His theorem (the Church Turing thesis) states that

“Any effective procedure (or algorithm) can be implemented through a Turing machine. ” [7]

http://library.thinkquest.org/18242/images/turing1.gif

Figure Schematic Drawing of a Turing Machine [7]

Turing machine are conceptual mathematical entities that are consist of a tape, a read-write head, and a finite-state machine. The head is basically an input-output device that can either move left or right, and read or write symbols onto the tape. The finite-state machine work as a memory processor that keeps the track of which of the finite-state it is currently in, and by knowing its currently finite state, it can determine which state it has to move on next, what symbol to read or write onto the tape, and which direction the head should move (left or write). The tape must be as large as the computation assigned to the machine. In above figure, the tape is assigned for the finite number of 0s, 1s and blank spaces.

Thus the Turing machine can perform three following possible things:

It can read or write symbol at its current position on the tape.

It can guess for a new state.

It can move the head either the left or right position.

The Turing is capable of making any computation. But this is neither a provable theorem nor a strictly proper ultimate approach. The Church-Turing theorem is base on perceptions of what computing is about. By understanding that what can Turing machine compute, we can grasp the potential of production system for computing.

7.1 Formal Definition of Turing Machine

A Turing Machine (TM) is the 7-tuple: M = (Q, S, G, d, q0, B, F), where

Q is a finite set of states,

G is a finite tape alphabet; SÍG is an input alphabet,

d: Q ´ G® Q ´ G ´ {L,R} is a transition (next move) function (can be undefined for some arguments); it takes a state and tape symbol, returns a new state and replacement symbol and direction L/R for head motion; initially, the tape head is at the leftmost cell that holds the finite input)

q0ÎQ is the initial state; F ÍQ accepting (final) states

BÎG-S is a blank symbol (it appears initially in all but the finite number of initial cells that hold input symbols).

Example

The following Turing machine < Q1 , http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/Sigma.gif, http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/Gamma.gif, q0 , http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/delta.gif> accepts the language aba* ,

Where

Q1 = { q0, q1, q2, q3 }

http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/Sigma.gif= { a , b }

http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/Gamma.gif= { a , b }

http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/delta.gifis as given by the table below.

Table Turing Machine Example Table

A transition diagram of this Turing machine is given below. It is assumed that the tape has http://www.cs.odu.edu/%7Etoida/nerzic/390teched/symbols/Delta.gifat the left end and the head is initially at the left end of the tape.

Figure Turing Machine Example Transition Graph

Finite State Machine

A Finite State Machine (FSM) is a model of behavior using states and state transitions. A transition is a state change triggered by an input event, i.e. transition maps some state-event pairs to other states. A finite state machine consist of a set of input events, a set of output events, a set of states, a function that maps states and input to output, a function that maps states and inputs to states and a description of the initial state. A finite state machine is one that has a limited or finite numbers of states. The machine state is described by a collection of state variables.

A finite state machine is an abstract concept, and may be implemented using a variety of techniques, including digital logics, games etc.

Finite state machine can specify control flow aspects. System viewed as a set of states which react to events. Upon as event, a system may stay in same or make transition to another state. [8]

Figure Finite State Machine

System behavior is interpreted as a series of functions. Input to each function is a set of conditions and an event. Output is the change in the state of the system and an

System behavior is interpreted as a series of functions. Input to each function is a set of conditions and an event. Output is the change in the state of the system and any other action.

Formally, A FSM consist of:

A set of states: Q

A set of inputs: I

A transition function: Q x I

Initial state: qo

Final state: qf

Figure Acceptor FSM: parsing the word “nice”.

In above state figure

Q = {start, n_found, i_found, c_found, error, success}

I ={n.i.c.e}

qo ={start}

qf = {error, success}

8.1 Application of Finite State Machine

FMSs have been used in video game industry. Different functionalities like moving, walking, talking and other odious techniques of robots are controlled by simple Finite State Machine. The advantages of complex FSM system are to control the Artificial Intelligence (AI). Beside the video games, robots, game environments and game’s characters etc, the FSMs are used outside the games. Like in automotives, robotics, computers and even in websites.

8.2 Email Address Validation by FSM

Email address is validated by using Regular Expression. The email IDs validation rules are described below by giving examples by comparing valid and invalid IDs.

The Email address must start with an alphabet, any number or digit can be added in the name. Underscore ( _ ) or dot ( . ) can be added between the alphabets.

No whitespace or other symbols can be used.

There must be an alphabet or a digit before @ sign.

No underscore ( _ ) sign can be used one after another.

Dot can be used only once but underscore can be used multiple times.

Examples

m.rizwan123@hotmail.com valid

123m.rizwan@htomail.com invalid (starting with number)

rizwanumaid_123@yahoo.com valid

rizwanumaid 123@yahoo.com invalid (white space)

rizwan.123_123@hotmail.com valid

rizwan.123_@hotmail.com invalid (name field ending with s symbol)

rizwan.123.123@hotmail.com invalid (double dots)

By obeying these rules and by looking these examples, a state diagram can be drawn which can illustrate the Email validation process more precisely:

diagram.gif

Figure State diagram for email validation

By seeing the above state diagram, we can form a regular expression of the Email ID before @:

[ a – z ] [ a – z | 0 -9 ] * ( [ _ ] [ a-z | 0 -9 ] + ) * ( [ . ] [ a -z | 0-9 ] + ( [ _ ] [ a-z | 0-9] ) * )

The Email address should start with an alphabet and any other number or alphabet can be added in between except white spaces and other symbols.

The regular expression for above rule is:

[ a – z ] [ a – z | 0 – 9 ] *

In portion like (.com or .net), after the dot ( . ) any alphabet or digit can be added. The same rule will be followed when another portion like previous is added like (.com.pk etc).

The regular expression for this is:

( [ a – z ] [ a – z | 0 – 9 ] * ( ( . ) [ a – z ] [a – z | 0 – 9] * ) )

By combining all of the above expressions, the main regular expression can be formed which is quite similar to the rules applied by Yahoo! Email validation rules.

[ a – z ] [ a – z | 0 -9 ] * ( [ _ ] [ a-z | 0 -9 ] + ) * ( [ . ] [ a -z | 0-9 ] + ( [ _ ] [ a-z | 0-9] + ) * )

@ [ a – z ] [ a – z | 0 – 9 ] *

( [ a – z ] [ a – z | 0 – 9 ] * ( ( . ) [ a – z ] [a – z | 0 – 9] * ) ? )

By using above rules and regular expressions, any type of validation can be done which is much easier than any other ways of validation.