11/ 8 (Wed)
communicating and mobile
systems : the π-calculus
chapter 1 introduction
chapter 2 Behaviour of Automata
[email protected]
chapter 1 Introduction
C
D
from call
to return
C
D
arc
A
concurrent
B
D1
D2
A
C
mobility
B
C
D
activation
A
B
A
B
chapter 2 : Automata
Automaton
Q={q0, q1,…} state
q0 ∈ Q
start states
F
accepting state
T : Q×Act×Q transition
Language of an automaton
chapter 2 : Regular sets
Regular sets (正則集合）
正則表現（Regular Expression）
1) ∅ は正則表現で、その表すものは空集合
2) εは正則表現で、その表す集合は{ε}である
3) Σの各元aに対してaは正則表現で、その表す集
合は{a}である
4) r とs がそれぞれRとSを表す正則表現のとき、(r+s ), ( rs ),
及び (r* ) は正則表現で、それぞれ集合R⋃S, RS, R*をあら
わす
ある言語が有限オートマトンの受理言語 ⇒ 正則集合
chapter 2 : The language of an
automaton
• どのようにして
を見つけるか？
chapter 2 : Determinism versus
nondeterminism
Deterministic Automaton
Non-deterministic Automaton
参考：参考文献 p29~
p38~
p84~
DFAとNFAの等価性
有限オートマトンと正則表現の
同値性
有限オートマトンの最小化
chapter 2 : Black boxes, or
reactive systems
prefix : ss’のs
prefix-closed : ss’∈S then s ∈S
prefix-closure : pref(X) – which contains all
the prefixes of every
string in S
参考文献
• オートマン言語理論 計算論Ⅰ
J.ホップクロフト/ J.ウルマン
サイエンス社