CIS262languages

計算理論の紹介

Jean GallierDepartment of Computer and Information Science University of PennsylvaniaPhiladelphia,PA19104,USAe-mail:[email protected]

©c Jean Gallierお願いします、著者の許可なしに再生産しないでください

March5, 2020

4 内容

• 6.4 ポンピング補題
• 6.5状態等価性をチェックするための高速アルゴリズム
• 7文脈自由文法と言語
• 7.1文脈自由文法
• 7.2派生と文脈自由言語
• 7.3文脈自由文法の正規形
• 7.4正規言語は文脈自由である
• 7.5文脈自由文法における無用な生成
• 7.6グライバッハ正規形
• 7.6グライバッハ正規形
• 7.7最小不動点
• 7.8最小不動点としての文脈自由言語
• 7.9最小不動点とグライバッハ正規形
• 7.10木ドメインとゴーン木
• 7.11派生木
• 7.12オグデンの補題
• 7.12オグデンの補題
• 7.13プッシュダウンオートマトン
• 7.14文脈自由文法からPDAへ
• 7.15PDAから文脈自由文法へ
• 7.16チョムスキー-シュッツェンベルガーの定理
• 8lr解析法の調査
• 8.1LR(0)-特性オートマトン
• 8.2Shift/Reduceパーサー
• 8.3firstの計算
• 8.4Shift/Reduceアルゴリズムの背後にある直感
• 8.5固定小数点を計算するためのグラフ法
• 8.6Followの計算
• 8.7algorithmtraverse
• 8.7algorithmtraverse
• 8.7algorithmtraverse
• 8.7algorithmtraverse
• 8.7algorithmtraverse
• 8.8more onLR(0)-特性オートマトン
• 8.9LALR(1)-先読みセット
• 8.10コンピューティング最初、フォローなど μ-Rules
• 8.11LR(1)-Characteristic Automata

Introduction

の存在下では、計算の理論はアルゴリズムとアルゴリズムシステムに関係しています。

これらのノートの目的は、形式言語とオートマトン理論からの概念、計算可能性の理論、再帰関数理論のいくつかの基本的な概念、およびcomplexitytheoryの紹介を含む、計算理論の基本的な概念のいくつかを導入することである。 プログラムの正しさなどの他のトピックはここでは説明されません（十分な時間がありません！).

ノートは三つの部分に分かれています。 最初の部分は、正式な言語とオートマトン。 第二部では、計算、再帰関数、および不確実性のモデルを扱っています。 第三部では、計算の複雑さを扱います。

5

形式言語理論の基礎

2.1いくつかの基本的な数学表記の見直しと

N,Z,Q,R,C.

そして自然数、N={0,1,2,…}.

..,− 2 ,− 1 , 0 , 1 , 2 ,…}.

、

、

、

、

=

{

pq

|p,q≤Z,q6 = 0

}

ヌル

が存在し、R.複素数、C={a+ib|a,b≤R}。グラフ(f)={(x,f(x)}|x∈X}≤X×Y

グラフ(f)={(x,f(x)}|x∈X}≤X×Y

グラフ(f)={(x,f(x)}|x∈X}≤X×Y

グラフ(f)={(x,f(x)}|x∈X}≤X×Y

グラフ(f)={(x,f(x)}|x∈X}≤X×Y

グラフ(f)={(x,f(x)}|x∈X}≤X×Y

グラフ(f)={(x,f(x)}|x∈X}≤X×Y

ザ-グラフォフ

7

8 第2章. 形式言語理論の基礎Im(f)=f(X)={y≤Y|≤x≤X,y=f(x)}≤Y

はイメージオフです。より一般的には、ifA≤Xであれば、f(A)={y≤Y|≤x≤A,y=f(x)}≤Y

は（直接の）像です。F−1(B)={x∈X|f(X)≤B}≤X

はbの逆像（またはプルバック）である。

f−1(B)は集合であり、b6=∞であっても空である可能性がある。2つの関数f:X→Yとg:Y→Zが与えられたとき、すべてのx∈X

に対して、関数g≤f:X→Zgiven(g≤f)(x)=g(f(x))は合成オフセットとなる。

関数idX:X→Xgiven by

idX(x)=x for allx≤X

