Formal Languages and Automata Theory Applied to Transportation Engineering Problem of Incident Management Neveen Shlayan Ph.D. Candidate Outline • • • • • • • • Introduction Set Theory Review Formal Languages Grammar Automata Theory Incident Management Problem Specification and Verification Conclusions Formal and Automata Theory • Has a fundamental role in the progress of computer science – Precise definition of syntax for programming languages • Bring order to the Chaos – Hardware and Software debugging Set Theory Review (Notation) • • A={a, b, c} A is the set whose elements a, b, and c W {x : x N } W equals the set of all x such that x is a natural number • • A B Union • A B Intersection • • Ø = { } Empty Set A B Complement of B relative to A Ac Complement of A • A B A is a subset of B • A B Cartesian product, set of all ordered pairs in the form (a, b) Examples….. A={a, b, c, d} B={c, d, e, f, g} • Function from A to B is a subset of A B Set Theory (Power Set) • P(X) is the power set of X, the collection of all subsets of X. • |X| is the number of elements in the set X |P(X)| = 2|X| Examples.. {1}, {1, 2}, {1, 2, 3} Power Set of Natural numbers is uncountable Operations over Symbols • Finite Alphabet: V, A non-void set of arbitrary symbols (e.g. {a,b}) – a and b here are called letters or symbols. • Finite strings of letters are called words over V, e.g. ab, aab, baba etc. • V*: The set of all words (obviously each has finite length) – is the empty word and is in V* for any V More Operations • Catenation: Joining of words… – e.g. abaa+abb=abaaabb; • Associative but not commutative; i.e. PQ QP in general, but (PQ)R=P(QR) • V* is closed with respect to catenation, i.e. P and Q in V* implies PQ is in V* • Unit : P P P – We can define length function on words and study properties etc. Even More Operations • Iterations: P ab; P0 ; P2 abab; • Mirror Image: P ab; P 1 ba; Language • Language: An arbitrary set of words of V*, e.g. {a, ab, aa, aaa, aab,….}; – Finite or infinite – V* is countable infinite (denumerable) – Number of languages out of V* (i.e. how many subsets, i.e. the size of powerset of V*) is uncountable (nondenumerable) Language Examples • Examples V {a, b} L1 {a, b, } L2 {a i b i | i 0,1,...} L3 {PP1 | P V *} Grammar • Definition Grammar Example Automata Incident Management Process Incident Occurs Emergency Responders (ER) Contacted ER Arrive to the Scene Incident Cleared Challenges In Current Incident Management Process Communication Coordination Increase in Clearance Time Economical, Safety, Environmental, and Social Impacts Formal Language Theory used in Incident Management Define a formal Language Process FSM Model Properties Specification Liveness and Safety Process Debugging Software for Finite State Machine • Labelled Transition System Analyzer v3.0 http://www.doc.ic.ac.uk/~jnm/book/ • Temporal Logic of Actions http://research.microsoft.com/enus/um/people/lamport/tla/tools.html Finite State Process (FSP) Model Labeled Transition Systems (LTS) Diagrams Sequence Properties • Safety: “nothing bad happens” • Liveness: “something good eventually happens” System Verification Thanks For Coming

Descargar
# Formal Languages and Automata Theory