对于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不能跨越三个地区中，只有最多两个（足够大的字符串）。第二条和第三条规则现在意味着您可以进行泵送，使得未跨越区域比其他区域中的至少一个小。