题目：构造一个下推自动机PDA M,使N(M)={(a^m)(b^n)|0<m<=n<=2m}.
解：初看这道题，容易陷入构造N(M)={(a^m)(b^n)|m<=n}或N(M)={(a^m)(b^n)|n<=2m}的思维中去，很恼火题目为什么把两个条件加到了一起。
灵光一现：把 (a^m)(b^n)写成a^xa^yb^n，这个问题等于构造一个下推自动机M1,使它在空栈接收的时候有2x+y=n成立，则由于x+y=m,0=<y<=m,必有m<=n<=2m成立。而构造一个M1是不难的。构造的自动机(空栈接收)如下：
δ(q0,a,Z0)={(q0,AAZ0),(q1,AZ0)}
δ(q0,a,A)={(q0,AAA),(q1,AA)}
δ(q1,a,A)={(q1,AA)}
δ(q1,b,A)={(q2,ε)}
δ(q2,b,A)={(q2,ε)}
本文地址：http://com.8s8s.com/it/it34475.htm