Permalink为L={a（2*m）c（4*n）dnbm | m，n构造下推自动机≥ 0}

先决条件—— 下推自动机 , 下推自动机最终状态验收 PDA在编译器设计中起着非常重要的作用。这就是为什么需要在PDA上有一个良好的实践。我们的目标是为L={a构建一个PDA ^（2*m） C ^（4*n） D ^N B ^M |m，n≥ 0}

示例——

Input: aaccccdb
Output: Accepted

Input: aaaaccccccccddbb
Output: Accepted

Input: acccddb
Output: Not Accepted 

本PDA中使用的方法- 在处理给定的输入字符串时，可能有四种情况。

案例1:m=0- 在这种情况下，输入字符串的形式为{c ^（4*n） D ^N }.在这种情况下，继续在堆栈中按c，直到遇到“d”。收到“d”后，检查堆栈顶部是否为“c”，然后从堆栈中弹出“cccc”。继续弹出cccc，直到处理完字符串的所有d。如果到达输入字符串的末尾，堆栈变为空，则到达最终状态，即接受输入字符串，否则将移动到死状态。

案例2：n=0– 在这种情况下，输入字符串的形式为{a ^（2*m） B ^M }.在这种情况下，继续在堆栈中按a，直到遇到“b”。收到b后，检查堆栈顶部是否为“a”，然后从堆栈中弹出“aa”。继续弹出aa，直到字符串的所有b都被处理。如果到达输入字符串的末尾，堆栈变为空，则到达最终状态，即接受输入字符串，否则将移动到死状态。

案例3:m，n>0- 在这种情况下，输入字符串的形式为{（a ^（2*m） C ^（4*n） D ^N B ^M }.在这种情况下，继续在堆栈中推a和c，直到遇到“d”。收到d后，检查堆栈顶部是否为“c”，然后从堆栈中弹出“cccc”。继续弹出cccc，直到处理完输入字符串的所有d。然后在收到b时，检查堆栈顶部是否为“a”，然后从堆栈中弹出“aa”。继续弹出aa，直到输入字符串的所有b都被处理。如果我们到达输入字符串的末尾，堆栈变为空，则到达最终状态，即接受输入字符串，否则移动到死状态。

案例4:m，n=0– 在这种情况下，输入字符串将为空。因此直接跳到最终状态。

注——

1. 我们使用（b，a/€，aa）弹出2个a，即当遇到b时，使用aa。
2. 我们使用（d，c/€，cccc）弹出4个c，即当遇到d时，cccc。