communicating and mobile syste ms : the π-calculus
chapter 1 introduction
chapter 2 Behaviour of Automata [email protected]
11/ 8 (Wed)
chapter 1 Introduction
A B
D C
A B
D C
A B
D C
A B
D
1D
2C
mobilityconcurrent activation
from call to return arc
chapter 2 : Automata
Automaton
Q= { q
0, q
1,… } state
q
0∈ 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 n ondeterminism
Deterministic Automaton Non-deterministic Automaton
参考：参考文献
p29~ DFA
とNFA
の等価性
p38~
有限オートマトンと正 則表現の 同値性
p84~
有限オートマトンの最小化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
参考文献
• オートマン言語理論 計算論Ⅰ
