通常の言語の定義

Question

私は試してみましたが、脳を燃やして通常の言語の定義を理解しました 離散数学とそのアプリケーション（ローゼン） この本の定義がそのようなものである理由を理解するという目標に到達することなく。ページ（789）、私はです rephrasing 定義：

タイプ3の文法は、次のように定義されています。

w1 --> w2

ここで、W1は非末端で、W2は次の形式です。

w2 = aB
w2 = a

ここで、Bは非末端で、Aは端子です。特別なケースは、W1が開始記号であり、W2がラムダ（空の文字列）である場合です。

w1 = S
S --> lambda

私が答えを見つけることができなかった2つの質問。まず、なぜできないのか W2 フォームになります ba. 。第二に、なぜ ラムダ 開始記号のみが許可されます それだけ. 。この本は、通常の言語は有限の状態オートマトンと同等であり、両方のケースでFSAを構築できることを簡単に確認できると述べています。私は他のリソースを見てみましたが、これらの制限はこれらのリソースには存在しません。

Answer 1

まず、なぜW2がbaの形にならないのか。

Wで次の文法を開始記号として取得します。

W -> lambda
W -> aX
X -> Wb

{aⁿ bⁿ ：n自然}は正規言語ではありません。したがって、通常の言語のみを生成したい場合、この制限は不可欠です。または、W2 = BAを許可することもできますが、 禁止 種類のW2 = ABのルール - これは通常の言語も提供します。その文法は「後方」という言葉を構築します。

両方のタイプのルールを許可する場合、あなたは次のように知られるクラスを取得します 線形言語.

第二に、なぜラムダは開始記号のみに許可されるのか。

これは壊死の制限ではありません。

非末端記号のラムダのすべての使用を排除できます。ルールw-> lambdaを取り、それを削除し、すべてのルールu-> awをu-> awおよびu-> aに置き換えます。明らかに、端末記号でのラムダの使用を排除することはできません（言語は空の単語を生成しなくなります）。

したがって、多くの場所でラムダを使用するすべてのタイプ3の文法は、スタート記号にのみラムダを使用する文法に「正規化」することができます。