32

私は、チョムスキーによって設定された4つのレベルの形式文法（無制限、文脈依存、文脈自由、通常）のわかりやすい（つまり、非形式的な）説明を見つけようとしています。

形式文法を勉強してからもう少し経ちましたが、今ではいろいろな定義がわかりづらいです。明確にするために、私はあなたがどこにでもある正式な定義を探していません（例えばこことここ-私は他の誰と同じようにグーグルできます）、あるいは実際にはどんな種類の正式な定義さえも探していません。代わりに、私が見つけたいと思っていたのは、完全性のために明快さを犠牲にしない、クリーンでシンプルな説明でした。

4

3 に答える 3

19

オートマトンがこれらの言語を生成したことを覚えていれば、理解が深まるかもしれません。

通常の言語は、通常のオートマトンによって生成されます。彼らは過去の有限の知識しか持っていない (彼らの計算メモリには限界がある) ため、接頭辞に依存する接尾辞を持つ言語 (回文言語) を使用するたびに、これは通常の言語では実行できません。

コンテキストフリー言語は、非決定論的プッシュダウン オートマトンによって生成されます。それらは過去の一種の知識を持っています (スタック、通常のオートマトンとは対照的に制限されていません) が、スタックは上からしか見ることができないため、過去の完全な知識はありません。

文脈依存言語は、線形結合の非決定論的チューリング マシンによって生成されます。彼らは過去を知っており、非決定論的であり、いつでも過去のすべてにアクセスできるため、さまざまなコンテキストに対処できます。

無制限の言語は、チューリング マシンによって生成されます。Church-Turing-Thesis によると、チューリング マシンは、あなたが想像できるすべてのもの (決定可能なものすべてを意味します) を計算できます。

于 2011-12-06T10:13:50.160 に答える
2

通常:これらの言語は有限オートマトンで yes/no で答えます

文脈自由:これらの言語では、入力単語が与えられたとき (ステート マシンとスタックを使用)、それが言語のメンバーである場合、常に yes/no と答えることができます。

コンテキスト依存:文法の生成が縮小しない限り ( α -> β )、yes/no で答えることができます (ステート マシンと、入力のサイズが線形であるメモリのチャンクを使用)

再帰的に列挙可能:はいと答えることができますが、いいえの場合は無限ループに入ります

完全な説明については、このビデオを参照してください。

于 2014-07-06T02:39:28.167 に答える
2

通常の言語に関しては、多くの同等の特徴があります。それらは、通常の言語を見るさまざまな方法を提供します。「平易な英語」の定義を与えることは困難であり、通常の言語の特徴を理解するのが難しい場合は、「平易な英語」の説明が役立つ可能性は低い. 定義とさまざまなクロージャー プロパティから注目すべきことの 1 つは、通常の言語が何らかの形で「有限性」の概念を具現化していることです。しかし、これも通常の言語に慣れていないと理解するのは困難です。

有限オートマトンの概念は単純できれいではないと思いますか?

多くの同等の特徴付けのいくつかに言及しましょう（少なくとも他の読者にとっては）：

于 2011-12-06T15:37:10.933 に答える