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

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

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

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

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