APPLICATIONOF FUZZY GRAPH THEORY IN FINITE STATE AUTOMATAV.MythiliAssistantProfessor, Department of Mathematics, PrinceShri Venkateshwara Padmavathi Engineering College, Ponmar, Chennai.Abstract – Multistage decision making is a kindof dynamic process. A required goal is not achieved by solving a singledecision problem but by solving a sequence of decision making problems.
Thesedecision making problems which represent stages in overall multistage decisionmaking are dependent on one another in dynamic sense. Automata theory dealswith the definitions and properties of mathematical models of computation. Finitestate automata are used in text processing, compilers and hardware design. Inthis paper we give a procedure to obtain an optimal sequence of input states offinite state automata.
Key words: Transition graph, Transition table,Finite state automata, Directed graph, Strings, Languages. IINTRODUCTIONTheprocess of computation involves solving problems by communicating them to acomputational model by means of a suitable language. Also we need some model torecognize these languages.
A simple kind of machines called finite automatawill fulfil this requirement. Here we discuss the application of fuzzy graphtheory in fuzzy finite state automaton through multistage decision making. Fuzzy sets originated in a seminal paper byLotfi A.Zadeh in 1965. Since then it has grown by leaps and bounds andinnumerable number of papers has appeared in various journals. Applications offuzzy 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 bothconsumer products like cameras, washing machines, TV and industrial productsbased on fuzzy logic controllers were rolled out in the market. Theorigin of graph theory started with the Konisberg bridge problem in 1735.
Best services for writing your paper according to Trustpilot
Eulerstudied the Konisberg bridge problem and constructed a structure that solvesthe problem which is referred to as an Eulerian graph. Graph theory is adelightful playground for the exploration of proof techniques in discretemathematics and its results have applications in many areas of computing,social and natural sciences. The initial model for any article on graph theorywas the elegant text by J.A.
Bondy and U.S.R Murty, Graph Theory withapplications (Macmillan/North-Holland 1976). Graph theory is still young andno consensus has emerged on how the introductory material should be presented.
Currentlyconcepts of graph theory are highly utilized by computer science applicationsespecially in areas of data mining, image segmentation, clustering andnetworking. Fuzzy sets paved the way for a new method of philosophical thinking”Fuzzy Logic” which is now an essential concept in artificial intelligence. Themost important property of fuzzy set is that it consists of a class of objectsthat satisfy a certain property or several properties.In1957 John Myhill invented Transition graphs. A Transition graph is a directedlabelled graph whose nodes correspond to the states of the finite automaton andedges correspond to the transition. Each edge of the graph corresponds to thetransition from one state to another state. Therefore each edge is labelledwith the corresponding input symbol, which is written on the edge.
If a path isfollowed from the start state to the final state and the symbols on the edgescontained in the path are combined together, a string will be generated, whichis accepted by the finite automaton.II FUZZY NUMBER A Triangular Fuzzynumber It is a Fuzzy numberrepresented 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 numberIt 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
The number of rows in a transition table is equal to thenumber of states in Q , while the number of columns is equal to the number ofinput 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 arrowwhereas the final states are enclosed in double circles.III DIRECTED GRAPHAdirected 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 thatnode and the number of arrows pointing to a particular node is the in degree. EXAMPLE Fig1.Directed Graph In a directed graph we represent anedge from i to j as a pair (i,j). The formal description of a directed graph Gis (V,E) where V is the set of nodes and E is the set of edges.
The formaldescription 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 Analphabet is a non empty finite set denoted byS.The members of the alphabet are the symbols of the alphabet. A string over analphabet is a finite sequence of symbols from that alphabet, written next toone 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 slightlycumbersome when it is used for every input symbol. Hence extended transitionfunction 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 eis the empty string.EXAMPLE Letus design a DFA to check for numbers that are divisible by 4.
We know that if any number isdivided by 4, it may give remainder 0, 1, 2 or 3 where remainder 0 implies thatthe 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 togenerate the transition table in which the number of rows would be equal to 4corresponding to q0, q1, q2, q3 andnumber 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 Table1. Transition TableThe DFAis defined as Q = { q0,q1,q2,q3 }S= ( 0,1,2,3,4,5,6,7,8,9)q0is the initial state and F = {q0}is the final state because a number is divisible by 4 only if it produces aremainder 0.Theorem Let A= (X,Z,f) be a fuzzy automatonwhere X & Z are respectively the set of input and output states and f:ZxX®Z is the state – transition function of A.
Theoptimal sequence of decisions x0, x1,x2…..xN-1 of decision can be obtained by successivelymaximizing values xN-K in CN-K(zN-K)=maxminAN-K(xN-K)CN-K+1(zN-K+1) XN-K forK= 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 beconsidered as constraints and fuzzy internal state CN as fuzzy goalin a fuzzy decision making, We may conceive of fuzzy decision as a fuzzy set onxn defined by D = Ã0 Ç Ã1Ç……
CN where Ãt is acylindric extension of At from X to XN for each t = 0,1,…. N-1 and CN isthe fuzzy set on xN that induces CN on Z.
That is for anysequence x0, x1,x2…..xN-1 viewed as a sequence of decision, themembership grade of D is defined by D(x0,x1,x2..
…xN-1 ) = minA0(x0), A1(x1)..
……AN-1 (xN-1), CN(zn )——————— (1)WherezN is a uniquely determined by x0, x1,x2.
….xN-1 and z0through zt+1 = f (zt, xt) we have tofind a sequence of input states.Example Let A = (x,z,f) be an automaton where inputstates X = {x1,x2} output states Z ={ z1, z2,z3 } and the state transition function. Let their be twostates 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/x2obtain an optimal sequence of input states. SolutionThebest decision X1 for eachstate z1 Î Z at time t=1is Z1 z1 z2 z3X1 x2 x1 x2 The best decision X0 for each state z0 Î Z at time t=0 is Z0 z1 z2 z3X0 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 maximisingdecisions is used.
IV CONCLUSIONAdecision problem conceived in terms of fuzzy dynamic programming is viewed as adecision problem regarding a fuzzy finite state automaton. A fuzzification of dynamic programmingextends its practical utility since it allows decision makers to express theirgoals, constrains, decisions and so on. In approximate fuzzy terms wheneverdesirable.REFERENCES 1 ZadehL.A.
Fuzzy sets ,Information and control,8(1965).2 Animesh Kumar Sharma,Padamwar.B.
V,Dewangar.C.L.-Trendsin 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 GraphTheory,Allied publishers Pvt. Ltd (2010).5 George J Klir and Bo Yuan, Fuzzysets and Fuzzy Logic, PHI Learning pvt ltd.6 J.
Kavikumar, Member, IAENG, Azme Bin Khamis and Rozaini Bin Roslan Bipolar-valuedFuzzy Finite Switchboard StateMachines Proceedings of the World Congress on Engineering and Computer Science2012 Vol I WCECS 2012, October 24-26, 2012, San Francisco, USA.7 Frank Harary, Graph Theory , Narosa PublishingHouse 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 CBA
