下推式自动机如何知道如何阅读回文? [英] How does a pushdown automaton know how to read a palindrome?

问题描述

例如，PDA如何知道如何以L = {a，b} *读取回文?

For example, how does a PDA know how to read a palindrome in L = {a, b}*?

在{a，b} *上接受回文的PDA:

PDA that accepts palindromes over {a,b}* :

因此，根据我的PDA图纸:

So, based on my drawing of the PDA:

它如何知道字符串的前半部分何时位于最后一个终端(字母字母)上，因此知道从状态0转到状态1(而且知道从栈中向后弹出字母) ，从而形成回文)?

How does it know when the first half of the string is on the final terminal (letter of the alphabet), and therefore knows to go from state 0 to state 1 (and furthermore knowing to "pop" letters from the stack backwards, hence creating the palindrome)?

推荐答案

这是不确定的下推式自动机.您问题的答案是猜测，并且可以假定是正确猜测.如果可以沿 w 处理的任何路径导致 w 被接受，则不确定自动机将接受字符串 w

This is a nondeterministic pushdown automata. The answer to your question is that it guesses and may be assumed to guess correctly. Nondeterministic automata accept a string w if any path along which w might be processed results in w's being accepted.

如果我们将接受定义为处于接受状态的空堆栈，那么上述NPDA可以接受的唯一方法是:

If we define acceptance as having an empty stack in an accepting state, then the only way something can be accepted by the above NPDA is if:

• 它将状态为q0的东西放到堆栈上
• 它最终猜测它需要读取字符串的后半部分
• 它在q1中读取它压入堆栈的内容，但向后读取

NPDA做出三种猜测":

There are three "guesses" that the NPDA makes:

1. 当它猜测e e/e时，它猜测该字符串是一个偶数回文，其中用e代替lambda.
2. 当它猜出e/e时，它猜测该字符串是一个奇数回文，且在两个半部之间有一个in，其中e代替了lambda.
3. 它猜测该字符串是一个奇数回文，当猜测b e/e时，它在两个半部之间，其中e用于代替lambda.

以上三个猜测中的每一个都还猜测该字符串的前半部分(可能的中间元素除外)已经被看到.

Each of the above three guesses is also guessing that the first half of the string, excluding a possible middle element, has been seen already.

这个猜测最终将适用于所有回文，而除了回文之外，将不适用，因此NPDA接受PAL.

This guess will eventually be true for any palindrome, and it won't be true for anything but a palindrome, so the NPDA accepts PAL.

这篇关于下推式自动机如何知道如何阅读回文?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！