4月23日帰納的表現と形式言語

4月23日帰納的表現と形式言語
先週の小テストの解答例
~ ∀xP( x) = ∃x ~ P ( x)
「すべてのxがP ( x)となるわけではない」と
「P ( x)にならないxが存在する」は等しい
¬∃xP( x) = ∀x¬P( x)
「P ( x)であるxが存在しない」と
「任意のxに対してP( x)ではない」は等しい
先週の小テストの解答例
∀x( P( x) ∧ Q( y )) = ∀xP( x) ∧ Q( y )
「任意のxに対してP( x)かつQ( y )」と
「任意のxに対してP( x)でかつQ( y )」は等しい
∀x( P( x) ∨ Q( y )) = ∀xP( x) ∨ Q( y )
「任意のxに対してP( x)またはQ( y )」と
「任意のxに対してP( x)，またはQ( y )」は等しい
先週の小テストの解答例
∃x( P( x) ∧ Q( y )) = ∃xP( x) ∧ Q( y )
「P( x)かつQ( y )となるxが存在する」と
「P( x)となるxが存在しかつQ( y )」は等しい
∃x( P( x) ∨ Q( y )) = ∃xP( x) ∨ Q( y )
「P( x)またはQ( y )となるxが存在する」と
「P( x)となるxが存在するか，またはQ( y )」は等しい
先週の小テストの解答例
∀x( P ( x) ∧ R ( x)) = ∀xP( x) ∧ ∀xR( x)
「任意のxに対してP( x)かつR( x)」と
「任意のxに対してP( x)でかつ任意のxに対してR( x)」は等しい
∃x( P( x) ∨ R( x)) = ∃xP( x) ∨ ∃xR( x)
「P( x)またはR( x)となるxが存在する」と
「P( x)となるxが存在するか，またはR( x)となるxが存在する」は等しい
数学的帰納法
形式言語と帰納的表現
形式言語
言語の演算

言語の和
言語の積
言語の閉包
数式の記法

前置記法（ポーランド記法）

Lisp
中置記法

*xy
(car ‘(A B C))
x*y
後置記法(逆ポーランド記法）

xy*
Hewlett-Packardの電卓
括弧を書かなくても良い．
頭の中で計算する順序に近い
小テスト１

中置記法 ( - y+z)*w/2 を逆ポーランド記
法（後置記法）に変換してください．
中置記法 ( - y+z*w)/2 を逆ポーランド記
法（後置記法）に変換してください．
ただし – は単項のマイナスとする
BNF記法

BNF記法で用いられる記号（メタ記号）
<○○>
○○という概念を表す．
::=
左の記号が右辺で定義される，
is defined as
|
もう一つの定義，「または」
BNF記法の例

<英数字>::=<英字>|<数字>

英数字とは英字または数字のことである．
<英字>::=a|b|....|y|z

英字とはa,b,....,y,zのどれかである
例題2.66

非負の整数を表す10進記法の数値のみからな
る言語をBNF記法で定義せよ
解
<数値>::=0|<正整数>
<正整数>::=<非零数字><数字繰返し>
<非零数字>::=1|2|3|4|5|6|7|8|9
<数字繰返し>::=ε|<数字><数字繰返し>
<数字>::=0|<非零数字>
例題2.68

和＋と積×からなる中置記法の数式をBNF記法
で定義せよ．変数はすべてxとし，括弧(,)を用い
る．定数は用いない．
解
<数式>::=x|<数式>+<数式>
|<数式>×<数式>|(<数式>)
構文図式表現とBNF表現
書き換え
分岐
a
連鎖
α
繰返し
b
c
B
B
B
オプション
<A>::=α
α
α
y
β
z
<A>::=a|b|c....|y|z
γ
<A>::=α<B>βγ
<A>::=<B>{<B>}
<A>::={<B>}
<A>::=[α]
小テスト２

例題2.73 つぎのBNF記法による言語の表現を，
拡張BNF記法を用いてあらわせるならば，その
表現に変換せよ．また，これらの言語をできるだ
け簡単な構文図式で表せ．
<A>::= a|ab|abb|ba
<A>::= a|a<A>
<A>::= ε|a|b<A>
<A>::= a<A>|ba
<A>::= ε|a<A>a|b<A>b

Download Report