は整数関数(ofX)です。関数f:X→Yが単射であるとは、x1,x2≤X,

iff(x1)=f(x2)ならばx1=x2であることを言う。 ;

は、x16=x2の場合、f(x1)6=f(x2)と等価です。F:X→Yが単射であるとは、

r∈f=idXとなるような函数r:Y→Xが存在することをいう。

注:ris全射。函数f:X→Yが全射であるとは、函数f:x→yが全射であることをいう。

f∘s=idYとなるような函数:Y→Xが存在することをいう。

10第2章。 基礎形式言語理論

GivenR⊆X×X(関係onX),defineRnby

R0=IXRn+1=R◦Rn.

Rによって与えられる閉包+の閉包+=

⋃

1

R+はrを含む最小の推移的関係である。

Rによって与えられるリの柔軟性と推移的閉包λ∗=

⋃

n≥0

Rn=R+≤IX。

R∞は、Rを含む最小の推移的かつ反射的な関係です。

関係r≤X×Xは、反射的、対称的、推移的である場合、等価関係です。

関係r≤X×Xを含む最小の等価関係は、

（R≤R−1）.で与えられます。

すべてのx,y∈Xに対して、(x,y)≤Rand(y,x)≤Rならば、x=yである。

関係≤X×Xisantisymmetricifは、反射的、推移的、反対称的である場合には、apartial orderです。

半順序r≤X×Xは、allx,y≤X,either(x,y)≤Ror(y,x)≤Rの場合、全順序です。

2.2アルファベット、文字列、言語

言語のビューは、言語は文字列のセットです。 次に、文字列は有限ですいくつかのアルファベットからの文字のシーケンス。 これらの概念は以下のように厳密に定義されている。

定義2.1.Analphabetúはanyfinitesetです。

2.2. アルファベット、文字列、言語11

私たちはしばしばΣ={a1,…,ak}. アルファベットの”thesymbols”と呼ばれています。例:Σ={a}Σ={a,b,c}Σ={0,1}Σ={α、β、γ、δ,ǫ,λ,φ,y,ω,c,b,p,σ,η,ξ,ζ}文字列である有限のシーケンスの記号です。 技術的には、文字列を関数として定義すると便利です。 任意の整数≥1に対して、

={ 1 , 2 ,…,n},

およびforn=0,let=∞.

定義2.2. アルファベットΛが与えられたとき、長さ

u:→Λのλ（または単に文字列）を超える。

整数は文字列uの長さであり、|u|と表記されます。 N=0のとき、長さ0の特別な文字列u:→∞は空の文字列、またはnull文字列と呼ばれ、λと表されます。

長さn≥1の文字列u:→∞が与えられた場合、u(i)は文字列uのi番目の文字です。 記法のsim-plicityに対して、ofu(i)と書き、文字列u=u(1)u(2)***u(n)を

u=u1u2***un,

と表します。例えば、U(1)=a,u(2)=b,u(3)=aとなるようなΛ={a,b}andu:→Λが定義されていれば、uu=abaと書くことができる。

文字列の他の例は、

仕事、楽しみ、gabuzomeuh

長さ1の文字列はfunctionsuです：→∞単純にいくつかの要素を選ぶ（1）=aiin Π。したがって、すべてのsymbolai θを対応する長さ1の文字列で識別します。

空の文字列を含むアルファベットΣ上のすべての文字列の集合をΣと表記する。

2.2. アルファベット、文字列、言語13

ベースcasen=0のために、以来、我々は持っています

u0u=θ u=u=u θ=uu0.

帰納的ステップについては、帰納仮説=u(unu)による結合性=uun+1による定義ofun+1によって、un+1u=(unu)uがあります。

定義2.4.

uはviffの接頭辞であり、

v=uyとなるようないくつかのμが存在する。

uはviffの接尾辞であり、

v=xuとなるようなsomex∈ σ ∗があります。

uis viffの部分文字列には、

v=xuyとなるようなsomex,y∈ σ ∗があります。

例えば、gaisはgabuzoの接頭辞であり、zoisはgabuzoの接尾辞であり、buzisはgabuzoの部分文字列であると言います。集合上の半順序σは、反射性、推移性、反対称性を持つ二項関係σ S×Sであることを思い出してください。

