Document

Report
形式言語 と オートマト
第8回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定1
形式言語とオートマト
有限状態オートマトン(FSA)
M=<Q, Σ, δ, q0, F>
Q :状態(state)の有限集合
Σ:入力記号(input symbol)の有限集合
δ :動作関数(move function) (δ:Q×Σ→Q)
q0:初期状態(initial state) (q0∈Q)
F :受理状態(accepting state)の有限集号(F∈Q)
形式言語とオートマト
例: M=<Q, Σ, δ, q0, F>
Q={r,s,t}
Σ={a}
δ:Q×Σ→Q
δ(r,a)=s δ(s,a)=t
δ(t,a)=r
q0=r
F={r}
形式言語とオートマト
動作例
a
状態
a
a
r
状態rからスタート
(最初のaを読む)
$
例: M=<Q, Σ, δ, q0, F>
Q={r,s,t}
Σ={a}
δ:Q×Σ→Q
δ(r,a)=s δ(s,a)=t
δ(t,a)=r
q0=r
F={r}
形式言語とオートマト
動作例
a
a
状態
a
$
s
最初のaを読み終わったら
状態sに移る
例: M=<Q, Σ, δ, q0, F>
Q={r,s,t}
Σ={a}
δ:Q×Σ→Q
δ(r,a)=s δ(s,a)=t
δ(t,a)=r
q0=r
F={r}
形式言語とオートマト
動作例
a
a
$
a
状態
t
最初のaを読み終わったら
状態tに移る
例: M=<Q, Σ, δ, q0, F>
Q={r,s,t}
Σ={a}
δ:Q×Σ→Q
動作例
a
a
a
$
δ(r,a)=s δ(s,a)=t
δ(t,a)=
q0=r
F={ }
形式言語とオートマト
3つ目のa3を読み終わったら状態が
なので受理!
有限状態オートマトンの瞬時表
現
a
状態
x
$
s
a
状態
x
r
文字aを読んで状態sからrに移る
(q,ax) 
(p,x)
M
形式言語とオートマト
$
有限状態オートマトンの瞬時表
現
a1
状態
x
$
an
a1
q0
x
状態
an
$
qn
( q 0 , a 1a 2 ... a n )  ( q 1 , a 2 ... a n )  ....  ( q n ,  )
M
M
*
( q 0 , a 1 a 2 ... a n )  ( q n ,  )
M
形式言語とオートマト
M
有限状態言語
*
L ( M )  { w | w   , ( q 0 , w )  ( q f ,  )}
*
M
例
( r , baa )  ( r , aa )  ( s , a )  ( t ,  )
M
M
*
( r , baa )  ( t ,  )
M
形式言語とオートマト
M
有限状態オートマトンの状態遷移
図
r
a
s
a
形式言語とオートマト
a
t
本日の予定2
形式言語とオートマト
「有限状態言語=正規言語の生成規則」
としての正規文法
形式言語とオートマト
言語の生成装置としての形式文法
P1  S 0  aS 1
q0
P 2  S 1  aS 2
a
P3  S 2  aS 0
q1
P4  S 2  a
L={a3n}を生成する文法
S 0  aS 1  aaS
2
形式言語とオートマト
 aaaS
0
a
q2
a
L={a3n0}を受理するFSA
 aaaaS
1
 aaaaaS
2
 aaaaaa
文
法
文法(grammar)
G  N ,  , P , S 0 
非終端記号(nonterminal)
N  {S 0 , S 1 , S 2 }
終端記号(terminal)
  {a }
生成規則(production rule) P  { p1 , p 2 , p 3 , p 4 }
初期記号(initial symbol)
形式言語とオートマト
S0
言語の生成装置としての形式文法
• 変数A,B,…,S,…の置き換え規則:
変数1個で生成できる言語の例:変数はSのみ,文字
は{a,b} 置き換え規則は S→ab, S→aSbの文法
生成できる文字列は
S  ab
S  aSb  aabb
形式言語とオートマト
長さ1の文字列は生成できない
長さ2の文字列はabのみ生成できる
長さ3bは生成不可,
長さ4はaabbのみ
文
文法(grammar)
法
G  N ,  , P , S 0 
N  {S }
非終端記号(nonterminal)
終端記号(terminal)
  { a , b}
生成規則(production rule)
P  { S  ab , S  aSb }
初期記号(initial symbol)
S
形式言語とオートマト
対応:文法~言語~オートマト
ン
オートマトン(左)と文法(右)の対応する階層性
FSA
正規文法
PDA
文脈自由文法
LBA
文脈依存文法
TM
句構造文法
形式言語とオートマト
文法例1(文脈自由文法)
文法(grammar)
非終端記号(nonterminal)
終端記号(terminal)
生成規則(production rule)
初期記号(initial symbol)
G  N ,  , P , S 0 
N  {S }
  { a , b}
P  { S  aSb , S  ab }
S0  S
=導出=
S  aSb  aaSbb  aaaSbbb  aaaaSbbbb
L  {a b }
n
形式言語とオートマト
n
 ..... a b
n
n
文法例2(文脈自由文法)
文法(grammar)
G  N ,  , P , S 0 
非終端記号(nonterminal) N  {S }
  { a , b , c}
終端記号(terminal)
生成規則(production rule) P  { S  aSb , S 
初期記号(initial symbol)
S0  S
ab , S  c }
=導出=
S  aSa  abSba  abaSaba  abaaSaacaa ba
L  { wcw
形式言語とオートマト
R
| w  { a , b} }
*
文法例3(文脈自由文法)
文法(grammar)
G  N ,  , P , S 0 
非終端記号(nonterminal) N  {S }
  { a , b}
終端記号(terminal)
生成規則(production rule) P  { S  aSa , S  bSb , S  aa , S  bb }
初期記号(initial symbol)
S0  S
=導出=
S  aSa  aaSaa  aabSbaa  aabaabaa
L  { ww
形式言語とオートマト
R
| w  { a , b} }
*
については
次回も詳しく説明します。
小テストで文法に慣れましょ
う!
形式言語とオートマト

similar documents