I . 下推自动机 设计
设计下推自动机 , 可以识别 { w w R : w ∈ { 0 , 1 } ∗ } \{ ww^R : w \in \{ 0, 1\} ^* \}{ww
R
:w∈{0,1}
∗
} 语言 ;
R RR 表示镜面反射 , 如果 w ww 是由 0 , 1 0 , 10,1 组成的字符串 011 011011 , 那么 w R w^Rw
R
就是其镜面反射 100 100100 字符串 , 然后将 w ww 和 w R w^Rw
R
串联在一起 , w w R = 011100 ww^R = 011100ww
R
=011100 ;
1 . 首先生成开始状态 ;
开始状态是接受状态 , 因为如果字符串是空字符串 , 空字符串的镜面反射还是空字符串 , 因此读取空字符串后的状态 , 是接受状态 , 开始状态其本身就是接受状态 ;
2 . 向栈底放入 字符 S SS , 用于作为栈底的标识 , 生成 ε , ε → S \varepsilon , \varepsilon \to Sε,ε→S 指令 ;
ε , ε → S \varepsilon , \varepsilon \to Sε,ε→S 指令包含 2 22 部分 : 读取字符 , 和 栈内操作 ;
读取字符 : 指的是读取的带子上的字符串 , ε , ε → S \varepsilon , \varepsilon \to Sε,ε→S 中前面的 ε \varepsilonε 指的是从带子上读取 ε \varepsilonε ;
栈内操作 : 使用某个字符 替换 栈顶字符 ; ε , ε → S \varepsilon , \varepsilon \to Sε,ε→S 中后面的 ε → S \varepsilon \to Sε→S 指的是使用 S SS 字符替换栈顶的空字符 ε \varepsilonε ;
3 . 镜面反射的前半个镜面 :
0 00 入栈 : 每读取一个 0 00 , 就将 0 00 放入栈中 , 生成指令 0 , ε → 0 0, \varepsilon \to 00,ε→0 ;
1 11 入栈 : 每读取一个 1 11 , 就将 1 11 放入栈中 , 生成指令 1 , ε → 1 1, \varepsilon \to 11,ε→1 ;
4 . 跳转到新的状态 , 在新的状态执行 后半个镜面的操作 :
无条件跳转就是读取 ε \varepsilonε , 并且栈中元素保持不变 , 即使用 ε \varepsilonε 替换栈顶的 ε \varepsilonε ;
生成的指令为
ε , ε → ε \varepsilon , \varepsilon \to \varepsilon
ε,ε→ε
当前的下推自动机 :
5 . 镜面反射的后半个镜面 :
0 00 出栈 : 每读取一个 0 00 , 从栈里拿走一个 0 00 , 生成指令 0 , 0 → ε 0, 0 \to \varepsilon0,0→ε ;
1 11 出栈 : 每读取一个 1 11 , 从栈里拿走一个 0 00 , 生成指令 1 , 1 → ε 1, 1 \to \varepsilon1,1→ε ;
6 . 栈清空 , 跳转到最后的 接受状态 : 上述出栈操作执行若干次后, 总能将栈内的字符取出完毕 , 只剩下一个 S SS 字符 , 该字符是栈底的标识 ; 此时将 S SS 字符从栈内取出即可 ;
生成如下指令 :
ε , S → ε \varepsilon , S \to \varepsilon
ε,S→ε
指令含义是 读取 ε \varepsilonε 字符 , 使用 ε \varepsilonε 字符替换栈中的 S SS 字符 ;
最后跳转到的状态是接受状态 ;
当前下推自动机为 :
