L={a^(n)b^(n)c^(n)|n>=1} 的下推自动机（PDA）
PushDown Automaton (PDA) for L={a^(n)b^(n)c^(n)|n>=1}
我正在尝试为非上下文无关语言构造下推自动机 L={a^(n)b^(n)c^(n)|n>=1} 并且想到了两种方法。
First approach:-
I thought that for every 'a' in string I will push 3 'a' into the stack and for every 'b' in the string, I will pop 2 'a' from the stack now for every 'c' in the string I will still have 1 'a' in the stack.
第一种方法的问题：-生成的语言变成这样 L={a^(p)b^(m)c^(n)| p>=1 and 无法确定如何定义 m 和 n}
Second approach:-
We know that L={ a^(n)b^(m)c^(m)d^(n) | n>=0 } is a context-free language and L={ wxw | w∈(a,b)* } is also context-free language.
So, I thought L={ a^(n)b^(m)b^(m)c^(n) | n>=1 and m=floor((n+1)/2) }
第二种方法的问题：-不知道我们是否可以在不干扰堆栈元素的情况下在 PDA 中计算 floor(n+1/2)。
请帮助确定如何在第一种方法中定义 m 和 n，以及如何在 PDA 中找到 floor((n+1)/2)。
如果需要，JFLAP 文件可用于两者。
您未能为该语言构建下推自动机的一个原因是没有。 Bar Hillel pumping lemma 显示了这一点。
概括证明，假设可以做到。然后，对于一些p，每个大于p的字符串可以划分为uvwxy，s.t.,
|vwx| < p
|vx| > 1
uvnwxny 也被接受自动机，对于任何 n.
第一条规则意味着 vwx 不能跨越三个区域，最多只能跨越两个（对于足够大的字符串）。第二条和第三条规则现在意味着您可以泵送，以便未跨越的区域小于其他区域中的至少一个区域。
正如 Ami Tavory 所指出的，这种语言没有 PDA，因为这种语言不是上下文无关的。如果您使用队列而不是堆栈、使用两个堆栈或使用图灵机（都是等效的），则很容易识别这种语言。
排队机：
- 排队
as 只要你看到 as，直到你看到 b.
- 出队
as 并入队 bs 只要你看到 bs，直到你看到 c
- 出队
bs 只要你看到 cs。
- 如果您在没有额外输入且队列为空的情况下结束此过程，请接受。
双栈 PDA：
- 当你看到
a 时按下 a，当你看到 b 时弹出 a，使用第一个堆栈确保 a^n b^n；
- 通过在看到
b 时按下 b 并在看到 c 时弹出 b 来使用第二个堆栈来确保 b^n c^n；
- 如果在此过程结束时两个堆栈都为空，则接受。
图灵机：
- 通过将每个
a 替换为 A 并删除匹配的 c; 来确保 a^n ... c^n
- 通过擦除
A 和 b 的匹配对来确保 A^n b^n；
- 如果在此过程结束时您没有更多
A 并且没有更多 b，即磁带已完全清除，请接受。
我正在尝试为非上下文无关语言构造下推自动机 L={a^(n)b^(n)c^(n)|n>=1} 并且想到了两种方法。
First approach:-
I thought that for every 'a' in string I will push 3 'a' into the stack and for every 'b' in the string, I will pop 2 'a' from the stack now for every 'c' in the string I will still have 1 'a' in the stack.
第一种方法的问题：-生成的语言变成这样 L={a^(p)b^(m)c^(n)| p>=1 and 无法确定如何定义 m 和 n}
Second approach:-
We know that L={ a^(n)b^(m)c^(m)d^(n) | n>=0 } is a context-free language and L={ wxw | w∈(a,b)* } is also context-free language.
So, I thought L={ a^(n)b^(m)b^(m)c^(n) | n>=1 and m=floor((n+1)/2) }
第二种方法的问题：-不知道我们是否可以在不干扰堆栈元素的情况下在 PDA 中计算 floor(n+1/2)。
请帮助确定如何在第一种方法中定义 m 和 n，以及如何在 PDA 中找到 floor((n+1)/2)。
如果需要，JFLAP 文件可用于两者。
您未能为该语言构建下推自动机的一个原因是没有。 Bar Hillel pumping lemma 显示了这一点。
概括证明，假设可以做到。然后，对于一些p，每个大于p的字符串可以划分为uvwxy，s.t.,
|vwx| < p
|vx| > 1
uvnwxny 也被接受自动机，对于任何 n.
第一条规则意味着 vwx 不能跨越三个区域，最多只能跨越两个（对于足够大的字符串）。第二条和第三条规则现在意味着您可以泵送，以便未跨越的区域小于其他区域中的至少一个区域。
正如 Ami Tavory 所指出的，这种语言没有 PDA，因为这种语言不是上下文无关的。如果您使用队列而不是堆栈、使用两个堆栈或使用图灵机（都是等效的），则很容易识别这种语言。
排队机：
- 排队
as 只要你看到as，直到你看到b. - 出队
as 并入队bs 只要你看到bs，直到你看到c - 出队
bs 只要你看到cs。 - 如果您在没有额外输入且队列为空的情况下结束此过程，请接受。
双栈 PDA：
- 当你看到
a时按下a，当你看到b时弹出a，使用第一个堆栈确保a^n b^n； - 通过在看到
b时按下b并在看到c时弹出b来使用第二个堆栈来确保b^n c^n； - 如果在此过程结束时两个堆栈都为空，则接受。
图灵机：
- 通过将每个
a替换为A并删除匹配的c; 来确保 - 通过擦除
A和b的匹配对来确保A^n b^n； - 如果在此过程结束时您没有更多
A并且没有更多b，即磁带已完全清除，请接受。
a^n ... c^n