文脈自由文法とか文脈依存文法で小泉構文ってどうやって作れば良い？

[0001 以下、5ちゃんねるからVIPがお送りします 2023/04/03(月) 01:43:32.808 ID:qgwQU3Q3r]

例えば文字の集合{a,b,は}が与えられてる場合
aはa,abはab,abbはabb,baはba…
みたいなのが小泉構文とするとして
任意の小泉構文のみを含む言語を生成するにはどういう形式文法にすればいい？

[0002 以下、5ちゃんねるからVIPがお送りします 2023/04/03(月) 01:49:40.940 ID:qgwQU3Q3r]

小泉構文の反転バージョンなら
S→X
X→aXa|bXb|は
でいいよね
例えば
aabはbaa
だと
S→aXa→aaXaa→aabXbaa→aabはbaa
で作れるし