APPLICATION

OF FUZZY GRAPH THEORY IN FINITE STATE AUTOMATA

V. Mythili

Assistant

Professor, Department of Mathematics,

Prince Shri

Venkateshwara Padmavathi Engineering College, Ponmar, Chennai-600127.

v.mythili.ma[email protected]

Abstract

– Multistage

decision making is a kind of dynamic process. A required goal is not achieved

by solving a single decision problem but by solving a sequence of decision

making problems. These decision making problems which represent stages in

overall multistage decision making are dependent on one another in dynamic

sense. Automata theory deals with the definitions and properties of

mathematical models of computation. Finite state automata are used in text processing,

compilers and hardware design. In this paper we give a procedure to obtain an

optimal sequence of input states of finite state automata.

Key words: Transition graph, Transition table,

Finite state automata, Directed graph, Strings, Languages.

I

INTRODUCTION

The

process of computation involves solving problems by communicating them to a

computational model by means of a suitable language. Also we need some model to

recognize these languages. A simple kind of machines called finite automata

will fulfil this requirement. Here we discuss the application of fuzzy graph

theory in fuzzy finite state automaton through multistage decision making.

Fuzzy sets originated in a seminal paper by

Lotfi A.Zadeh in 1965. Since then it has grown by leaps and bounds and

innumerable number of papers has appeared in various journals. Applications of

fuzzy sets and fuzzy logic were ushered in by Mamdani through a paper in 1975.

The development in applications was so drastic that within 15 years both

consumer products like cameras, washing machines, TV and industrial products

based on fuzzy logic controllers were rolled out in the market.

The

origin of graph theory started with the Konisberg bridge problem in 1735. Euler

studied the Konisberg bridge problem and constructed a structure that solves

the problem which is referred to as an Eulerian graph. Graph theory is a

delightful playground for the exploration of proof techniques in discrete

mathematics and its results have applications in many areas of computing,

social and natural sciences. The initial model for any article on graph theory

was the elegant text by J.A.Bondy and U.S.R Murty, Graph Theory with

applications (Macmillan/North-Holland 1976). Graph theory is still young and

no consensus has emerged on how the introductory material should be presented.

Currently

concepts of graph theory are highly utilized by computer science applications

especially in areas of data mining, image segmentation, clustering and

networking. Fuzzy sets paved the way for a new method of philosophical thinking

“Fuzzy Logic” which is now an essential concept in artificial intelligence. The

most important property of fuzzy set is that it consists of a class of objects

that satisfy a certain property or several properties.

In

1957 John Myhill invented Transition graphs. A Transition graph is a directed

labelled graph whose nodes correspond to the states of the finite automaton and

edges correspond to the transition. Each edge of the graph corresponds to the

transition from one state to another state. Therefore each edge is labelled

with the corresponding input symbol, which is written on the edge. If a path is

followed from the start state to the final state and the symbols on the edges

contained in the path are combined together, a string will be generated, which

is accepted by the finite automaton.

II FUZZY NUMBER

A Triangular

Fuzzy number

It is a Fuzzy number

represented by 3 points (a1, a2, a3) as A (a1, a2,

a3) with membership function

mA(x) = 0 if

x < a1
(x-a1)/(a2-a1) if a1 ? x ? a2
(a3-x)/(a3-a2)
if a2 ? x ? a
0 if x > a3

B Trapezoidal Fuzzy number

It is a

Fuzzy number represented by 4 points

(a1,a2,a3,a4) as A(a1,a2,a3,a4)

with membership function

mA(x) =

0 if x <
a1
(x-a1)/(a2-a1) if
a1 ? x ? a2
1 if a1 ? x ? a2
(a4-x)/(a4-a3) if
a1 ? x ? a2
0 if x >

a4

Deterministic finite state automaton

A Deterministic finite state automaton M

is defined as a 5-tuple ( Q, S,

d,

q0, F )

where

(i)

Q represents a

finite non empty set of states

(ii)

S denotes a finite non empty set of input symbols

from which input string is made.

(iii)

d is a transition function which may be defined as d

: Q´S®Q

Here

q0Î

Q is called as the initial state, F Í

Q is the non empty finite set of final states or accepting states. For finite

automata, a finite set of final states can be specified. However, for a given

input, there will always be only one final state. Changes in the input string

may provide some other final states.

The

transition function of finite state automata is generally represented by a

transition table. The number of rows in a transition table is equal to the

number of states in Q , while the number of columns is equal to the number of

input symbols in S.

The entry for each row is generated by using d

: Q ´S®Q.

The starting state in a transition table is denoted by an incoming arrow

whereas the final states are enclosed in double circles.

III DIRECTED GRAPH

A

directed graph is a set of points with arrows connecting some of the points.

The points are called nodes or vertices, the arrows are called directed edges.

The number of arrows pointing from a particular node is the out degree of that

node and the number of arrows pointing to a particular node is the in degree.

EXAMPLE

Fig1.

Directed Graph

In a directed graph we represent an

edge from i to j as a pair (i,j). The formal description of a directed graph G

is (V,E) where V is the set of nodes and E is the set of edges. The formal

description of figure 1 is G =

{{1,2,3,4,5}, {(1,2),(1,5),(2,1),(2,4),(5,4),(5,6),(6,1),(6,3)}}

Alphabet

An

alphabet is a non empty finite set denoted byS.

The members of the alphabet are the symbols of the alphabet. A string over an

alphabet is a finite sequence of symbols from that alphabet, written next to

one another and not separated by commas.

