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  {PP1 | 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