Introduction to Finite State Automata: Language and Theory
Explore the world of finite state automata, capturing dynamic behaviors of systems through logical properties. Learn about languages, regular expressions, and how they represent events in systems. Dive into the definitions and examples of regular languages and expressions, unraveling the fundamentals of automata theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 2 Language and Automata Theory Self-reading 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 by letters in E. Language vs DES : E = set of events string = sequence of events L = set of all possible event sequences Example : E = { L1 = , L2 = {all strings of length 3} L3 = {all strings of finite length ending with } L4 = {all possible sequences of a queue} 4 4
The language of the single server queue Events : a = arrival, d = departure The language of the initially empty queue L = { , a, aa, ad, aaa, aad, ada, aaaa, aaad, aada, aadd, adaa, adaa, 4events } Customer arrivals 0 event 1 event 2 events 3 events Server Queue Customer departures 5 5
Regular expressions Operations E : alphabet, A, B : languages = empty string, u, v, w: strings Concatenation : AB = {w : w = uv, u A, v B} Union : A+B = {w : w A, or v B} Kleene closure : = * n A A = 0 n whereA0= { }, An= AAn-1 6
Regular expressions Example : E = { L1= , L2= { } L1L2= L2*= { } L1*= { } L1+ L2= 7 7
Regular expressions Definition: A regular expression is a representation defined recursively as follows : 1 is a regular expression denoting the empty set, is a regular expression denoting the set { }, 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. 8
Regular expressions Examples: L = ( + ) = L = ( ) + = L = (( + ) ) 9
Language of a machine subject to failures Events : f = failure, r = repair Language of an initially UP machine : L = (fr)*( + f) Language of an initially DOWN machine : L = (rf)*( + r) Language of a machine starting and finishing in UP : L = (fr)* 10
Definition Definition: A finite-state automaton (FSA) is a five-tuple (E, X, f, x0, F) where a finite alphabet E a finite state set X a state transition functionf: X E X where f is a partial function and f(x, e) is sometime undefined. f an initial state, x0 X a set of final states, F X x0 F
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 = { } X = {x, y, z} f(x, ) = x, f(x, ) = f(x, ) = z f(y, ) = x, f(y, ) = f(y, ) = y f(z, ) = z, f(z, ) = f(z, ) = y initial state x0 = x Final states : F = {x, z} x y z Sample paths: ??? 14
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}. L(A) = language recognized by A. x y Example: L(A) = ??? z 15
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. x y Arden s rule : If A does not contain the empty string, X = AX + B X = A*B X = XA + B X = BA* z 16
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 not containing a final state 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}. 17
Automata models of queueing systems Server a Queue d a B a a I 0 1 2 d d d Queueing perspective D Server perspective I = idle, B = busy D = down 18