接頭辞、接尾辞、および部分文字列の概念は、明らかな方法でΣ ∗上の二項関係を定義します。 これらの関係が部分順序であることを示すことができる。

文字列のもう一つの重要な順序付けは辞書式（または辞書）の順序付けです。

定義2.5。 与えられたアルファベットΛ={a1,…,ak}1<aのような完全な順序を仮定した2 <···< akは、任意の二つの文字列su,v∈が与えられたとき、次のように表現順序を定義する：

uv







(1) （２）ｉｆｕ＝ｘａｉｙ，ｖ＝ｘａｊｚ，ａｉ＜６ ６ １ ３＞ａｊ，ｗｉｔｈａｉ，ａｊ θ，及びｓｏｍｅｘ，ｙ，ｚ θについて。

14第2章。 形式言語理論の基礎

アイデアは、我々はm=1で始まるthemthsymboluminuto themth symbolvminvを比較し、左から右に同時にscanuandvsimultaneouslyということです。 矛盾が生じない場合、thatis、them-th symboluminuagrees with them-th symbolvminvform=1、。..,|u|,thenuis接頭辞ofvand私たちはそれを宣言します辞書式順序を先行しています。 これは、formula_6=aj(andx,y,z∈Arbitrary)であることを意味する。 これを行うには、シンボル1<aという事実を使用します2 <···< akは（完全に）順序付けられていると仮定されているので、どのofaiandajが最初に来るか、sayai<ajを見て、辞書式順序付けでu=xaiyprecedesv=xajzinと宣言します。

ケース(1)と(2)は相互に排他的であることに注意してください。 (1)の場合、uはvの接頭辞です。 (2)v6uandu6=v.

例えばabb,gallhagergallier.

辞書順序付けが実際にはapartial順序付けであることを証明するのはかなり面倒です。実際には、それは任意の二つの文字列su、v∈、eitheruv、orvuのためのことを意味し、atotal順序付けです。

stringwは帰納的に次のように定義されています。

σ r=σ,(ua)R=auR,

wherea σ Andu σ.

たとえば、reillag=gallierRです。

よsettingu=ǫin(ua)R=auR,

sinceǫR=ǫanda=ǫaのになります

aR=(ǫa)R=aǫR=aǫ=a,

namelyaR=aforル∈Σ.

|v|の帰納法によって

(uv)R=vRuRであることが示されます。

文字列の誘導を行うときに面倒な表記法を削減する便利なトリックlength n+1(n≤0)のanonempty stringw∈ σ ∗は、someu∈ σ ∗といくつかのSymbola∈ σに対して、|u|=nと書くことができます

w=uaと書くことができるという観察です。

16第2章。 形式言語理論の基礎

空集合でない場合、sincef:X→Nisは射影r:N→Xsuch thatr≤f=idXがある場合、setXis可算iff asurjectionfromNontoXがある場合。

集合Xが可算であることは、それが有限であるか、またはそれが全単射である場合（その場合は無限である）であることを示すことができる。

結果として、setQof有理数可算です。

集合は数えられない場合は数えられません。

例えば、r(実数の集合)は無計画である。同様に

(0,1) ={x≤R/0<x< 1 }

数えられないです。 しかし、（0,1）と（1）の間には全単射があります。）のすべての部分集合の集合2nは非可算である。 これはCantorの定理の特別な場合です以下で議論されています。

|Ε|=kwith Ε={a1,…,ak}. まず、長さの長さnと(kn+1−1)/(k-1)の長さの文字列が最大Λ以上であることを観察する。k=1のとき、第二の式はn+1に置き換えられるべきである。 実際、文字列は関数であるため、{1,…,n}→∞とすると、長さの文字列の数は{1,からの関数の数である。..,n}からΠへの写像であり、Π iskの固有性から、このような関数が存在する（これは帰納法onnによってすぐに示される）。 次に、長さが最大で

の文字列の数を1+k+kとする。2 +···+kn.

k=1の場合、この数はn+1であり、k≥2の場合、幾何級数の和としては(kn+1−1)/(k-1)である。

Σ6=∅の場合、σ Ontonから明示的な全単射を構築することによって示すように、σ上のすべての文字列の集合Σ ∗は無限で数えられます。

Ifk=1writea=a1であり、

