(a ^ n b ^ n)^ m c ^ m的下推自动机 [英] Pushdown automaton for (a^n b^n)^m c^m

问题描述

我一直在为该自动机构建转换功能.

I'm stuck building the transition functions for this automaton.

我想我应该为每个a堆叠一个1，然后为每个b堆叠它

I suppose I should stack a 1 for each a and unstack it for each b

c的数量等于ab对的数量，所以我认为我应该为遇到的每个b堆叠一个0.问题是:如何将1拆开并同时加0?

The number of c's equals the number of ab pairs, so I think I should stack a 0 for each b I encounter. Thing is: how do I unstack 1s and add 0s at the same time?

推荐答案

不要在每次遇到b时将0推入堆栈.相反，每次遇到b且堆栈为空或堆栈顶部为0时，将0推入堆栈.

Don't push a 0 onto the stack each time you encounter a b. Instead, push a 0 onto the stack each time you encounter a b and the stack is empty or the top of the stack is a 0.

因此，将您的命名法用于aabbabcc:

So, using your nomenclature for aabbabcc:

read a push 1
read a push 1
read b pop 1
read b pop 1
stack is empty so push 0
read a push 1
read b pop 1 
top of stack is 0 so push 0
read c pop 0
read c pop 0

堆栈为空，因此我们接受此字符串.

Stack is empty so we accept this string.

这篇关于(a ^ n b ^ n)^ m c ^ m的下推自动机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！