這是語法{a^2n b^n | n> = 0}上下文是否空閒？

Question

這個語法環境是否免費？

{a^2n b^n | n >= 0} 

Answer 1

你問的對象不是語法，而是語言：一組字符串。一組字符串可以用上下文無關的語法來描述，這是因爲存在一些語法，其規則完全生成該組字符串。

在這種情況下，您所設定的擴張看起來是這樣的：

{ "", "aab", "aaaabb", "aaaaaabbb", ... } 

這是一套由偶數a -s的所有字符串，其次是一半的b -s。

這組可通過以下規則重複產生：

1. 空字符串是在該組。
2. 如果字符串s在集合中，那麼字符串"aa" + s + "b"在集合中。

也就是說，是從一個集合中的任何字符串，就可以形成一個新的字符串，這也是一組，只需添加在左邊的兩個a -s和右側的b。與空字符串在集合中的基本情況規則一起，這些規則描述了整個集合。

而且這些規則等同，並且可以在，上下文無關文法的形式寫出：

s -> "" 
    -> "aa" s "b" 

語法是上下文無關，因爲它僅具有形式的規則「一 - >符號...「：左側只有一個非終端符號。所以世代都不依賴於上下文：一個符號被採用，並根據一些可用的規則單獨替換。