对于上下文无关的语法，我如何将其转换为等效的下推自动机? [英] For a context free grammar, how do i convert it to an equivalent push down automaton?

问题描述

对于Σ= {0，1，2}上的上下文无关文法G，使用起始变量S:
S→0S0 | 1S1 | 2S2 | Y
Y→22

For a context-free grammar G over Σ = {0, 1, 2}, with start variable S:
S → 0S0 | 1S1 | 2S2 | Y
Y → 22

如何将其转换为等效的下推式自动机

How do i turn this into an equivalent Push-Down automaton

推荐答案

下推式自动机可以将符号推入堆栈顶部并将其弹出.它还可以根据最上面的堆栈符号进行转换.我们需要考虑一种机制，该机制将允许我们通过操纵堆栈来接受正确的语言.

A pushdown automaton can push symbols on top of a stack and pop them off. It can also base its transitions on the topmost stack symbol. We need to think of a mechanism that will allow us accept the right language by manipulating our stack.

您的语法生成的语言具有以下特征:

The language your grammar generates has the following characteristics:

1. 它的中间是22
2. 这是{0, 1, 2}上的回文.也就是说，它读取的向前与向后读取的内容相同.

1. It has 22 in the middle
2. It is a palindrome over {0, 1, 2}. That is, it reads the same forwards as backwards.

我们需要记住"字符串的开头，以便能够判断字符串的结尾是否向后重复.这是堆栈的一个好用例:我们可以在看到符号时将它们压入堆栈，然后在读回它们时将其弹出.另一注:我们知道我们只有在读完22后才能尝试开始读回.

We need to "remember" the beginning of the string so that we're able to tell whether the end of the string is being repeated backwards. This is a good use case for a stack: we can push the symbols onto the stack as we see them, and then pop them off as we're reading them back. One other note: we know we can only try to start reading back after reading 22.

首先，我们阅读所有内容并将其压入堆栈，直到找到"22":

First, we read everything and push it onto the stack until we find "22":

Q    s   S    Q'    S'
----------------------
// read 0s and 1s and push them on the stack
q0   0   Z    q0    0Z
q0   0   0    q0    00
q0   0   1    q0    01
q0   1   Z    q0    1Z
q0   1   0    q0    10
q0   1   1    q0    11

// if you read a 2, pus it on the stack and
// go to a new state where we look for a second 2
q0   2   Z    q1    2Z
q0   2   0    q1    20
q0   2   1    q1    21

// if you read a 2 and then 0 or 1, go back to the
// initial state and keep reading input. otherwise,
// if you find a second two, proceed
q1   0   2    q0    02
q1   1   2    q0    12
q1   2   2    q2    22

// assume the '22' we just saw was not the one in
// the middle of the input string and that we need
// to keep reading input.
q2   0   2    q0    02
q2   1   2    q0    12
q2   2   2    q2    22

// assume the '22' we just saw was the one in the
// middle of the input string and that we now need
// to start reading from the stack.
q2   -   2    q3    - 
q3   -   2    q4    -
q4   0   0    q4    -
q4   1   1    q4    -
q4   2   2    q4    -
q4   -   Z    q5    Z

// we read a string in the language and are
// ready to accept in q5. go to dead state q6
// explicitly if still have input.
q5   0   Z    q6    Z
q5   1   Z    q6    Z
q5   2   Z    q6    Z

// consume the rest of the input in the dead state.
q6   0   Z    q6    Z
q6   1   Z    q6    Z
q6   2   Z    q6    Z

如果您定义崩溃使机器明确地拒绝该字符串，则通常不必严格转换q5和q6.我将这些转换包括在内，以便PDA可以正常使用所有输入而不会崩溃.

The transitions for q5 and q6 aren't strictly necessary if you define crashing the machine to mean the string is definitively rejected, which is typical. I include those transitions so the PDA will gracefully exhaust all input without crashing.

此PDA不确定.没有针对该语言的确定性PDA.基本上，在读取任何子字符串22之后，我们必须猜测22的实例是否在中间.如果是这样，我们需要开始读回初始字符串以查看是否有回文.如果没有，我们需要继续将符号压入堆栈.

This PDA is not deterministic. There is no deterministic PDA for this language. Basically, after we read any substring 22, we have to guess whether that instance of 22 was the one in the middle. If so, we need to start reading the initial string back to see if we have a palindrome. If not, we need to keep pushing symbols on the stack.

这篇关于对于上下文无关的语法，我如何将其转换为等效的下推自动机?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！