下面的語言環境是免費的語法嗎？

Question

對於n> = 0，給定的語法（a^na^na^n）上下文是否自由？我嘗試使用抽象引理，結果是，不，它不是上下文無關的。

Answer 1

對於工作的抽象要點，你需要證明你可以找到一個單詞並「抽空」，以打破PL的規則。

在這種情況下，您有a^n a^n a^n，並且希望將這些單詞拆分爲單詞uv^kw，以便它仍然處於指定的語法中。

在這種情況下，它不會工作！

要看到這一點，我們必須考慮幾種情況：

1）u是至少1（爲v不能是由PL的定義是空的），使得V和W的一個的

休息

2）U具有lenght a^n，v至少有一個^ n的長度，w爲a^n

3）長度...

想象一下，你有長度爲k的模板，並把它在a^na^n的每個可以想象的位置下一個n次方像這樣：

如果只添加1 n，則最終的字不會成爲在了a^n a^n a^n，因此PL失敗。語言a^n a^n a^n等於a^n b^n c^n這是失敗的PL的標準示例。

旁註：如果PL不失敗，你不能斷定語法是上下文無關的。 PL僅適用於一個方向。