Semantics with Applications

Slides:



Advertisements
Similar presentations
Probabilistic Method 7.7
Advertisements

プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
アルゴリズムイントロダクション第2章 主にソートに関して
4章 制御の流れ-3.
情報理論2 注意!! 11月26日(火)は休講 (小林が学会出張のため) 湘南工科大学情報工学科 准教授 小林 学 湘南工科大学
「Postの対応問題」 の決定不能性の証明
ソフトウェア基礎科学 授業資料: 論理関係(logical relations)のお話
    有限幾何学        第8回.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
Natural Semantics 実行過程の、最初と最後の状態(state)の関係を考える。
線形代数学 4.行列式 吉村 裕一.
データ構造と アルゴリズム 知能情報学部 新田直也.
情報理論2 第6回 小林 学 湘南工科大学 2011年11月15日 〒 神奈川県藤沢市辻堂西海岸1-1-25
Probabilistic Method 6-3,4
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
本時のねらい 「円周角と中心角の意味を理解し、二つの角の関係について、操作・実験を通して予測したことを確認し、定理としてまとめる。」
計算量理論輪講 岩間研究室 照山順一.
第2章 「有限オートマトン」.
繰り返し計算 while文, for文.
岩村雅一 知能情報工学演習I 第11回(後半第5回) 岩村雅一
3. 可制御性・可観測性.
プログラミング言語論プログラミング言語論 プログラムの意味論 水野嘉明
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
正則言語 2011/6/27.
形式言語の理論 5. 文脈依存言語.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
地域情報学演習 VBAプログラミング 第3回 2017年10月24日
電磁気学C Electromagnetics C 5/28講義分 電磁波の反射と透過 山田 博仁.
7.4 Two General Settings D3 杉原堅也.
Structured programming
岩村雅一 知能情報工学演習I 第10回(後半第4回) 岩村雅一
逐次プログラムの正当性(2) 帰納的アサーション法(フロイド法)
古代の難問と曲線 (3時間目) 筑波大学大学院 教育研究科 1年                 石井寿一.
依存型で型付けされた 副作用のある関数のための 型保存コンパイラ
25. Randomized Algorithms
Structural operational semantics
Additive Combinatrics 7
A Dynamic Edit Distance Table
プログラミング言語論 第四回 理工学部 情報システム工学科 新田直也.
書き換え型プログラムの生成・検証 研究課題:適切な実行戦略を効率よく探索する、 より自動化された手続きの実現 書き換え型プログラム
岩村雅一 知能情報工学演習I 第11回(後半第5回) 岩村雅一
プログラムの基本構造と 構造化チャート(PAD)
A path to combinatorics 第3章後半(Ex3.8-最後)
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
コンパイラ 2011年10月20日
14. The Basic Method M1 太田圭亮 14.3 Spaces of polynomials
融合原理 (resolution) 人工知能 論理と推論(2) 論理的帰結 節形式 融合原理 知識を組み合わせて知識を生み出す
中3数 三平方の定理の計算 三平方の定理の逆 中学校 3年数学 三平方の定理 授業第2時に実施する。
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
補講:アルゴリズムと漸近的評価.
計算の理論 I 反復補題 月曜3校時 大月 美佳 平成15年7月14日 佐賀大学知能情報システム学科.
C#プログラミング実習 第2回.
vc-1. Visual Studio C++ の基本操作 (Visual Studio C++ の実用知識を学ぶシリーズ)
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
情報処理Ⅱ 2006年11月24日(金).
4.プッシュダウンオートマトンと 文脈自由文法の等価性
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
Chapter5 Systems of Distinct Representatives
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
プログラミング基礎演習 第4回.
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
岩村雅一 知能情報工学演習I 第10回(後半第4回) 岩村雅一
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
線形符号(10章).
PADのテンプレート 処理、連接 x0 ← x x ← x0+ u(x0) err ← |x - x0| 判断(選択) x2 ← x3
数理論理学 最終回 茨城大学工学部情報工学科 佐々木 稔.
分岐(If-Else, Else if, Switch) ループ(While, For, Do-while)
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

Semantics with Applications (2章3節)

2.3 等価の結果 While言語の意味論2つ (自然意味論と構造的操作的意味論) が等価であることを証明する

定理 2.26 Whileの全ての命令文で である。 この結果は2つの性質を表している ・もしある状態からのSの実行がどちらかの意 味論で終了するなら、それはもう一方でも終 了し、結果の状態は等しくなる 味論でループするなら、それはもう一方でも ループする。

ならば (定理2.26を証明するための補助定理) 補助定理2.27 Whileの全ての命令文Sと状態sとs’で  構造的操作的意味論でも同じ状態で終了するだろう。 ならば 次ページから証明→

補題2.27の証明 *証明:証明は<S, s>→S’のための導出木の形における帰納法 (つまり[ass(ns)],[skip(ns)],….のこと)によって始める

補題2.27の証明 (1/3)

補題2.27の証明 (2/3)

補題2.27の証明 (3/3)

ならば (つまり補助定理2.27の逆) (定理2.26を証明するための補助定理2) 補助定理2.28 Whileの全ての命令文Sと状態sとs’,自然数kで   もしsからのSの実行が構造的操作的意味論で終了するなら、自然意味論でも同じ状態で終了するだろう。 ならば (つまり補助定理2.27の逆) 次ページから証明→

補題2.28の証明 (1/3)

補題2.28の証明 (2/3)

補題2.28の証明 (3/3)

定理2.26の証明: 任意の命令文Sと状態sで、補助定理2.27と2.28より  が導かれる。  よって  が言える。

演習2.29   Whileの言語を命令文 repeat S until b で拡張しなさい。   その構造の自然意味論は演習2.7で、構造的操作的意味論は演習2.17で考えた。拡張された言語にも定理2.26が成り立つように証明を修正しなさい。

演習2.30   Whileの言語を命令文 for x := a1 to a2 do S で拡張しなさい。   その構造の自然意味論は演習2.8で、構造的操作的意味論は演習2.18で考えた。拡張された言語にも定理2.26が成り立つように証明を修正しなさい。

定理2.26を証明するのに使った証明のtechnique 1.導出木の形の帰納法による証明により、自然意味論のそれぞれの導出木に一致する操作的意味論の有限の導出列があることを示した 2.導出列の長さの帰納法により証明し、構造的操作的意味論の有限な導出列それをれに対して、一致する自然意味論の導出木があることを示した