如何判斷一種語言是否是一見鍾情的？

Question

我的教授期望我們能夠快速判斷一個給定的語言是否是規則的，上下文無關的，但不是常規的，或者沒有上下文無關的（換句話說，沒有繪製PDA，編寫上下文無關文法，並使用抽象引理用於上下文無關的語言）。

我知道提示，可以幫助我們快速判斷常規語言一見鍾情，但不知道語言是否無上下文。

謝謝。

Answer 1

當然，沒有普遍的答案。但是有一些CF可以或不可以做的以不同變體顯示的一般模式。事情CF可以做（和REG沒有）：同時

• 數在兩個地方就像一個^ NB^N，
• 也多次就像在一個^ NB^NA^MB^M
• 或嵌套例如，在「具有相等數量的a和b的單詞」中計算一個字母相對於另一個字母的數量或者「具有比a多5個a的詞」

個

典型事物CF不能做：同時

• 數在三個地方就像一個^ NB^NC^N
• 計數同時兩次都像處在^ NB ^馬^ NB的地方有兩個交叉對^ m
• 像ww
• 兩個有序的副本比較三個字母的數字，如「在a，b和c數目相等的單詞」中。

考慮到這些模式，您應該能夠確定大多數常見示例語言的上下文無關性。