形式言語とオートマトン 講義資料 ver.1.8 b(2013/4/24) 教科書 オートマトン 言語理論 計算論 Ⅰ (第2版) J.ホップクロフト・R.モトワニ・J.ウルマン 授業資料 http://thales.philos.k.hosei.ac.jp/automaton/ 何をする学問分野か? 次の1~3のための統一的な枠組み 1. 言語理論として: プログラミング言語、通信プロトコル、知識表現 2. 計算論として: 計算の限界、計算の量 3. オートマトンとして: アルゴリズムとその表現 他の科目との関係 • 計算量の理論(2年後期) • コンパイラ(3年前期) – 形式言語の応用分野 • コンパイラ演習(3年前期) – コンパイラ作成 • プログラミング言語理論・設計(3年後期) – プログラミング言語の基礎理論 学習の目標 • • • • オートマトンの概念を理解する(今日) 簡単なオートマトンが設計できる 正則表現が書ける 文法が表す言語が判る 以上に加えて、 • コンピュータに関する理論のトレーニング • 情報・計算システムについて語るためのリテ ラシー 例題 狼と山羊とキャベツをもった男が川の左岸から 右岸に舟で渡ろうとしている。 • 舟は小さいので3つのうち1つしか積めない。 • 男が見張っていないと… – 狼は山羊を食べる – 山羊はキャベツを食べる 3つの品物を右岸に運べるか? YESならどうやって?NOならなぜ? システムの記述 男M,狼W,山羊G,キャベツCを川の左右の岸に 応じてハイフン ー の左右に書く。 はじめ: MWGC ー 男が山羊を右岸に運ぶと、 WC ー MG と変わる。この状態が変化する様子を次のよう に表す g WC ー MG MWGC ー 可能な遷移すべてを図示 =状態遷移図 g MWGCー m WCーMG g MWCーG m w CーMWG w c c WーMGC 状態遷移図の性質 • 状態の数は有限 • 矢印(のラベル)の種類は有限 – (例の場合、g, m, w, c) • したがって図全体として有限 (有限状態系) • ゴールに至るラベルの列が答え (一通りとは限らない!) 例からわかったこと • 問題の答えは状態遷移図を描けば経路(の 存在)としてわかる。 • 与えられた手順(行為の列)が答えか否かは そのとおり状態遷移図をたどっていけるか否 かでわかる。(解か否かを認識できる) – 例: gmwwcgwmgは解か? 上のように状態遷移図を認識装置とみなしたも のを(有限)オートマトンという。 レポート問題1 白石○3つと黒石●2つを横一直線にならべる。 真ん中の石を左、右の端に移動させる操作l , r によって並べ替えることを考える。 ○○○●●から始めて、白黒の色の並びが左 右対称になるように並べ替えたい。 1. 操作回数が最小の手順は何か? 2. rlllrrlrrlは解か? 言語との関係 • 解となる記号列全体はどのような集合か? • 逆に、与えられた(有限とは限らない)集合の 要素だけを認識する方法は何か? – C言語の正しいプログラムかどうかは有限オート マトンで判定できるか否か? 記号列の集合=(形式)言語 言語とオートマトン 言語を認識するオートマトンは? オートマトンで 認識できる 言語の集合 有限オートマトン の集合 オートマトンが認識する言語は? 通信プロトコルへの応用 “RFC793” TCP接続状態遷移図 これからの内容 • 有限オートマトンと言語を取り扱うための数学 の準備 – 論理、集合、関係、グラフ、帰納法 • オートマトンと正則言語の等価性と変換方法 • オートマトンで認識できない言語 • もっと表現力豊かな言語~文法で表される言 語 数学的準備 • • • • • • • 記号列 集合 グラフ 帰納的定義 構造帰納法 論理 関係と関数 記号列 • 記号(symbol) ― 定義なしで用いる対象 • 記号列(string) ― 記号の有限個の並び. 語(word)ともいう。 例 a, b, cが記号のとき abbacは記号列 • 記号列w を構成する記号の数をw の長さといい |w|であらわす。 例 記号列w がabbacであるとき|w|=5 • 長さが0である(記号がひとつもない)記号列のこ とを e と書き、空語(empty word)と呼ぶ。 | e |=0 接頭語と接尾語 • 記号列w の先頭のいくつかの記号の並びからなる 語をw の接頭語(prefix)という。 w そのものと空語e もまた w の接頭語である。 例 abbはabbacの接頭語。 abcはabbacの接頭語ではない • 同様に、記号列w の末尾のいくつかの記号の並び からなる語をw の接尾語(postfix)という。 w そのも のと空語e もまた w の接尾語である。 • wの接頭語でwとは異なるものをw の真の(proper) 接尾語という 問 記号列abbacの接頭語をすべて挙げよ。 連接 • 2つの記号列u,v をこの順に繋げてできる新しい 記号列w をuとv の連接(concatenation)といいuv であらわす。 例 hot とdogの連接はhotdog (空白をあけてはいけない) 注:記号列wと空語の連接はw(eは連接の単位元) we = e w = w • 記号列wのn個の連接 ww … w をwnとかく w0 = e と定義する n個 言語 • 記号の有限集合をアルファベット(alphabet)と いう。 例 {a,b,…z}, {0,1}はそれぞれアルファベット • あるアルファベットに属する記号の列の集合 を言語(language)と呼ぶ。 注:空集合φもまたひとつの言語である。 {e }(空語1つだけからなる言語)と区別せよ • アルファベットSに属する記号のすべての列 の集合をS *とかく。 言語の例 - 回文 • 前から読んでも後ろから読んでも同じになる 言葉を回文(palindrome)という。 例 たけやぶやけた わたしまけましたわ • 語wの記号の順序を逆にしたwRであらわす。 • アルファベットS 上の回文とは、 S *の要素wでwR = wとなるもの。 S = {0,1}上の回文全体は言語である。 集合 • 集合(set) 特定の性質をもつものの集まり • x が集合A の要素(element)であることをx∈A 、そうでな いないことは x∈Aとかく / • 集合Bの要素がすべて集合Aに含まれるとき、 BはA の部分集合(subset)であるといい、B ⊆Aとかく。 • 「xについて命題Pが成り立つ」ことをP(x)とかく • P(x)となるx全体の集合を{x|P(x)} また集合Aの要素xでP(x)となるもの全体の集合を {x∈A |P(x)}のように書く。 例 {w∈S *| wR = w} S上の回文全体 • {f(x1,…, xn)|P(x1,…, xn)} P(x1,…, xn)となるx1,…, xn から つくられるf(x1,…, xn)全体の集合 集合に対する演算 AとBを集合とする A∪B={x | x∈A またはx∈B} (AとBの和, union) A-B={x | x∈A かつx∈B} / (AとBの差, difference) A∩B={x | x∈A かつx∈B} (AとBの共通部分, intersection) A×B ={(x, y)| x∈A, y∈B} (AとBの直積, Cartesian product) 2A ={X|X⊆A} ( Aのべき集合, power set ) 問 A ={1, 2}, B={2, 3}として上の集合を求めよ。 言語に対する演算 A,B,Cを言語とする AB={xy | x∈A, y∈B} (AとBの連接) ABC= A(BC) = (AB)C An = AA…A (n個, n>0) A0 ={e} A*= A0 ∪ A1 ∪…= ∞ ∪i=0 A i (Aの閉包) 問 A ={0, 1}, B={2}, C={2}として上の言語を求めよ。 グラフ • グラフGは頂点(vertexまたはnode)の有限集 合Vと頂点の対で表される辺(edge)の有限集 合Eの組であってG=(V,E)で表される。 例 V={1,2,3,4,5}, E={(1,3), (3,4), (2,5), (2,2)} のときグラフ(V,E)は 1 5 3 2 4 • グラフの頂点の列v1,v2,…vkが道(path)である とは(v1,v2),(v2,v3),…(vk-1,vk)が辺であること。 有向グラフ • 有向グラフはグラフの辺の向きを考慮したもので やはりG=(V,E)で表す。辺の代わりに有向辺(arc) といい、u→vのように書く。 • 有向グラフの頂点の列v1,v2,…,vkが道であるとは v1→v2, v2→v3,…vk-1→vkが有向辺であること。 問 有向グラフ({x∈N|0<x<5},{i→j | i<j}) を図示せ よ。 (Nは自然数の集合) • v1,v2,…,vkが(有向)グラフGの道であってv1=vkであ るとき、道v1,v2,…,vkは閉路(cycle)であるという。 レポート問題3 1. a,b,cを記号とする。記号列x,y,zをそれぞれabc, bb, abcab と す る と き 、 |xyz|,|xxx|,|xeyeze|,|xjykzl|はいくらか? 2. a,b,c,d を記号とし、A={a,b}, B={b,c,d}とする とき、 次の言語の要素を書き下せ。 ① AAB ② {w∈A* | |w| < 5} 3. V={0,1,2,3,4,5,6,7}, E={i→j | i, j ∈ V, j = i2%8 }と するとき、 G=〈 V, E 〉を図示せよ。 (m%nはmをnで割った余りを表す。) 帰納的定義(inductive definition) 例 自然数の定義 • 0は自然数 [基礎(base)] • 自然数nに1を加えたものn+1は自然数 [帰納ステップ(inductive step)] • 上のようにして得られたものだけが自然数 木の帰納的定義 • 基礎: 頂点1個だけで有向辺を持たない有向 グラフは木であり、その根はその唯一の頂点。 • 帰納ステップ:1個の頂点rと、( rを頂点とせ ず、また互いに頂点を共有しない)有限個の 木T1,…,Tkの根はr1,rkをk本の有向辺r→r1, …,r →rkで繋いで合成した有向グラフ Tree(T1,…,Tk)は木で根はr • 上のようにして構成した有向グラフだけが木 T0 Tree(T1,…,Tk) r r1 T1 r … ならば … rk Tk r1 … rk 帰納法 数学的帰納法: すべての自然数nに対して命題P(n)がなりたつことを 証明する方法 1. P(0)がなりたつ。 2. P(k)がなりたつと仮定すれば(帰納法の仮定)、 P(k+1)がなりたつ。 1,2から「すべての自然数nに対してP(n)がなりたつ」 ことが推論できる。 構造帰納法 • すべての木で「頂点の数は有向辺の数より1つ多い」こと を証明する。 木Tについて上の「…」が成り立つことをP(T)と書く。 木Tの頂点の数をn(T)、有向辺の数をe(T)と書く。 帰納法による証明 基礎: P(T0) (∵ n(T0)=1, e(T0)=0) 帰納ステップ: P(T1), P(T2), …, P(Tk) ならばP(Tree(T1,…,Tk)) (∵ e(Tree(T1,…,Tk))= e(T1) +…+ e(Tk) + k n(Tree(T1,…,Tk))= n(T1) +…+ n(Tk) + 1 = (e(T1) + 1) +…+ (e(Tk) + 1) + 1 (帰納法の仮定) = e(T1) +…+ e(Tk) + k+ 1 これらからすべての木Tに対してP(T)と推論してよい。 レポート問題4 S ={0,1}のとき、 言語Lを次のように帰納的に定義する 1. e, 01, 10 はLの要素 2. x, yがLの要素のとき、 xyはLの要素 Lの要素はすべて0と1の数が同じであることを 構造帰納法で示せ。 レポート問題5 Sをアルファベットとする言語Lを 次のように帰納的に定義する 1. e∈L 2. a∈S、x∈Lのとき、 axはLの要素 このとき、 L = S*であることを示せ。 (ヒント) L ⊆ S*は自明。逆を長さに関する帰 納法で示せ。 論理 ∀x.P(x) 「すべてのxについてP(x) 」 ∃x.P(x) 「あるxについてP(x) 」 あるいは、 ∀x∈A.P(x) 「Aのすべての要素xについてP(x)」 などと書く。 ∀を全称限量子(universal quantifier) ∃を存在限量子(existential quantifier)という。 関係 • 集合AとBの間の(2項)関係とは AとBの直積 A×Bの部分集合のこと。 • A上の関係、というときはAとAの間の関係 R⊆A2のことを指す。 • Rが集合AとBの間の関係であるとき、 (a, b)∈Rであることを、(記号Rを演算子のよう に用いて)aRbのように書く。 関数 集合AとBの間の関係 f は次の2条件を満たすとき AからBへの関数(写像)であるといい、f : A → Bと書く。 (存在) ∀x∈A.∃y∈B. xfy (唯一) ∀x∈A.∀y1∈B .∀ y2∈B . xfy1∧ xfy2 ⇒y1=y2 f : A → Bであるとき、 afbのかわりにf: a |→ bと書く。 afbとなるただ一つのb∈B をf (b)で表す。 集合Aをfの定義域、 Bをfの値域と呼ぶ。 関数f : A→Bは値域Bが明らかであるか、もしくは度外視する場合は 単にA上の関数という。 すすんだ用語: 関数f : A → Bにおいて、 集合X⊆Aに対して、{f (x)| x∈X} ⊆B をXのfによる像(image)といいf [X]で表す。 とくに定義域Aの像f [A]のことをIm(f)と書く。 (上の定義と異なり、Im(f)のことを値域と呼び、Bを終域と呼んで区別する立場もある。) 関数の定義から(存在)の条件を除いたものを部分関数(写像)と呼ぶ。 部分関数では{ x∈A | ∃y∈B. xfy }を定義域, Aを始域と呼んで区別する。 関数の帰納的定義 関数f :A → Bを集合(⊆A×B)として帰納的に定義するこ とをいう。 大抵の場合、Aの帰納的定義におけるAの要素の定義と同時にf によって対応づけられる値を定義するように変更すればよい。 例: 記号列に対してその長さを対応づける関数 f :S* → Nは次のように帰納的に定義される。 [基礎] (e∈S*であって、) f(e) = 0 [帰納ステップ] a∈S, x∈S* のとき、 (ax∈S*であって、) f(ax) = f(x)+1 レポート問題6 S ={0,1}のとき、 Sの語wを引数とし、2進数と 解釈したときの値を返す関数 j :S*→N を 帰納的に定義せよ。( 0以外で先頭の0は無 視し、 eに対する値は0とする。) (0以外に0から始まる語はない)正しい2進数お よびその値を定義するように上を修正せよ。 eも除外のこと。 有限オートマトン 決定性有限オートマトン(DFA)Mは次の5つ組 で定義される。 M=<Q, S, q0, d, F> Q : 状態(state)の有限集合 S : 入力アルファベット q0 : 開始状態(初期状態とも) (∈ Q ) d : Q×S → Q 遷移関数 d (q, a) =p は状態qのときaを読んだとき 次の状態がpであることを表す F : 最終状態(受理状態とも)の集合 (⊆ Q ) 遷移表 遷移関数を表で表したものを遷移表という。 0 1 → q0 q2 q0 * q1 q1 q1 q2 q2 q1 →は開始状態、*は最終状態を表す 上の遷移表が表す遷移関数を図で表せ。 遷移関数 d (q, a) =pを図で表す。 p a q 状態遷移図 0 q2 0 1 開始 q0 1 q1 0,1 オートマトンが受理する言語 DFAが受理する言語の直観的な説明 入力記号列を w=001001 とする 0 0 1 0 0 q2 1 0 q0 q2 q 2 q1 q1 q1 q1 0 開始 q0 1 q1 1 受理状態に導く語全体の集合を DFA Mの受理する言語と定義する。 0,1 遷移関数の拡張 入力記号列(の接頭語)を読んだときの状態を返 す関数dˆ: Q×S* → Qを次のように帰納的に定 義する。(☞入力記号列の長さに関する帰納法) (基礎) dˆ(q, e) =q (帰納ステップ) dˆ(q, xa) = d (dˆ(q, x), a) ただしa∈S, x∈S*とする。 拡張された遷移関数の計算 dˆ(q0, 001001) = d (dˆ(q0, 00100), 1) = d (d (dˆ(q0, 0010), 0), 1) = d (d (d (dˆ(q0, 001), 0), 0), 1) … = d (d (d (d (d (dˆ(q0, 0), 0), 1), 0), 0), 1) = d (d (d (d (d (d (dˆ(q0, e), 0), 0), 1), 0), 0), 1) = d (d (d (d (d (d (q0, 0), 0), 1), 0), 0), 1) = d (d (d (d (d (q2, 0), 1), 0), 0), 1) … = q1 受理言語の定義 DFA A=<Q, S, d, q0, F> が受理する言語L(A)は次で定義される。 L(A) ={w∈S*|dˆ(q0, w)∈F} (受理状態に導く入力記号列全体の集合) また言語Lは、あるDFA Aを用いてL = L(A) とかけるとき正則(regular)であるという。 正則な言語を正則言語(regular language)と呼ぶ 正則言語の例 接頭語01を持つ語(∈{0,1}*)全体の集合は正則 か? ヒント:定義より当該言語を受理する DFAが存在すれば正則。 q2 1 0 開始 0 q0 q1 0,1 1 q3 0,1 レポート問題7 次の言語を受理するDFAを設計せよ。 1. 0と1が交互に並ぶ語全体。ただし、e, 0,1も この言語の語であるものとする。 2. 1がちょうど3回現れる語全体 3. 2進数とみなせる列全体 4. (やや難)3で割り切れる2進数全体 正則言語の例その2 接尾語01を持つ語全体の集合は正則か? q2 0 1 開始 q0 q1 0,1 これはDFAではない! 非決定性 DFAを変更して同じ入力記号に対して(0個を含 む)複数の状態のいずれかに遷移可能にな るようにする。 このように変更された有限オートマトンを 非決定性有限オートマトン p (Nondeterministic FA, NFA)と呼ぶ。 a NFAの状態遷移図では 同一ラベルの辺が q a 複数出てよい。 r NFAの定義 DFAからの変更点は遷移関数dのみ d : Q×S → 2Q d(q, a) =P(⊆Q)は状態qでaを読んだとき 次の状態がPの任意の要素pになり得ること を表す。 言い換えれば、 d(q, a) は状態qでa読んだとき に遷移できる行き先全体の集合 NFAの例 M=<{q0, q1, q2}, {0, 1}, d, q0, {q2}> d q1 φ {q2} * q2 φ φ 1 開始 q0 1 {q0} → q0 q1 0 0 {q0 , q1} q2 0,1 NFAが受理する言語 直観的な説明 NFAは入力記号を読むたびに可能な遷移のう ちどれか1つを選んで遷移する。 うまく選んで、入力記号列を読み終わった直後 に受理状態に居るようにできればその入力は 受理される。 受理される記号列全体の集合をそのNFAの 受理する言語という。 NFAが受理する言語の例 末尾が01であるような語全体を受理するNFA q2 0 1 開始 q0 q1 0,1 このNFAがw=1001を受理することを確かめよ。 遷移関数の拡張(NFA版) 入力記号列(の接頭語)を読んだときの状態を返 す関数dˆ: Q×S* → 2Qを次のように帰納的に定 義する。(☞入力記号列の長さに関する帰納法) (基礎) dˆ(q, e) ={q} (帰納ステップ) dˆ(q, xa) = ただしa∈S, x∈S*とする。 ∪ d (p, a) p∈dˆ(q, x) 拡張された遷移関数の意味 # # Q Q d : 2 ×S → 2 を d (P, a) =∪ d (p, a) p∈P で定義すると、(帰納ステップ)の右辺は ∪ d (p, a) = d#(dˆ(q, x), a) p∈dˆ(q, x) のように書ける。 問1 DFA版のものと比較せよ。 問2 dˆ(q, x)={p1, …, pn}のとき上の式をp1, …, pnを用いて表せ。 NFAが受理する言語 厳密な定義 NFA A=<Q, S, d, q0, F> が受理する言語L(A)は次で定義される。 L(A) ={w∈S*|dˆ(q0, w)∩F≠φ} 平たく言えば… dˆ(q0, w)は、 wを読んで行ける状態全ての集合。 L(A)は「各ステップで遷移先をうまく選べば受理状 態に行ける入力記号列全体の集合」 問 例のNFAについてdˆ(q0, 1001)∩F≠φを確か めよ NFAとDFAの等価性 • オートマトンの2つのクラスは片方のクラスに 属すオートマトンの受理言語が他方に属す オートマトンでも受理できるとき、等価である、 という。 以下でNFAとDFAが等価であること を示す。 DFA NFA MD L(MN)=L(MD ) MN サブセット構成 サブセット構成(subset construction): NFA N=<QN, S, dN, q0, FN>が与えられたとき L(N) を受理するDFA D=<QD, S, dD, {q0}, FD> を次のようにして構成する。 QDはQNの部分集合全体( QNのべき集合) FDはQNの部分集合SでS∩FN≠φを満たすもの 全体の集合 S (⊆QN)とa∈Sに対して、 dD(S, a)=∪ dN (p, a) p∈S サブセット構成の例題 次を繰り返す。 1. 左欄が空でない行について表を埋める 2. 左欄にない集合が出たら左欄に追加 →{q0} 0 {q0, q1} 1 開始 0 q0 q1 1 q2 0,1 サブセット構成で得られる遷移図 • ノードのラベル(名前)として集合を使うと構成 過程がわかりやすいが最終的には必要ない。 • ラベルを通常の記号に付け替えて遷移図を 完成せよ。 サブセット構成の正当性 サブセット構成によってNFA N=<QN, S, dN, q0, FN>から DFA D=<QD, S, dD, {q0}, FD>を構成したとき L(D) =L(N)が成り立つ。 [証明] dˆD ({q0},w) = dˆN (q0, w) を示す |w|に関する帰納法: (基礎) dˆD({q0},e) = dˆN(q0, e) = {q0} (帰納) dˆD({q0},xa) = dD (dˆD({q0}, x), a) ( dˆDの定義) = dD (dˆN(q0, x), a) (帰納法の仮定) =∪ dN(p, a) p∈dˆN(q0, x) = dˆN (q0, w) (dDのサブセット構成) ˆNの定義) (d 等価性 • 言語LがあるDFAで受理されるための必要十 分条件はLがあるNFAで受理されること。 [証明]あるDFAで受理⇒あるNFAで受理 だけ言えばよい。次のようにd Dからd Nを構成 dD (q,a) =p のときd N (q,a) = {p} 問い 受理状態について確認せよ。 NFAの拡張:e 動作 +-符号つき10進数(整数)を受理するNFA 開始 1, …, 9 +,- 0, 1, …, 9 0 符号がない場合もあるとすると 1, …, 9 開始 +,- 1, …, 9 0 これをもっと簡単に書きたい。 0 0, 1, …, 9 e 動作を含むNFA e 動作を含むNFA(e -NFA) A=<Q, S, q0, d, F> はNFAの遷移関数を次のように変更して定義 される。 変更前 d : Q×S → 2Q 変更後 d : Q×(S∪{e }) → 2Q 遷移図では が許される。 e この図が表す遷移をe -遷移という。 e -NFAの例 符号がない場合もありうる+-符号つき10進 数(整数)を受理するe -NFA 開始 +, -, e 1, …, 9 0 0, 1, …, 9 遷移関数を拡張するための準備 q∈Qのe-閉包(e -closure) ECLOSE(q)⊆Qを 次のように帰納的に定義する。 基礎: q∈ECLOSE(q) 帰納: p∈ECLOSE(q)かつr∈d (p, e)ならば r∈ECLOSE(q) ECLOSE(q)はqからe -遷移だけをたどって到達でき る状態すべての集合である。 e-閉包の例 e e 2 e 3 6 1 e b 4 5 a ECLOSE(1)={1,2,3,4,6} ECLOSE(2)={2,3,6} ECLOSE(4)={4} e 7 遷移関数の拡張(e -NFA版) dˆ: Q×S* → 2Qを次のように帰納的に定義する (基礎) dˆ(q, e) = ECLOSE(q) (帰納ステップ) dˆ(q, xa) = ∪ ECLOSE(r) r∈∪d (p, a) ˆ p∈d (q, x) ただしa∈S, x∈S*とする。 上の定義でたとえば dˆ(q, x)={p1, …, pk},∪ki=1d(pi,a)={r1,…,rm} とすると、帰納ステップの右辺は∪mj=1ECLOSE(rj) (参考) 見通しをよくする記法 # NFAのときと同様にd : 2Q×(S∪{e}) → 2Q を # d (P, a) =∪ d (p, a) p∈P と定義し、さらに、 # ECLOSE (R)=∪ECLOSE(r) r∈R のように書くことにすると、帰納ステップの右辺は ECLOSE#(d#(d(q, x), a)) e -NFAの受理する言語 e -NFA A=<Q, S, d, q0, F>が受理する言語は L(A) ={w∈S*|dˆ(q0, w)∩F≠φ} で定義される。 (e無しの)NFAとの相違点はdˆがe -NFA版の 拡張された遷移関数dˆ: Q×(S∪{e })*→ 2Q である点のみ。 e -NFAとDFAの等価性 e -NFA E=<QE, S, dE, q0, FE>が与えられたとき, Eが受理する言語L(E) と同じ言語を受理するDFA D=<QD, S, dD, qD, FD>を次のようにして構成する。 QDはQEの部分集合SのうちS=∪ECLOSE(p)なるもの全体 p∈S qD=ECLOSE(q0) FDはQEの部分集合SでS∩FE≠φを満たすもの全体の集合 S (⊆QE)とa∈Sに対して、 ∪ dD(S, a)= ECLOSE(r) r∈∪ dE(p, a) p∈S (Sの要素から出発してaで遷移した後,e-遷移だ けで到達できる状態全体の集合) (参考)問 前ページの記法で右辺を書き直せ。 e -NFAとDFAの等価性 (1/2) e -NFA E=<QE, S, dE, q0, FE>から前頁にしたがって DFA D=<QD, S, dD, ECLOSE(q0), FD>を構成したとき L(D) =L(E)が成り立つ。 [証明] dˆD (ECLOSE(q0),w) = dˆE (q0, w) を示す |w|に関する帰納法: (基礎) dˆD(ECLOSE(q0),e) = dˆE(q0, e) = ECLOSE(q0) (帰納) dˆD(ECLOSE(q0),xa) = dD (dˆD(ECLOSE(q0), x), a) = dD (dˆE(q0, x), a) (帰納法の仮定) ∪ECLOSE( ) = r r∈∪ dE(p, a) (dDの構成) p∈dˆE(q0, x) = dˆE (q0, xa) ˆEの定義) (d e -NFAとDFAの等価性 (2/2) DFA D=<Q, S, dD, q0, F>に対して同じ言語を受 理するe -NFA Eが存在する。 [証明] E=<Q, S, dE, q0, F>ただし dE(q, a) = {dD(q, a)} (a∈S) dE(q, e) = φ とすればよい。 e -NFAからDFAを構成する方法 NFAから構成する方法(サブセット構成)で得ら れる遷移先集合の各要素のe -閉包の和集合 を遷移表エントリとして表を埋めていく。 a d(p1, a)∪…∪d(pk, a) ECLOSE(q0) … … … … … {p1, …, pk} {s1, …, sn} ={r1, …, rm} ECLOSE(r1)∪… ∪ECLOSE(rm) ={s1, …, sn} e -NFA→DFA構成の例 下のe -NFAと等価なDFAを求めよ。 1 1, e 0 1 開始 0 0 1 1, e 2 1 オートマトンの利用法:字句認識 符号つきの整数および小数を認識するe -NFA (0から始まる整数は0だけ。符号なしも可) 問 入力ファイルが上記の数を含むか否かを調 べるCプログラムを作成せよ。 正則表現 正則表現(または正規表現ともいう。regular expression, RegExp)はオートマトンが受理す る言語を簡便に表す方法(一種の言語)であ り、以下の性質をもつ。(証明はあとで。) 1. オートマトンが受理する言語はすべて正則表 現で表すことができる。 2. 逆に、正則表現で表した言語はオートマトン で受理することができる。 以下で正則表現Eの表す言語をL(E)と書く。 正則表現の定義 正則表現とその表す言語は次のように帰納的に定義される。 基礎: 1. 定数e, φは正則表現で、L(e)={e}, L(φ)=φ 2. aが記号のとき、aは正則表現でL(a)={a} 帰納: 1. E, Fが正則表現のとき、E+Fは正則表現で L(E+F)=L(E)∪L(F) 2. E, Fが正則表現のとき、EFは正則表現で L(EF)=L(E)L(F) 3. Eが正則表現のとき、E*は正則表現でL(E*)=L(E)* 4. Eが正則表現のとき、(E)は正則表現でL((E))=L(E) 演算子の結合順位 帰納的定義に現れる演算子の結合は *, 連接, + の順に強い。例えば、 L(E+FG*) = L(E+(F(G*))) = L(E)∪L(F)L(G)* 注:集合および言語の演算子の結合順位は上から強い順に、 1. *, べき 2. 連接 3. ∪, ∩, - 正則表現定義の早見表 正則表現 E e φ a E+F EF E* (E) L(E) {e} φ {a} L(E)∪L(F) L(E)L(F) L(E)* L(E) 演算子の結合は上から弱い順 (+が最も弱く、 * が最も強い。) 正則表現が表す言語の例 01*+1が表す言語 L(01*+1)=L(01*)∪L(1) =L(0)L(1*)∪L(1) =L(0)L(1)*∪L(1) ={0}{1}*∪{1} ={0}{e,1,11,111,…}∪{1} ={0,01,011,0111,…}∪{1} 「1個の0の後に1だけが0個以上続く語および1」 レポート問題8 次の条件を満たす語全体からなる言語をそれぞ れ正則表現で表せ。(S={0,1}) • • • • 0がちょうど3回現れる。 条件なし。(すべての語) 0が3回以上現れる。 同じ記号が3つ以上連続しない。 正則表現の略記法 E? = e + E (0回か1回) 問 前頁の正則表現を略記法で書け。 有限オートマトンと正則表現の等価性 有限オートマトンが受理する言語のクラスと正 則表現で表わされる言語のクラスは等しい。 クラスAの任意の言語がクラスBに属すことを A B のように記すと、 e-NFA NFA RegExp DFA DFAが受理する言語は正則表現で表される (証明)DFA Aの状態を{1, 2, …, n}とする。 kより大きい状態を経由せずに状態iから状態jに至る経路 に沿ってラベルをつなげたもの全体を表す正規表現 Rij(k)は次のように帰納的に定義できる。(経路の両端 ijはkを越えてもよい。) [基礎] (i≠jの場合) 1. 2. 3. Rij(0)=f (辺i→jがないとき) Rij(0)=a (辺i→jはaをラベルとするものだけ) Rij(0)=a1+a2+…+am(辺i→jのラベルはa1, …, am) (i=jの場合) 1. 2. 3. Rij(0)=e (辺i→iがないとき) Rij(0)=e+a (辺i→iはaをラベルとするものだけ) Rij(0)=e+a1+a2+…+am(辺i→jのラベルはa1, …, am) (証明つづき) [帰納] Rij(k)=Rij(k-1)+Rik(k-1)(Rkk(k-1))*Rkj(k-1) Rik(k-1) i Rkk(k-1) k Rkj(k-1) … k j Rij(k-1) これをもちいて、受理言語を表す正則表現は R1f1(n)+…+R1fp(n) と書ける。ただし{ f1, …, fp}は受理状態の集合 状態消去法(1/3) R11 q1 Q1 ..... ..... S p1 R1m P1 s Pm Qk qk Rkm pm Rk1 状態消去法(2/3) q1 R11+Q1S*P1 ..... ..... Rk1+QkS*P1 qk p1 R1m+Q1S*Pm Rkm+QkS*Pm pm 状態消去法(3/3) すべての受理状態qについてqと開始状態以外 を消去する。 R S U 開始 (R+SU*T)*SU* T 開始 R R* 得られた正規表現をすべて+でつなぐ。 状態消去法の適用例 次のDFAが受理する言語を正則表現で表せ。 3 0 開始 1 1 1 0 1 4 1 2 0 0 3 0 1 1 1 0 0 1 1 1 4 1 1 1 2 2 3 0 1 0 10*1 1 3 0 10*1 10*1 0 0 1 1 4 1 10*1 3 z=10*1 z 3 0 0 z 1 1 0 4 1 4 0 3 z 3 0 1 z+01 0 3 01 00 3 (z+0(00)*(z+01))*0(00)* 1 00 1 3 z 3 0 1 z 1 0 0 1 0 3 1 4 4 z+0z 1 00 00 1+0z 4 1 0 4 1 0z 00 0z 4 (z+0z+00(00)*(1+0z))*00(00)* 0 z 00 4 z=10*1, y=0(00)*として以上をまとめると、 (z+y(z+01))*y+(z+0z+0y(1+0z))*0y McNaughton-Yamadaの構成法(1/2) 正則表現からe-NFAを構成する方法 N(R) – 正則表現Rがあらわす言語を受理し、 – 受理状態が一つだけで、開始状態へ入る辺、最 終状態から出る辺がないもの。 N(R) McNaughton-Yamadaの構成法(2/2) N(R)の帰納的定義 4. N(R+S) 1. N(f) e e 2. N(e) e N(S) e N(R) e 5. N(RS) N(R) 3. N(a) e N(R) e N(S) e a 6. N(R*) e e 山田先生の業績 • McNaughton-Yamada construction(1960) – オートマトン理論の基礎理論 • Real-Time computation(1962) – 計算量理論を創始 • Tessellation automata(1971) – セル構造オートマトン初期の研究 • T-code (1980’s) – 無連想打鍵方式による日本語入力の発明 山田 尚勇 (1930-2008) 適用例 (10+01)* であらわされる言語を受理するe-NFA を構成せよ。 正則表現の応用1:字句解析生成系 lex, flex delim ws letter digit id number %% {ws} if then else {id} {number} [ \t] {delim}+ [A-Za-z] [0-9] {letter}({letter}|{digit})* {digit}+(\.{digit}+)?(E[+|-]?{digit}+)? {} {return(IF);} {return(THEN);} {return(ELSE);} {yylval=install_id();return(ID);} { sscanf(yytext,"%d",&yylval);retur n(NUM);} "<" {yylval=LT;return(RELOP);} "<=" {yylval=LE;return(RELOP);} "=" {yylval=EQ;return(RELOP);} "<>" {yylval=NE;return(RELOP);} ">" {yylval=GT;return(RELOP);} ">=" {yylval=GE;return(RELOP);} %% int install_id(){ /* 変数名を記号表に登録して表のエントリへの ポインタを返す */ /* ここにコードを書け */ /* 注)この関数が呼び出されたとき、 字句の先頭はyytext、字句の長さは yyleng に入っている。 (ここではこの変数で参照できる。) number {digit}+(\.{digit}+)?(E[+|-]?{digit}+)? number {digit}+ */ return 0; } int install_num(){ sscanf(yytext,"%d",&yylval); } 正則表現の応用2:検索コマンド egrep ‘正則表現’ ファイル名 % egrep ‘yy+|return’ foo.l 正則言語の性質 1. 言語が正則でないことの証明方法:反復補題 2. 最小のオートマトン:Myhill-Nerodeの定理 正則言語でないこと L01={0n1n| n≧1} L01が状態数kのDFA Aで受理されると仮定する。 入力が0n1n (n>k) のとき、n個の0を読むうちに2 度訪れる状態が少なくとも1つある。(i個目とj 個目とする。i≠j) 0i1iと0j1iを考える。0iを読み終えた状態と0jを読 み終えた状態は同じなのでその後の入力1i が同じなら到達する状態も同じ。これは矛盾。 反復補題 反復補題(ポンプの補題、pumping lemma) Lを正則言語とする。このとき、Lに依存する 定数nで次の条件を満たすものが存在する。 条件: |w|≧nを満たす任意の記号列w∈Lは次の (1)~(3)を満たす3個の部分列の連接w=xyz に分解できる。 (1) y≠e (2) |xy|≦n (3) ∀k ≧0 に対して、xykz∈L 反復補題の証明 Lが状態数nのDFA Aで受理されると仮定する。 wを長さn以上の任意の文字列∈Lとする。w=a1a2…am (m≧n)とする。 i=0,…,mに対して記号をi個読み終 えた時の状態をpiと書くことにする。すなわち、 pi=dˆ(q0, a1a2…ai) (i=1,…,m). p0=dˆ(q0, e) (i=0). 状態は全部でn個だったからp0,…,pmのうちには同じも のが少なくとも2つある。これらをpi,pjとする。(pi=pj)。 x=a1a2…ai y=ai+1…aj z=aj+1…am とせよ。これらは条件(1)~(3)を満たす。(示せ。) 条件を満たすこと(ヒント) y=ai+1…aj a1 p0=q0 p1 x=a1a2…ai pi=pj pm z=aj+1…am 反復補題の応用 L01={0m1m| m≧1}は正則でない [反復補題を用いた別証] L01が正則言語であると仮定する。反復補題中 の条件を満たす数をnとする。 w=0n1nとすると |w|=2n≧nであり、かつL01の要 素であるから |xy|≦n, y≠eとなるx,yによって w=xyzと分解できて、∀k ≧0 に対してxykz∈L01と なるはず。 ところが、|xy|≦n, y≠eであるならばy=0l (l>0)。 このときxy2zは0の方個数がl個多くなり矛盾。 同値関係 集合A上の関係~⊆A×Aは次を満たすとき、同 値関係であるという。 (a~b ⇔ (a,b)∈~) 1. (反射律)a~a 2. (対称律)a~bならばb~a 3. (推移律)a~bかつb~cならばa~c 同値関係~によってa~bであるとき、aとbは同 値である、あるいは、aはbと同値であるとい う。 同値類と同値類集合 ~が集合A上の同値関係であるときa∈Aに対して、aと同 値であるもの全体の集合をaの属する同値類といい、 [a]と書く。すなわち、 [a]={b∈A|a~b} Aのすべての要素aにわたって[a]を集めてできる集合をA の~による同値類集合あるいはAの~による商(集 合)いい、A/~と書く。すなわち、 A/~={[b]|b∈A} 同値類の個数すなわち同値類集合の要素数を同値関係 ~の指数(index)という。 集合A上の同値関係R,QについてRの各同値類がQの同 値類に含まれるとき(部分集合であるとき)RはQの細 分である、という。 同値類の性質 ~が集合A上の同値関係であるとき, a,b∈Aに 対して次が成り立つ。(示せ。) • a~b ならば[a]=[b] • a~b でないならば[a]∩[b]=f 状態集合上の同値関係 1つのDFAの状態集合上の同値関係≡を次で定義す る。 p≡q ⇔ すべての入力列wに対してdˆ(p, w)とdˆ(q, w)はどち らも受理状態であるかどちらも受理状態でない。 (関係≡が実際に同値関係であることを確かめよ。) 同値でない状態の対は区別可能であるという。 wが(p, q)が区別可能であることの証拠であるとき、す なわち、dˆ(p, w)、dˆ(q, w)の片方だけが受理状態で あるとき、wは(p, q)を区別するという。 同値な状態の例 0 1 開始 A 0 B 1 E 1 1 0 C D 0 1 0 1 1 F 1 G 0 0 H 0 対(C,G), (A,G),(A,E)について区別可能性を調べよ。 区別可能性の特徴づけ DFA A=<Q, S, d, q0, F> における区別可能な対 をすべて見つける再帰アルゴリズムの基礎 基礎:状態pが受理状態で状態qが受理状態でな いならば対(p, q)は区別可能 再帰:ある入力文字a対してr=d(p, a)とs=d(q, a) が区別可能ならば対(p, q)は区別可能 問 上の基礎、再帰について対(p, q)を区別する 記号列は何か? 穴埋めアルゴリズム 状態の対の表について、区別可能な対に×印 をつけるアルゴリズム 1. 片方だけが受理状態の欄に×印をつける。 2. ×印がついた対の状態の各々に同じ記号 で入る矢印を逆にたどってそれぞれp, qに 行けば(p, q)に×印をつける。 穴埋めアルゴリズムの実行 ×: 第0ステップ ×: 第1ステップ ×: 第2ステップ B C D E F G H × × × × × × × × × × × × × × × × × × × × × × × × × A B C D E F G 穴埋めアルゴリズムの正当性 定理: 穴埋めアルゴリズムで×印がつかない状態の対 は同値。(区別可能なものはすべて×印がつく。) [証明]区別可能であるにもかかわらず×印がつかない対 が存在すると仮定する。列w=a1a2…anをそのような対の どれかを区別する列で長さ最小のものとし、wが区別す る対を(p, q)とする。 wはeではあり得ない。dˆ(p, e)=p, dˆ(q, e)=qのどちらかだ けが受理状態なら基礎で×印がつけられたはず。)ゆえ n≧1 a2…anは(r, s)=(dˆ(p, a1), dˆ(q, a1))を区別する。(示せ。) a2…anはwよりも短いので(r, s)は×印されている。 (r, s)が×印されていればアルゴリズムの次の再帰ステッ プで(p, q)が×印されていなければならない。これは矛 盾。 穴埋めアルゴリズムの改良 d(p,a)=r, d(q,a)=s,r≠sのとき (r,s) (p,q) のように矢印を書いておく。 × × × O(n2)で穴埋めできる。 B C D E F G H A B C D E F G DFAの等価性 二つのDFA A,Bの状態遷移図を合成したものにつ いて、A,Bそれぞれの開始状態p,qの区別可能性 を調べる。 区別可能でない(同値)ならばA,Bは等価。すなわち、 L(A)=L(B) 開始 開始 p A q B 等価性決定手順の実行例 0 開始 開始 0 A 1 1 B 0 C 0 1 1 0 B C D E E 1 A B C D D DFAの最小化 DFA A=<Q, S, d, q0, F> の最小化は B=<Q/≡, S, g, [q0], {[s]| s∈F}> で与えられる。ここで g :Q/≡×S → Q/≡ g ([q], a)=[d(q, a)] gが定義可能であること: p≡qであるとき[d(p, a)]=[d(q, a)]を背理法で示す。 wがd(p, a),d(q, a)を区別すると仮定すると、 awはp,qを区別するのでp≡qに反する。(矛盾) 最小化の例 開始 1 A,E 1 0 0 B,H 0 0 1 G 1 0 C 1 D,F 最小化の正当性 Mを最小化で得られたDFAとする。 Nを, Mと等価で状態数がMより少ないDFAとする。 開始 開始 a1a2…ak a1a2…ak p M q N MとNの合成で状態の区別可能性を調べると、 Mの任意の状態pはNのある状態qと区別不能。 Mの状態のほうが多いから、Nの状態のうち少なくとも1つ q1はMの2状態p1,p2と区別不能。最小化ではすべての 状態は互いに区別可能のはずであり、矛盾。 語の同値関係と右不変性 言語Lに対してS*上の同値関係RLを次で定義する。 xRLy ⇔ どんなz∈S*に対してもxzとyzはどちらもLに 属すかどちらも属さない。 また、DFA M=<Q, S, d, q0, F> に対してS*上の同値関係 RMを次で定義する。(「同じ状態に導く」という関係。) xRMy ⇔ dˆ(q0, x) = dˆ(q0, y) S*上の同値関係Rは xRy ⇒ xzRyz を満たすとき、(連接に関して)右不変であるという。 RM, RLは右不変(示せ)。 同値類と細分 集合A上の同値関係R,Qについて Rのどの同値類も、Qの同値類のいずれかに含 まれるとき、RはQの細分であるという。 主張: 集合A上の同値関係R,Qについて RがQの細分すなわち、∀a∃b. [a]R ⊆ [b]Q ⇔ R⊆Q 証明: (⇒)左 ⇒∀a∃b.( [a]R ⊆ [b]Q ∧ a∈[b]Q ) ⇒∀a∃b. ( [a]R ⊆ [b]Q ∧ aQb ) ⇒∀a∃b. ( [a]R ⊆ [b]Q ∧ [a] Q= [b] Q ) (同値類の性質) ⇒∀a . [a]R ⊆ [a]Q このとき、 xRy ⇒y ∈[x]R ⇒y ∈ [x]Q⇒ xQy (⇐)任意のaに対して x∈[a]R ⇒xRa⇒(x,a) ∈R ⇒ (x,a) ∈ Q ⇒ xQa ⇒x ∈[a]Q ゆ え、[a]R ⊆ [a]Q したがって、bとしてa自体を選べばよい。 Myhill-Nerodeの定理 [定理](Myhill-Nerode)つぎの1~3は同値。 1. L∈S*は有限オートマトンの受理集合である。 2. Lは右不変で有限の指数を持つ同値関係の いくつかの同値類の和に等しい。 3. RLの指数は有限。 Myhill-Nerodeの定理の証明(1⇒2) DFA M=<Q, S, d, q0, F>がLを受理するとする。 2つの語について「同じ状態に導く」という関係 RM は右不変な同値関係である。 LはF属する状態fに導く同値類の和である。 Myhill-Nerodeの定理の証明(2⇒3) Eを右不変で指数有限の同値関係とし、LがEの 同値類の和であるとする。EがRLの細分であ ることを示す。すなわち、xEy⇒xRLyをいう。 (細分の指数の方が大きいからこれがいえれ ばRLの指数有限がいえたことになる。) xEyと仮定する。Eは右不変であるから任意の z∈S*についてxzEyzとなる。 ところでLがEの同値類の和であるからxzEyzな らばxz,yzはいずれもLに属す([w]∈Lのとき) かいずれも属さない(それ以外)。 以上により、xRLy Myhill-Nerodeの定理の証明(3⇒1) M=<Q’, S, d’, q0’, F’>を次のように定める。 Q’はLのRLによる同値類集合L/RLとする。すなわち、 Q’=L/RL d’: Q’×S* → Q’は次で定義する。(定義が矛盾な いことはRLの右不変性から。) d’([x], a)=[xa] q0’=[e],F’={[x]|x∈L}とする。このとき d’([e], w)∈F’ ⇔ w∈L (確かめよ) すなわちL=L(M) Myhill-Nerodeの定理の応用: 正則でないこと L={w∈{0,1}*|wは同数の0,1からなる} [証明] zを固定したとき、wzがLに属すか否かはw中の 0,1の個数の差だけで決まる。したがってRLによ る同値類は0,1の個数の差が同じものである。 RLによる同値類集合はつぎのものからなる。 …,[1i],…,[11],[1],[e],[0],[00],[000],…,[0i],… これらは互いに異なる類であってRLの指数は有 限ではない。よってMyhill-Nerodeの定理によ りLは正則でない。 文脈自由文法 文脈自由文法(context free grammar, CFG)Gは 4つ組 < V,T,P,S>で規定されるここで、 1. Vは変数(あるいは非終端記号)の集合: 変数は記号列の集合に対応する。(後述) 2. Tは終端記号の集合 定義される言語に現れる記号の集合 3. S∈Vは開始記号 4. Pは生成規則の集合 生成規則は変数A∈Vと記号(∈V∪T)の列X1X1…Xnの組で A→X1X1…Xn のように書く。 通例文法といえば文脈自由文法を指す。 文法の例 G=<{P}, {0,1}, A, P> Aの要素は次の5つ P → e P P P P → → → → 0 1 0P0 1P1 文法が生成する言語 文法G=< V,T,P,S>において 記号列aに現れる非終端記号A(∈V)1つをある規則 A→X1X2…Xnを用いてX1X2…Xnに置き換えてbを得る操 作を導出とよびa ⇒bと書く。 aから始めて、導出を繰り返してbが得られるとき a ⇒*bと書く。(0回含む) Sから始めて導出を繰り返して得られる終端記号の列w全 体の集合を文法Gが生成する言語といい、L(G)で表す。 すなわち L(G)={w∈T*|S ⇒*w} 文脈自由文法が生成する言語は文脈自由言語とよばれる。 必ずしも終端記号だけではない記号の列aについてS⇒*a のとき、aを文形式という。 文法が生成する言語の例 前述の文法G=<{P}, {0,1}, A, P>で P⇒0P0⇒01P10⇒010P010⇒0100010 により 0100010∈L(G) L(G)は{0,1}上の回文全体 文法の略記法 規則の左辺(→記号の左側)が同じ規則が複数 ある場合、たとえば、giを記号列として A → g1 A → g2 … A → gn がある場合これらをまとめて A → g1 | g 2 | … | gn のように書く。 問 回文の文法を上の略記法で書け。 最左(右)導出 • 導出の各書き換えステップで一番左(右) の非終端記号の書き換えのみをおこなう 導出を最左(右)導出という。 • 最左導出でa1からのa2の導出ができると き a1 ⇒*lm a2 などとかく。 • S ⇒* lm aなるaを左文形式という。aは非終 端記号を含んでもよい。 最左導出の例 1桁の数 0, 1と2種類の変数x, yのみの和および 積でつくる式全体は次の文法で生成される。 E → I | E+E| E*E | (E) I→x|y|0|1 E ⇒lm E+E⇒lm E*E+E ⇒lm I*E+E ⇒lm x*E+E ⇒lm x*I+E ⇒lm x*y+E ⇒lm x*y+I ⇒lm x*y+1 構文木 • 導出を、どの非終端記号を書き換えるかの順序 を捨象して木であらわしたものを構文木という。 • 構文木の各節点は非終端記号、葉は終端記号、 根は開始記号。 • 各節点の子の並びはその節の非終端記号の書 き換えにもちいた生成規則の右辺。 構文木の例 E E E E E * I I x y I + 1 曖昧さ 2つ以上の構文木をもつ文を生成する文法は 曖昧であるという。 注 文が構文木を2つ持つことは最左(右)導 出が2つあることと同じ。 問 前述の式の文法でx*y+1の構文木をもう1 つ作れ。 応用1:括弧のバランス 開いた括弧が必ず閉じるとき、また閉じる括弧 には必ず開く括弧が対応するとき、括弧のバ ランスが取れているという。 括弧だけからなる文で括弧のバランスが取れ たものは次の文法Gbalで表される。 Gbal : B→BB | (B) | e 問い ()((())()) の導出を求めよ。 応用2:パーサー生成器 プログラム言語などの言語の構文を解析して構文木 に翻訳することを構文解析という。 構文解析器(parser)を1から作成することは労力を要 するが文法から自動的にparserを生成する技術が ある。 YACCプログラムは文法を入力としコンパイラの一部 であるparserのCコードを出力する。 YACCのように言語仕様(文法など)を入力としコンパ イラ(の一部)を得るプログラムはコンパイラ・コンパ イラと呼ばれる。 主要なプログラミング言語で使えるコンパイラ・コンパ イラが開発されている。(ml-yacc, javaccなど) YACC yaccの構文 • →のかわりに : を使う。 • 左辺は必ずまとめて右辺を | でつなぐ。 • 各変数ごとの規則は ; で区切る。 • 終端記号は ’ で囲む。 • そのほか詳細は例を参考にせよ。 yacc&lex(flex)の使い方 lex、yaccのソースを格納したファイルをそれぞれcalc.l, calc.yとする。 シェルから C:\> flex calc.l C:\> yacc calc.l C:\> cc y.tab.c –lfl 宿題 http://thales.philos.k.hosei.ac.jp/automaton/calcから上 のファイルをダウンロードして上の作業を行い、生成されたプ ログラムの動作を確かめよ。 応用3:XML/DTD XML(Extensible Markup Language)は意味 内容を記述する。 XMLの一部であるDTD(Document-Type Definition,文書型定義)は意味が了解された 語をもとに表現形式(CFL)を定義する。 DTDの形式 • DTDは次の形式である。 <!DOCTYPE DTDの名前 [ 要素の定義のリスト(並び) ]> • 要素の定義は次の形式である。 <!ELEMENT 要素の名前 (要素の記述)> • 要素の記述は要素の名前と特別の項 \#PCDATAを記号とする正則表現で和(|)、 連接(,)、および繰り返し(*,+,?)が使える。 DTDの例 <!DOCTYPE PcSpec [ <!ELEMENT PCS (PC*)> <!ELEMENT PC (MODEL,PRICE,CPU,RAM,DISK+)> <!ELEMENT MODEL (\#PCDATA)> <!ELEMENT PRICE (\#PCDATA)> <!ELEMENT CPU (MANF,MODEL,SPEED)> <!ELEMENT MANF (\#PCDATA)> <!ELEMENT SPEED (\#PCDATA)> <!ELEMENT RAM (\#PCDATA)> <!ELEMENT DISK (HARDDSK | CD | DVD)> <!ELEMENT HARDDISK ()> <!ELEMENT SIZE (\#PCDATA)> <!ELEMENT CD (SPEED)> <!ELEMENT DVD (SPEED)> ]> PcSpecに従うXML文書 <PCS> <PC> <MODEL>4560</MODEL> <PRICE>$2295</PRICE> <CPU> <MANF>Intel</MANF> <MODEL>Pentium</MODEL> <SPEED>800MHz</SPEED> </CPU> <RAM>256</RAM> <DISK><HARDDISK> <MANF>Maxtor</MANF> <MODEL>Diamond</MODEL> <SIZE>30.5Gb</SIZE> </HARDDISK></DISK> <DISK><CD> <SPEED>32x</SPEED> </CD></DISK> </PC> <PC> … </PC> </PCS> 言語と機械 言語 表現 受理機械 正則言語 正則表現 (RegExp) 有限オートマトン (FA) 文脈自由言語 (CFL) 文脈自由文法 (CFG) プッシュダウン オートマトン (PDA) プッシュダウンオートマトン プッシュダウンオートマトン(Pushdown Automaton, PDA)は次で定義される。 P=<Q,S,G,d,q0,Z0,F>: Q: 状態の集合 S: 入力記号の集合G: スタック記号の集合 d : Q×(S∪{e})×G→2Q×G* 遷移関数 (p, g)∈d(q, a, X)の意味 状態はpに遷移し、スタックの上端の記号Xをgに置 き換えてよい。g=YZならZがYの下。 q0: 開始状態∈Q Z0: 開始記号(底記号) F: 受理状態の集合⊆Q 遷移にともなうスタック操作の図 (p, YZ)∈d(q, a, X)による遷移: (q, aw, Xb) |- (p, w, YZb) … … a X q Y Z Z0 Z0 a p PDAの受理言語 P=<Q,S,G,d,q0,Z0,F> をPDAとする。 {w|∃q∈F (q0,w,Z0) |-* (q,e,a) } をPが最終状態で受理する言語と呼び、L(P)と 書く。 {w| (q0,w,Z0) |-* (q,e,e) } をPが空スタックで受理する言語と呼び、N(P)と 書く 受理言語の等価性 定理 L=L(P)ならば L=N(P1)となるPDA P1が存在する。 逆に L=N(P)ならば L=L(P2)となるPDA P2が存在する。 PDAとCFGの等価性 定理 任意のPDA P に対してL(P)=L(G)となるCFG G が存在する。 定理 任意のCFG Gに対してL(G)を受理するPDAが 存在する。 発展科目 • 計算量の理論(2年後期) – 一般の計算モデル • コンパイラ(3年前期) – 言語の字句を正則表現、構文を文法で記述 • コンパイラ演習(3年前期) – コンパイラ作成:オートマトン設計、構文解析 • プログラミング言語理論・設計(3年後期) – 論理と計算の基礎的素養をもっていることが望ま しい。
© Copyright 2024 ExpyDoc