オートマトン、文脈自由文法の問題

オートマトン、文脈自由文法に関する問題です。
画像の生成規則P1で表される言語は、曖昧さを含む（a + a * aなど）
それを曖昧さを含まない生成規則P2を定義したい。
そのとき、空欄に当てはまる式を記せ。
という問題があった時、どのように解けばよいですか。
答えだけでなく、どうやってそのようにしたのか記していただけると幸いです

No.2 回答者： stomachman 回答日時： 2023/07/13 11:44

{S→a, S→S+a, S→S*a}

という有限状態機械で足りるんだから、これだけでは「変な問題」。
　だけど、ま、この次に「普通の式」のparsingをやることを意識しているんだろう。ならばカッコを扱わないとなー。（そして、カッコを扱うためには文脈自由文法でなくちゃならん、ということになる。）
　で、そういうことなら、普通の式」の用語で言えば、Yはfactor(因子)、Xはfactorsを"*"でドンドンつないだterm(項)、Sはtermsを"+"でドンドンつないだexpression(式)、ということ。あとはできるでしょう。

No.1 回答者： Tacosan 回答日時： 2023/07/13 00:41

まず一般論でいうと, 「どうしようもなく曖昧」なことはある. ただし, そのようなものでは「曖昧さを除け」という問題は出せない.

「どうして曖昧なのか」がわかれば「曖昧でない文法」を作ることができる, というパターンもよくある.