Report

Chapter 2 Language and Automata Theory Learning objectives : Introduce finite state automata Able to capture state, events and dynamic behavior of “man-made systems” Present logical properties Textbook : C. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, Springer, 2007 1 1 Plan • Languages • Finite state automata 2 2 Languages 3 3 Definitions Definition: A language L, defined over an alphabet E, is a set of strings formed from events in E. Language vs DES : E = set of events string = sequence of events L = set of all possible event sequences Example : E = {a,b,g} L1 = {e, a, abb}, L2 = {all strings of length 3} L3 = {all strings of finite length ending with a} L4 = {all possible sequences 4of a queue} 4 Regular expressions Operations E : alphabet, A, B : languages e = empty string, u, v, w: strings • Concatenation : AB = {w : w = uv, uA, vB} • Union : A+B = {w : wA, or vB} • Kleene closure : A * An n 0 where A0 = {e}, An = AAn-1 5 Regular expressions Example : E = {a,b,g} L1 = {e, a, abb}, L2 = {g} L1L2 = {g, ag, abbg} L2* = {e, g, gg, ggg, ...} L1* = {e, a, abb, aa, aabb, abba, abbabb, ...} L1+ L2 ={e, a, abb, g} 6 6 Regular expressions Definition: A regular expression is a representation defined recursively as follows : 1. F is a regular expression denoting the empty set, e is a regular expression denoting the set {e}, e is a regular expression denoting the set {e} for any e E. 2. If r and s are regular expressions, then rs, (r+s), r* and s* are regular expressions. 3. There are no regular expressions other than those constructed by applying rules 1 and 2 a finite number of times Definition: Any language that can be denoted by a regular expression is a regular language. 7 Regular expressions Examples: L = (a+b)g* {???} L = (ab)*+g {???} L = ((a+b)g*)* 8 Finite-state automata 9 Definition Definition: A finite-state automaton (FSA) is a five-tuple (E, X, f, x0, F) where • E is a finite alphabet • X is a finite state set • f is a state transition function f: X× E → X where f is a partial function and f(x, e) is sometime not defined. • x0 is an initial state, x X • F is a set of final states, F X Definition • Transition function f can be extended to strings u : f(x, u) • An automaton is a device that generates a language according to some rules. • An automaton is nondeterministic if there are two possible transitions with the same event and starting from the same state. • Nondeterministic automaton can always be transformed into deterministic FSA by taking all possible subsets reached by events as states. • Nondeterministic automaton will not be considered. Example State transition diagram Definition: Consider an automaton (E, X, f, x0, F) E = {a, b, g} X = {x, y, z} f(x, a) = x, f(x, b) = f(x, g) = z f(y, a) = x, f(y, b) = f(y, g) = y f(z, b) = z, f(z, a) = f(z, g) = y initial state x0 = x Final states : F = {x, z} a a x g b 12 y a g z b Sample paths: ??? b g Automata as language recognizers Definition: A string u is recognized by a finite automaton (E, X, f, x0, F) if f(x0, u) = x where x F. Definition: The language recognized by a finite-state automaton A = (E, X, f, x0, F) is a set of strings {u: f(x0, u) x F}. a L(A) = language recognized by A. a x g b Example: aab L(A) = ??? z 13 b a b y g g Equivalence of FSA and regular expressions Theorem: If a language is regular, then it can be generated by some finite-state automaton; and if it is generated by a finite-state automaton, then it is a regular language. Deriving the language of an FSA • define the language Ls terminating at state s; • write one-step equations for all Ls; • Solve the equations. Arden’s rule : If L1 does not contain the empty string, L2 = L1L2 + L3 → L2 = L1*L3 L2 = L2L1 + L3 → L2 = L3L1* 14 a a x g b z b a b y g g Properties of a FSA model Reachability: A state s is reachable from the initial state x0 if there exists a sequence u such that f(x0, u) = s. Blocking-free: For any reachable state, there exists a sequence of transitions leading to a final state. Deadlock: a state s is called a deadlock state if there is no feasible event from it. Livelock: a subset of states that are mutually reachable but with no event going out of the set. Example : FSA = (0, a, 1), (1, g, 5), (1, a, 3), (1, b, 2), (2, g, 0), (3, b, 4), (4, a, 3), (4, g, 4), x0 = 0, F = {2}. 15 FSA models of queueing systems a Queue a 0 d a 1 d Server d a a 2 b I d m Queueing perspective B l D Server perspective I = idle, B = busy D = down 16