接受以下语言的下拉自动机

Question

我需要为以下语言构建下推式自动化：L = {a ^ n b ^ m | 2n> = m}有人可以帮我吗？

Answer 1

想到两种方法：

1. 尝试以明智的方式使用堆栈从头开始编写PDA
2. 编写CFG，然后依赖于显示PDA接受所有CFG语言的结构

采用方法1，请注意PDA就像NFA一样，可以将符号推入堆栈并将其弹出。如果我们希望2n> = m，则意味着我们希望a的数量至少是b的数量的一半。也就是说，我们希望每两个b至少有一个a。这意味着，如果我们将堆栈中的所有a都压入，那么对于堆栈中的每个a，我们需要读取的b都不得超过两个。这建议使用这样的PDA：

1. read all the a's, pushing into the stack
2. read b's, popping an a for every two b's you see
3. if you run out of stack but still have b's to process, reject
4. if you run out of input at the same time or sooner than you run out of stack, accept

关于状态和转换：

Q    S    E    Q'    S'

q0   Z    a    q0    aZ   // these transitions read all the a's and 
q0   a    a    q0    aa   // push them onto the stack

q0   a    b    q1    a    // these transitions read all the b's and
q1   a    b    q2    -    // pop a's off the stack for every complete
q2   a    b    q1    a    // pair of b's we see. if we run out of a's
                          // it will crash and reject

q0   Z    -    q3    Z    // these transitions just let us guess at any
q0   a    -    q3    a    // point that we have read all the input and
q1   Z    -    q3    Z    // go to the accepting state. note that if
q1   a    -    q3    a    // we guessed wrong the PDA will crash there
q2   Z    -    q3    Z    // since we have no transitions defined.
q2   a    -    q3    a    // crashing rejects the input.

这里，接受条件处于状态q3，没有更多的堆栈。

要执行第二个选项，您将像这样编写CFG：

S -> aSbb | aS | e

然后您的PDA可以执行以下操作：

push S onto the stack
pop from the stack and push onto the stack one of the productions for S
if you pop a terminal off the stack, consume the nonterminal from input
if you pop a nonterminal off the stack, replace it with some production for that nonterminal

根据CFG不确定地生成所有可能的推导。如果输入是该语言中的字符串，则这些派生之一将消耗所有输入，并使堆栈为空，这是暂停/接受条件。