regex - この文脈自由文法は正規表現ですか?

Question

次のように定義された文法があります。

A -> aA*b | empty_string

A正規表現ですか？BNF 文法の解釈方法について混乱しています。

Answer 1

いいえ、この質問は実際には正規表現とは関係ありません。文脈自由文法は、正規表現では記述できない言語を指定します。

ここで、Aは非終端記号です。つまり、プロダクション ルールによって展開する必要があるシンボルです。ルールが 1 つしかない場合、それは開始記号でもあります。この文法のすべての生成は . で開始する必要がありAます。

制作ルールは

(1)    A -> aA*b | 
(2)         empty_string

aとbは終端記号です。これらは言語のアルファベットであり、展開できません。左側に非終端記号がなくなったら、完了です。

aしたがって、この言語では、 andbの代わりに(andを使用することを除いて、バランスの取れた括弧のような単語を指定します)。

たとえば、ab次のように作成できます。

A -> aA*b (using 1)
aAb -> ab (using 2)

同様に、以下を生成できますaabb。

A -> aA*b (1)
aAb -> aaA*bb (1)
aaAbb -> aabb (2)

またはさらにaababb：

A -> aA*b
aA*b -> aabA*b:
aaba*b -> aababA*b:
aababA*b: -> aababb

それを得る？星印は正規表現で見たことがあるので少し混乱するかもしれませんが、実際にはここでも同じことを行います。これは Kleene クロージャと呼ばれ、0 個以上Aの s で作成できるすべての単語を表します。

Answer 2

正規表現は正規言語を生成し、ステートマシンで解析できます。

BNF文法は、文脈自由言語を生成する文脈自由文法であり、プッシュダウンオートマタ（スタックマシン）で解析できます。

文脈自由文法は、正規文法ができることすべてを行うことができます。

Answer 3

A は BNF 文法規則のようです。これを正規表現と混同している理由がよくわかりません。* が入っているので混乱していませんか？* が付いているものはすべて正規表現ではありません。