chapter-7-下推自动机.pptVIP

第七章、下推自动机 一、下推自动机概念 定义1、下推自动机（Pushdown Automaton，PDA）M是一个七元组： 其中，Q是有限状态集，F是终止状态集， 是输入字母表， 是下推 栈字母表， 是初始栈顶元素， 是起始状态， 是状态与栈元 素转换函数： 第七章、下推自动机 事实上，下推自动机在某个状态 和某个栈顶元素 下， 不仅扫描到某个字符 时，可以有运算式： 而且不扫描任何字符，也可以有运算式（称为空动作）： 第七章、下推自动机 下推自动机的结构如下图所示： 正如： RL语言 ? 有穷自动机 一样 CFL语言 ? 下推自动机 第七章、下推自动机 例2、设计一个下推自动机接受语言 注意到 中元素（串）有一个共同特点，串的中点为字符c，前半 部可以是字母表{0,1}上的任意一个串，但后半部必须是前半部的逆 串（即 中的每个串都是回文）。下推自动机中有一个辅助存储 器：下推栈。栈结构的主要特点就是后进先出的存取顺序，根据这 个特点，容易设计一个以空栈形式接受语言的PDA接受 。 我们可以设置3个栈字母，设为R，B，G，其中R作为初始栈顶元素。 扫描到字符c之前，PDA的状态为 （显然 就是初始状态），在 状态下，每扫描到一个字符“0”，就在栈中压入一个栈元素B，每 读到一个“1”就在栈中压入一个元素G。 第七章、下推自动机 当扫描到字符“c”时，PDA的状态改为 。在 状态下，假如当前 的栈顶元素为B，而读到的字符恰好是“0”，则把栈顶弹出，继续 读下一个字符（如果读到的字符为“1”，则说明c后面的子串不是c 之前的子串的逆，这个输入串不被接受）；假如当前的栈顶元素为 G，而读到的字符恰好为“1”，则把栈顶元素弹出（同样，如果这 时读到字符是“0”，也不接受输入串）。当把输入串全部扫描完时， 如果恰好露出初始栈顶R，则说明输入串是 的一个元素，用一个空 动作把初始栈顶弹出，把栈倒空，表示这个输入串被接受。 根据上面的讨论，可以写出接受 的PDA如下： 其中 第七章、下推自动机 且 第七章、下推自动机 例如：对于输入串 的工作过程可以用下面的推导反映出来： 最后一个结果 表明，输入串全部扫描完，而且栈被倒空，因此这个输入串被 接受。 参照p238页，例7-1，比较。 下推自动机 第七章、下推自动机 例3： 设计一个接受语言 的下推自动机 。 中的串同 类似，也可以分为前半部分和后半部分，前半部 分可以是字母表{0,1}上的任何串，后半部分必须是前半部分的逆串。同 不同的是， 中没有中界符号c。因此，从输入串的第2个字符开始，每读到一个字符（0或1），由于不知道它是前半部分或者是后半部分的字符，因此动作函数就要从两方面考虑，压入一个新栈顶还是弹出当前栈顶（在符合要求的情况下）。因此，相关的动作函数就有两个值。 接受 的下推自动机 的形式表示在p242例7-2。 第七章、下推自动机 例4： 设计一个接受语言 的下推自动机 。 令 （1）、 （2）、 （3）、 （4）、 那么，运算表如下： 第七章、下推自动机 字母 0 1 ε 栈 0 $ ε 0 $ ε 0 $ ε q1 Ф Ф Ф Ф Ф Ф Ф Ф {（q2， $）} q2 Ф Ф {（q2， 0）} q3 Ф q4 第七章、下推自动机 运算举例如下： 注意： 表示机器读a时，可以用c来替换栈顶的b。 1 q3 q4 q1 q2 第七章、下推自动机 例5： 给出识别 PDA。 解、显然PDA先读完i个a，并把它们全部放入栈，然后与b或c匹配，由于机器不知是与b还是与c，因此便想到了非确定性，即用2个分支去做，即： 第七章、下推自动机 q5 q7 q2 q1 q1 q3 q4 q5 q6 第七章、下推自动机 形式定义如下： （1） （2） （3） （4） （5） q1 （6） δ，大家看表后，计