對於L = {a ^（n）b ^（n）c ^（n）| n> = 1}的PushDown自動機（PDA）

Question

我正在試圖構建非上下文的下推自動機的愚人差事自由語言L = {a ^（n）b ^（n）c ^（n）| n> = 1}並考慮兩種方法。

第一種方法： -

我認爲，每一個「A」的字符串我會推3「」進棧和字符串中的每一個「B」，我會彈出2 'a'現在對於字符串中的每個'c'，我仍然會在堆棧中有'a'。

問題與第一種方法： -產生的語言成爲這樣的L = {A ^（P）b ^（M）C ^（n）的| P> = 1和無法確定如何m和n可以定義}

第二種方法： -

我們知道，L = {A ^（n）的b ^（ m）c ^（m）d ^（n）| n> = 0}是一種上下文無關語言，L = {wxw | w∈（a，b）*}也是上下文無關的語言。所以，我認爲L = {a ^（n）b ^（m）b ^（m）c ^（n）| N> = 1且m =地板（第（n + 1）/ 2）}

問題的第二種方法： -不知道，如果我們可以計算出地板（N + 1/2）在PDA不會干擾堆棧的元素。

請幫助確定如何在第一種方法中定義m和n，以及如何在PDA中找到floor（（n + 1）/ 2）。

如果需要，JFLAP文件可用於兩者。

Answer 1

正如Ami Tavory所指出的，這種語言沒有PDA，因爲這種語言沒有上下文。如果您使用隊列而不是堆棧，使用兩個堆棧或使用圖靈機（所有等價物），則很容易識別此語言。

排隊機：

1. 排隊a S作爲你只要看到a S，直到你看到一個b。
2. 出列a S和排隊b S作爲你只要看到b S，直到你看到一個c
3. 出列b S作爲你只要看到c秒。
4. 如果結束此過程而沒有附加輸入和空隊列，請接受。

雙堆棧PDA：

1. 使用第一棧推a確保a^n b^n當你看到一個a啪a當你看到一個b;
2. 使用第二個堆棧確保b^n c^n按b當您看到b並彈出b當您看到c;
3. 如果在此過程結束時兩個堆棧均爲空，則接受。

圖靈機：

1. 通過用A代替每個a和擦除確保a^n ... c^n一個匹配c;
2. 通過擦除匹配對A和b來確保A^n b^n;
3. 如果在此過程結束時您接受A而不再有b，即磁帶已被完全清除。

Answer 2

你還沒有設法構造這種語言的下推自動機的原因之一，是因爲沒有。 Bar Hillel pumping lemma顯示了這一點。

爲了概括證明，假設可以完成。然後，對於一些p，每串大於p可以劃分爲uvwxy，S.T.，

• | VWX | < p

• | vx | > 1個

• ^UVÑ WX ^Ñý也由自動機接受，對於任何Ñ。

的第一條規則意味着VWX不能跨越三個地區中，只有最多兩個（足夠大的字符串）。第二條和第三條規則現在意味着您可以進行泵送，使得未跨越區域比其他區域中的至少一個小。