私は離散数学における正規言語の定義とその応用 (Rosen)を理解しようとしましたが、この本の定義がそのようなものである理由を理解するという目標に到達することはできませんでした。ページ（789）で、定義を言い換えています：
タイプ 3 文法は次のように定義されます。
w1 --> w2
w1 は非終端記号で、w2 は次の形式です。
w2 = aB
w2 = a
ここで、B は非終端記号で、a は終端記号です。特殊なケースは、w1 が開始記号で、w2 がラムダ (空の文字列) の場合です。
w1 = S
S --> lambda
答えが見つからなかった2つの質問。まず、 w2をBaの形式にできないのはなぜですか。第二に、ラムダが開始シンボルのみに許可される理由. この本には、通常の言語は有限状態オートマトンと同等であり、両方のケースで FSA を構築できることが簡単にわかると述べられています。他のリソースを調べましたが、これらのリソースにはこれらの制限はありません。
まず、w2 を Ba の形にできないのはなぜですか。
W を開始記号とする次の文法を取ります。
W -> lambda
W -> aX
X -> Wb
通常の言語ではない{a n b n : n natural } を生成します。したがって、通常の言語のみを生成する場合は、この制限が不可欠です。あるいは、w2 = Ba を許可し、w2 = aB の種類のルールを禁止することもできます。これにより、通常の言語も得られます。その文法は「後方」という単語を構築します。
両方のタイプのルールを許可すると、線形言語として知られるクラスが得られます。
第二に、ラムダが開始シンボルのみに許可される理由。
これは必須の制限ではありません。
非終端記号に対するラムダの使用をすべて削除することができます。いくつかのルール W -> ラムダを取り、それを削除して、すべてのルール U -> aW を U -> aW および U -> a に置き換えます。明らかに、終端記号にラムダの使用を排除することはできません (言語は空の単語を生成しなくなります)。
したがって、多くの場所でラムダを使用するすべてのタイプ 3 文法は、開始記号のみにラムダを使用する文法に「正規化」できます。