> 文章列表 > 形式语言和自动机总结---PDA下推自动机

形式语言和自动机总结---PDA下推自动机

文章列表

形式语言和自动机总结---PDA下推自动机

第6章下推自动机

下推自动机相当于 $\\varepsilon -NFA+$ 栈:他既有非确定性也支持空转移，他拥有栈的性质，体现在它能够识别w $w^{R}$ 但是不能识别ww和 $a^{n}b^{n}c^{n}$ (图灵机可以识别)语言。

将000入栈，每读入一个1弹出一个0....当输入完所有的1栈空，则就是识别0n1n的PDA

每次根据读头、状态、栈顶三个东西进行跳转，修改当前状态、改变读头，弹出一个符号往栈里压入多个符号多个符号构成的字符串的长度可以是0个1个或者多个，0个代表弹出栈顶元素，1个代表保持或者修改栈顶符号，多个表示弹出一个符号压入多个符号。

PDA的设计

一般有两种方式:空栈接受和终态接受，他们是等价的，空栈接受有利于消除一些无用的状态。

构造PDA关键在于理解非确定性。

1.设计识别{ $0^{n}1^{n}$ |n $\\geq$ 1}的PDA

2.升级版设计识别{ $0^{n}1^{n}$ |n $\\geq$ 0}的PDA

*思考:1当识别0001111扫描完整个串的空串才能停下来在q3接受状态如果后边还有字符他会卡死Z0可以判断是否扫描完整个串.2.000111我00之间也可以通过空转移到达q2但是此时读头上是0，而我只能接受1的读字符串的动作因此会卡死，由于PDA具有非确定性，只有在wwr的形式上才能接受，否则就会卡死。

3.设计识别{w $w^{R}$ |w $\\epsilon$ $(0+1)^{*}$ }的PDA

4.The set of all strings of 0’s and l’s such that no prefix has more l’s than 0’s.

5.接受 Leq = {w ∈ {0,1} | w 中字符 0 和 1 的数量相同 } 的 PDA

以空栈方式接受

思路，如果第一个读入1/0第二个读入0/1那么直接弹栈,如果都是0或者都是1，那么压栈，直到栈弹空。

以终态方式接受:

6.接受 L = { $0^{n}1^{m}$ | 0 ≤ n ≤ m ≤ 2n } 的 PDA

方法1:由于PDA具有非确定性,所以可以让一次弹入1个或者2个0，最后读入1再弹出1

方法2：第一次读入n个0，第二次添加情况读入1弹出一个0或者两个0

思考:如果我们设计这种语言对应的文法:

$S\\rightarrow 0S1\\,\\,|\\,\\,0S11\\,\\,|\\,\\,\\varepsilon$ 左边保证了他小于2n，右边保证了他大于n,而“|”体现了文法的非确定性。

7.

8. $Design\\,\\,PDA\\,\\,in\\,\\, the\\,\\, language\\,\\,of\\,\\,{{a^{i}b^{j}c^{k}}}\\,\\,(i\\neq j\\,\\,|\\,\\,j\\neq k)$

case1:a和b的数量不相等,先让a入栈，再让b入栈，如果读到a就弹出，如果a不够那就b一直入栈这个时候肯定是不相等的就符合题意了case2:bc不相等同理

9.The set of all strings of 0's and 1's with twice as many 0's as 1's.

利用文法比较简单

PDA性质

由于PDA具有非确定性，仅用状态无法很好描述当前的性质

终态方式和空栈方式接受PDA

等价性的证明(不考但是对理解PDA有用)

用 $P_{F}$ 构造 $P_{N}$ 用在PF上增加一个新状态，并且利用空转移，将pn的栈底X0压入栈中，pf模拟pn该接受的字符串

PDA和CFG的转换

cfg $\\rightarrow$ pda

由于PDA的非确定性，他有很多种形式

1.一部分来自规则2.一部分来自终止符号

举例1:对 $S\\rightarrow\\,aAA\\,\\, A\\rightarrow\\,aS\\,|\\,bS\\,|a\\,\\,$ 设计文法.

举例2:任何的PDA都可以通过文法转换过来

pda $\\rightarrow$ cfg

上图的含义是:初始状态是q，当前栈顶符号是X，想要完全弹出X需要抵消一个w,也就是说从状态q完全弹出x会派生出字符串w,r是字符弹出后所到达的状态,r不知道是什么状态，期间能消耗掉很多串，而消耗掉的串可以认为是由X派生出来的

DPDA的设计

DPDA就是保留接受空串的能力，但是消除非确定性的有穷自动机。

DPDA和PDA不是等价的但是他可以识别某些特定的串。