Chomsky Normal Formで文脈自由文法を構築する

Question

Chomsky Normal Formで、唯一の文字列a^21を含む言語を受け付ける可能な限り少数のプロダクションでCFGを構築しようとしています。

は、私はちょうど

Sを変換することができることを理解する - > AAAAAAAAAAAAAAAAAAAAA A - >

が、その後、その言語を短縮チョムスキー標準形に変換する他の方法がありますか？

Answer 1

生成された文字列の長さを各プロダクションで最大2倍にすることができることを認識し、この言語のCNFでCFGを生成するために少なくとも6つのシンボルが必要であることをかなり簡単に示すことができます。

CNFには、ターゲット言語を生成する6つのプロダクションを持つ文法がないことが示されています。文法を上から構築することで議論を始める。

1. 文字列を取得するには、A_1 := aが必要です。
2. 私たちは、私たちが今A_3またはそれをスキップしてA_4を生成する、あるいはその両方を生成することができます。1.
3. よりも大きい長さの任意の文字列を取得するA_2 := A_1 A_1を持っている必要があります。これらのケースはそれぞれ次のように考えられます。

ケース1：A_3

1. 我々はA_3 := A_2 A_1を追加します。
2. すでに3つのプロダクションがあり、A_21 := X Yのいずれかのフォームが必要です。だから我々は最大2つを追加することができます。現在可能な最大の作品 - A_6とA_12を追加したとしても、必要に応じてA_21を生成することはできません（最大でA_18 := A_6 A_12を生成することができます）.を追加すると、6つのプロダクションで私たちの言語を生成する文法を得ることができません。

ケース2：。。。A_4

1. 我々はA_4 := A_2 A_2を追加
2. 我々はすでに3つの作品を持っている、と我々は、フォームA_21 := X Yのいずれかが必要です知っているので、我々はさらに2つまで追加することができます私たちのOPTIO現在、A_5、A_6およびA_8です。 A_5とA_6は、上記のケース1と同じ理由で失敗します。しかし、A_8は、その推論によって失敗しないので、A_8 := A_4 A_4を追加します。
3. 生産が1つしかなく、A_20, A_19, A_17またはA_13のいずれかになる必要があります。既存の制作物を使用してこれらを生成することはできません。

したがって、6つのプロダクションで文法を除外しました。上記の推論を使って7つのプロダクションで文法を見つけようとすると、いくつかのプロダクトが見つかります。 7つのプロダクションでCNFに文法があり、6つでは文法がないことを知っているので、あなたは完了です。ここには7つの生産文法のいくつかがあります：

S := A_18 A_3 
A_18 := A_9 A_9 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_17 A_4 
A_17 := A_9 A_8 
A_9 := A_8 A_1 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

S := A_16 A_5 
A_16 := A_8 A_8 
A_8 := A_4 A_4 
A_5 := A_4 A_1 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

S := A_15 A_6 
A_15 := A_9 A_6 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_14 A_7 
A_14 := A_7 A_7 
A_7 := A_4 A_3 
A_4 := A_3 A_1 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_13 A_8 
A_13 := A_8 A_5 
A_8 := A_5 A_3 
A_5 := A_3 A_2 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_12 A_9 
A_12 := A_9 A_3 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_11 A_10 
A_11 := A_10 A_1 
A_10 := A_8 A_2 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

さらにたくさんあります。難しい部分は、6つのプロダクションがないことを示していました。