有限自动机理论05章下推自动机.ppt

《有限自动机理论05章下推自动机.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章下推自动机PDAFA识别正则语言(右线性语言)PDA识别上下文无关语言FA只能处理正则语言正则文法生成无穷语言是由于A->wA不需要记录w的个数无关文法生成无穷语言A->αAβ需要记录α和β之间的对应关系无法用FA的有穷个状态来表示。为FA扩充一个无限容量的栈用栈的内容和FA的状态结合起来就可以表示无限存储。这种模型就是下推自动机PDAPDA作为形式系统最早于1961年出现在Oettinger的论文中。与上下文无关文法的等价性由Chomsky于1962年发现。与FA比较PDA具有一个栈存储器有两个操作：入栈---将内容压入栈中出

2、栈---将栈顶元素移出下推自动机物理模型a1a2a3…aj…anan+1…FSC…存储带栈存储器栈存储器存放不同于字母的符号只能对栈顶元素进行操作。下推自动机动作根据FSC当前的状态输入带上的当前字符栈顶符号进行状态改变和入栈或出栈操作将读头向右移动一个单元5.1.1确定的下推自动机例5-1语言L={w

3、w∈(a,b)*，且a、b个数相等}暂时不考虑状态(或PDA仅有一个状态)初始栈为空从左到右逐个扫描串w∈(a，b)*入栈若栈为空,当前符号是a,则A入栈若栈为空,当前符号是b,则B入栈若栈顶为A,当前符号是a,则A入栈若栈顶为B,当

4、前符号是b,则B入栈出栈若栈顶为A,当前符号是b，则A出栈若栈顶为B,当前符号是a，则B出栈若串w有相同个数的a和b当且仅当w扫描结束后，栈为空。注意PDA在两种情况下停机：串扫描结束没有对应的规则串扫描结束栈如果为空就接收扫描过的串。对于非正式的算法，用形式化的方式进行描述：特殊的符号Z0表示栈底初始化时先压入栈规则(指令)若x是w的当前符号D是栈顶符号则用符号串V代替D即将D弹出栈，而将串V压入栈具体若x是w的当前符号，栈顶符号为D将D弹出栈将A压入栈，成为新的栈顶一般地若x是w的当前符

5、号，栈顶符号为D表示：将D弹出栈将串A1A2…Ak压入栈(A1为新栈顶)例5-1算法的形式化描述<ε，Z0，ε>规则<ε，Z0，ε>表示将w扫描结束后，将栈置成空也表示该PDA可以接收空串ε思考：如何接收语言L={w

6、w∈(a,b)+,且a和b个数相等}?例：语言L={anbn

7、n≥0}定义：<ε，Z0，ε>则还可以接收语言{(ab)n

8、n≥0}，或{ambm(

9、ab)n

10、m≥0,n≥0}等语言。思考：如何接收语言L={anbn

11、n>0}L={anbn

12、n≥0}L={(ab)n

13、n>0}L={(ab)n

14、n≥0}例5-2L={wcwT

15、w∈(a，b)*}识别语言思想：将w的各个字符压入栈后栈中的内容从栈顶到栈底的顺序刚好是wT的顺序为了区别压栈和出栈动作增加两个状态----read和matchPDA处于read状态时，处理整个串的前半部分，将对应的符号压入栈扫描到字母c时PDA的状态转为match开始处理整个串的后半部分，将栈中的内容出栈。规则若PDA处于状态qw的当前

16、字母是x当前栈顶符号为D则自动机的状态改变为q′并用符号串V代替D（在本例中）用Z代表任意的栈顶符号规则〈read，a，Z，read，AZ>可以表示以下3条规则：〈read，a，Z0，read，AZ0>〈read，a，A，read，AA>〈read，a，B，read，AB>用下列的规则来描述PDA〈read，a，Z，read，AZ>〈read，b，Z，read，BZ>〈read，c，Z，match，Z>〈match，a，A，match，ε>〈match，b，B，match，ε>〈match，ε，Z0，match，ε>若串w是该语言的合

17、法的串当且仅当w扫描结束后，栈为空。Z0符号栈串abbcbba的处理过程ABreadmatch=>B扫描到字母c栈内的内容（从栈顶到栈底）是扫描过的串的逆与未扫描过的串的顺序相同此时，不作出栈和入栈操作，仅仅把PDA的状态从read改变到match。接收语言L={anbn

18、n>0}〈q0，a，Z0，q0，AZ0>〈q0，a，A，q0，AA>〈q0，b，A，q1，ε>〈q1，b，A，q1，ε>〈q1，ε，Z0，q1，ε>5.1.2不确定的下推自动机例5-3语言L={wwT

19、w∈(a,b)*}没有中心点字符在扫描过程中，就没有确定的位置进

20、行状态的变换具有不确定性。使用规则〈read，ε，Z，match，Z>来代替〈read，c，Z，match，Z>即在read状态时，可随时改变为match状态（栈的内容和扫描符号不变）〈read，a，Z，read，AZ>