{a}λ={λ,a,aa,aaa,…、アン、。..}.

私たちは全単射n7→anfromNto{a}∗を持っています。もしk≥2ならば、文字列

u=ai1***ain

は、(kn−1)/(k−1)によって変換されたbasekshiftedのintegerv(u)の表現として考えることができます。

2。2. アルファベット、文字列、言語17

σ(u)=i1kn−1+i2kn− 2 +···+in-1k+in

=

kn-1k− 1

• (i1-1)kn− 1 +···+ (in−1-1)k+in-1.

(ここで、1≤ij≤kforj=1である。..,n.

これは、v:Π→Nisが全単射であることを示すための練習として残します。 の逆関数を求めることは、驚くほど困難である。

実際、μは、|u|<|v|の場合はuprecedesv、|u|=|v|の場合は辞書式順序をuprecedesvinとするΛの列挙に対応します。 以上のことを確認するのは簡単です（uprecedesv）は総注文です。たとえば、ifk=2で、Ε={a,b}と書くと、列挙は

ε,0a,b,1,2,aa,ab,ba,bb,3,4,5,6,aaa,aab,aba,abb,baa,bab,bba,bbb7で始まります, 8 , 9 , 10 , 11 , 12 , 13 , 14

次の行を取得するには、左に連結し、左に連結します。 ウェハヴェフ(bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

それは動作します！一方、σ ∗6=∅の場合、σ ∗（すべての言語）のすべての部分集合の集合2Σ ∗は数えられません。確かに、2ontoからの射影がないことを示すことができます最初に、σ ∗から2σ ∗への射影がないことを示します。 これはカントールの定理の特別な場合である。私たちは、Σ ∗から2σ ∗への射影がなければ、2ontoからの射影もないと主張しています。

矛盾によって全射g:N→2Πが存在すると仮定する。 しかし、Σ6=∅の場合、σ ∗は無限で可算であるため、全単射v：σ ∗→Nがあります。 その場合、構成

≤||n

g||2≤

は全単射であり、全単射は全単射であり、全単射は全単射であり、全単射の合成は全単射であり、σ ∗から2σ ∗への全単射はないという仮説と矛盾する。

2.3. 言語の操作19

2.3言語の操作

より単純なものからより複雑な言語を構築する方法は、さまざまな操作を使用してそれらを結合することです。 まず，和集合，交叉，および完備化の集合論的演算をレビューした。

たらされた文字Σ、二languagesL1L2Σ,theunionL1∪L2ofL1andL2つの言語

L1∪L2={w∈Σ∗|w∈L1またはw∈L2}.

インターセクションL1≤L2ofL1andL2は、言語

L1≤L2={w≤|w≤l1And w≤l2}です。

ThedifferenceL1−L2ofL1andL2は、言語

L1−L2={w≤|w≤l1And w/≤l2}です。

この差を補数補数ともいう。

差分の特殊なケースは、l1=∞のときに得られ、その場合、languagelas

l={w≤|W|≤l}を定義します。

上記の操作は文字列の構造を使用しません。 以下の操作は、concatenationを使用します。

定義2.8。たアルファベットΣ、二languagesL1L2Σ,theconcatenationL1L2ofL1andL2つの言語

L1L2={w∈Σ∗|∃u∈L1,∃v∈L2,w=uv}.

任意のlanguageLに対して、

L0={λ},Ln+1=LnL(n≤0)と定義する。

n=0inLn+1=LnL,sinceL0={π}と設定すると、

L1=L0+1=L0L={π}L=L,

soL1=Lが得られます。

20第2章。 基礎形式言語理論

以下のプロパティを簡単に検証す:

L∅=∅,∅L=∅、L{ǫ}=L,{ǫ}L=L L1∪{ǫ})L2=L1L2∪L2L1L2∪{ǫ})=L1L2∪L1,LnL=LLn.

一般に、L1L26=L2L1.So これまでに導入した演算は、補完（sinceL=Μ−Lis無限ifLis有限でμが空でない場合）を除いて、言語の有限性を保持します。 これはそうではありません次の2つの操作の場合。

定義2.9。アルファベットΛが与えられたとき、任意の言語オーバー Λに対して、kleene λ-closureL λは言語

L λ=

である。