theory - 就職の面接のための文脈自由文法の曖昧さを説明する

Question

私は就職の面接で、彼らが私にこう質問しました。

以下の2つはあいまいですか？そうである場合は、文字列を指定します。そうでない場合は、そうでない理由を証明してください。

解決できなかったので、答えと今後の理由を知りたいです。

質問1

S-->XaaaX
X-->aX | bX | e(epsilon)

質問2

S-->aaS | aaaS | a

繰り返しますが、これはハードウェアではありません。

ありがとうございました。説明が役立ちます。

Answer 1

文法からのいくつかの生成物に複数の可能な派生がある場合 (およびその場合にのみ)、文法はあいまいであることを思い出してください。

問題 1 では、記号 S は XaaaX に展開され、記号 X を展開するための利用可能な代替手段には、aX とイプシロン (ε) が含まれます。通常、記号イプシロンは空の文字列を表します。aX で X をイプシロンとして展開すると、a が生成されます。したがって、aaaa を取得するには少なくとも 2 つの方法があります。リチャード・マッケンナ、見つけるのは君に任せるよ。

問題 2 では、記号 S は aaS、aaaS、または a に展開されます。aaaaaa を取得するには、少なくとも 2 つの方法があります。繰り返しますが、派生物を見つけるのはあなたに任せます。

必要に応じて、このページに派生物を書き込むことができます。