問題と解法

• Σ = {1, +, -}
• E→ 1 | EE+ | E-

Eを式（その定義は上の文法）として、

• S→ E
• S→ SE
• P→ S | SEE+

SはEのシーケンスで、Pはプレフィックスから。Eの言語をL, Pの言語をL'として、ターゲット命題は

• L' = Prefix(L)

M = Prefix(L) とすれば、

1. L'⊆M
2. M⊆L'

2番目の証明のために

• w∈M ⇒ w∈L'
• w∈W ⇔ ∃v.(wv∈L)

w∈W を次のような命題に分ける。

1. P(w, 0) ≡ ∃v.(|v| = 0 ∧ wv∈L)
2. P(w, 1) ≡ ∃v.(|v| = 1 ∧ wv∈L)
3. P(w, 2) ≡ ∃v.(|v| = 2 ∧ wv∈L)
4. ...

すると、

• P(w, n) ⇒ w∈L'

が示すべき命題になる。数学的帰納法を使って、

• Basis: P(w, 0) ⇒ w∈L'
• Step: (P(w, n) ⇒ w∈L') ⇒ ( ( P(w, n + 1) ⇒ w∈L' )

ステップの後件をちゃんと書くと：

• ∃v.(|v| = n + 1 ∧ wv∈L) ⇒ w∈L'

後件の前件から、v = v'+, v = v'- （v'∈L'）に場合分けできて、

• ∃v'∈L'.(|v'| = n ∧ wv'+∈L) ⇒ w∈L'
• ∃v'∈L'.(|v'| = n ∧ wv'-∈L) ⇒ w∈L'

となり、さらに場合分けして、

• ∃v'∈L'.(|v'| = n ∧ wv'+∈L) ⇒ w∈L ∨ w∈L⁺ ∨ w∈L⁺LL{+}