context-free-grammar - の CFG を構築する

Question

L1 = {a^ib^j | i,j>=0 }

私の試み：

S = SA|e

A = aAB|e

B = bB|e

答えを確認する方法がありません。これは正しいですか?

Answer 1

L1 = {a ^ ib ^j|を定義します i、j>=0}。つまり、これは、0個以上のaで始まり、0個以上のbで終わるすべての文字列の言語です。これは正規言語です。その正規表現はa*b*です。正規文法（文脈自由文法でもあります）は次のとおりです。

S := lambda | aS | bT
T := lambda | bT

もう1つの文脈自由文法は次のとおりです。

S := lambda | aS | Sb

私が何かを逃していて、あなたの言語が私が読んでいるものより複雑であるならば、すみません。そのように定義されたL1が私が説明した言語と異なると信じる理由がある場合は、説明してください。