finite-automata - 与えられた文脈自由言語が規則的かどうか

Question

次のいずれかが決定可能ですか。

1. 与えられた文法は文脈自由ですか?

2. 特定の再帰言語はコンテキストフリーですか?

3. 与えられた文脈自由言語は規則的ですか?

Answer 1

与えられた文法は私たちに言語を与えることができ、言語とポンピング補題を使用して、与えられた文法が文脈自由であるかどうかを簡単に判断できます

グライバッハの定理を使うことで、文脈自由言語が正規かどうかは決定できないことを示すことができます。