EXAMPLE

Let S

= {0,1} be an alphabet. Then the strings are {0011,0000011111, 111100011100,}

DEFINITION

Transition function is slightly

cumbersome when it is used for every input symbol. Hence extended transition

function is used which is denoted by d*

and is defined by d*:

Q´S*®

Q as

d*(q0,

aw)

= d*(

d(q0,

a),w)

and d*(q,e)

= q where e

is the empty string.

EXAMPLE

Let

us design a DFA to check for numbers that are divisible by 4.

We know that if any number is

divided by 4, it may give remainder 0, 1, 2 or 3 where remainder 0 implies that

the number is divisible by 4. Hence there are 4 possible states for the DFA.

Let us represent these states as q0, q1, q2, q3. The next step is to

generate the transition table in which the number of rows would be equal to 4

corresponding to q0, q1, q2, q3 and

number of columns would be equal to 10 corresponding to all possible inputs (

0,1,2,3,4,5,6,7,8,9)

States/Input

0

1

2

3

4

5

6

7

8

9

q0

q0

q1

q2

q3

q0

q1

q2

q3

q0

q1

q1

q2

q3

q0

q1

q2

q3

q0

q1

q2

q3

q2

q0

q1

q2

q3

q0

q1

q2

q3

q0

q1

q3

q2

q3

q0

q1

q2

q3

q0

q1

q2

q3

Table

1. Transition Table

The DFA

is defined as Q = { q0,q1,q2,q3 }

S

= ( 0,1,2,3,4,5,6,7,8,9)

q0

is the initial state and F = {q0}

is the final state because a number is divisible by 4 only if it produces a

remainder 0.

Theorem

Let A= (X,Z,f) be a fuzzy automaton

where X & Z are respectively the set of input and output states and f:ZxX®Z is the state – transition function of A. The

optimal sequence of decisions x0, x1,x2…..xN-1 of decision can be obtained by successively

maximizing values xN-K in CN-K(zN-K)=max

minAN-K(xN-K)CN-K+1(zN-K+1)

XN-K

for

K= 1,2, ……. N where zN-K+1 = f ( zN-K,

xN-K)

Proof

Let A0, A1, A2…..AN-1 be the fuzzy input states which could be

considered as constraints and fuzzy internal state CN as fuzzy goal

in a fuzzy decision making, We may conceive of fuzzy decision as a fuzzy set on

xn defined by D = Ã0 Ç Ã1Ç……CN where Ãt is a

cylindric extension of At from X to XN for each t = 0,1,…. N-1 and CN is

the fuzzy set on xN that induces CN on Z. That is for any

sequence x0, x1,x2…..xN-1 viewed as a sequence of decision, the membership

grade of D is defined by

D(x0,

x1,x2…..xN-1

) = minA0(x0), A1(x1)……..

AN-1 (xN-1), CN(zn )

——————— (1)

Where

zN is a uniquely determined by

x0, x1,x2…..

xN-1 and z0

through zt+1 = f (zt, xt) we have to

find a sequence of input states.

Example

Let A = (x,z,f) be an automaton where input

states X = {x1,x2} output states Z ={ z1, z2,

z3 } and the state transition function. Let their be two

states and the fuzzy goal at t =2 is C2 = .3/ z1

+ 1/z2 + .8/z3 .

At time t= 0, t=1. Let the fuzzy constraints be A0 = .7/x1

+ 1/x2 and A1 = 1/x1 + .6/x2

obtain an optimal sequence of input states.

Solution

The

best decision X1 for each

state z1 Î Z at time t=1

is

Z1 z1 z2 z3

X1 x2 x1 x2

The best decision X0 for each state z0 Î Z at time t=0 is

Z0 z1 z2 z3

X0 x2 x1 or x2 x1 or x2

The goal is satisfied to the degree

.6 when the intial state is Z2 regardless of which of the two maximising

decisions is used.

IV CONCLUSION

A

decision problem conceived in terms of fuzzy dynamic programming is viewed as a

decision problem regarding a fuzzy finite state automaton. A fuzzification of dynamic programming

extends its practical utility since it allows decision makers to express their

goals, constrains, decisions and so on. In approximate fuzzy terms whenever

desirable.

REFERENCES

1 Zadeh

L.A.Fuzzy sets ,Information and control,8(1965).

2 Animesh Kumar

Sharma,Padamwar.B.V,Dewangar.C.L.-Trends in Fuzzy Graphs- IJIRSET,2 (2013)

4636-4639.

3 Bhattacharya.p,

Some Remarks of fuzzy graphs, pattern Recognition Left, 6 (1987) 297-302.

4

NagoorGani.A, Chandrasekaran.V.T., A first look at Fuzzy Graph

Theory,Allied publishers Pvt. Ltd (2010).

5

George J Klir and Bo Yuan, Fuzzy

sets and Fuzzy Logic, PHI Learning pvt ltd.

6 J.

Kavikumar, Member, IAENG, Azme Bin Khamis and Rozaini Bin Roslan Bipolar-valued

Fuzzy Finite Switchboard State Machines

Proceedings of the World Congress on Engineering and Computer Science 2012 Vol

I WCECS 2012, October 24-26, 2012, San Francisco, USA.

7 Frank Harary, Graph Theory , Narosa Publishing

House Pvt Ltd.

8 Douglas B.West,

Introduction to Graph Theory, Second Edition, Pearson India Education

Services Pvt Ltd.

M. GATTO AND G. GUARDABASSM. GATTO AND G.

GUARDABASS

C

BA