精华内容
下载资源
问答
  • 下推自动机

    2015-08-18 00:51:51
    描述了形式语言与自动机课程中关于下推自动机的相关内容,包括相关概念和例题等。
  • I . 下推自动机 设计 II . 上下文无关语法 ( CFG ) 等价于 下推自动机 ( PDA )





    I . 下推自动机 设计



    设计下推自动机 , 可以识别 { w w R : w ∈ { 0 , 1 } ∗ } \{ ww^R : w \in \{ 0, 1\} ^* \} {wwR:w{0,1}} 语言 ;


    R R R 表示镜面反射 , 如果 w w w 是由 0 , 1 0 , 1 0,1 组成的字符串 011 011 011 , 那么 w R w^R wR 就是其镜面反射 100 100 100 字符串 , 然后将 w w w w R w^R wR 串联在一起 , w w R = 011100 ww^R = 011100 wwR=011100 ;


    1 . 首先生成开始状态 ;

    开始状态是接受状态 , 因为如果字符串是空字符串 , 空字符串的镜面反射还是空字符串 , 因此读取空字符串后的状态 , 是接受状态 , 开始状态其本身就是接受状态 ;

    在这里插入图片描述


    2 . 向栈底放入 字符 S S S , 用于作为栈底的标识 , 生成 ε , ε → S \varepsilon , \varepsilon \to S ε,εS 指令 ;


    ε , ε → S \varepsilon , \varepsilon \to S ε,εS 指令包含 2 2 2 部分 : 读取字符 , 和 栈内操作 ;

    • 读取字符 : 指的是读取的带子上的字符串 , ε , ε → S \varepsilon , \varepsilon \to S ε,εS 中前面的 ε \varepsilon ε 指的是从带子上读取 ε \varepsilon ε ;

    • 栈内操作 : 使用某个字符 替换 栈顶字符 ; ε , ε → S \varepsilon , \varepsilon \to S ε,εS 中后面的 ε → S \varepsilon \to S εS 指的是使用 S S S 字符替换栈顶的空字符 ε \varepsilon ε ;

    在这里插入图片描述


    3 . 镜面反射的前半个镜面 :


    0 0 0 入栈 : 每读取一个 0 0 0 , 就将 0 0 0 放入栈中 , 生成指令 0 , ε → 0 0, \varepsilon \to 0 0,ε0 ;

    1 1 1 入栈 : 每读取一个 1 1 1 , 就将 1 1 1 放入栈中 , 生成指令 1 , ε → 1 1, \varepsilon \to 1 1,ε1 ;

    在这里插入图片描述


    4 . 跳转到新的状态 , 在新的状态执行 后半个镜面的操作 :


    无条件跳转就是读取 ε \varepsilon ε , 并且栈中元素保持不变 , 即使用 ε \varepsilon ε 替换栈顶的 ε \varepsilon ε ;

    生成的指令为

    ε , ε → ε \varepsilon , \varepsilon \to \varepsilon ε,εε


    当前的下推自动机 :

    在这里插入图片描述


    5 . 镜面反射的后半个镜面 :


    0 0 0 出栈 : 每读取一个 0 0 0 , 从栈里拿走一个 0 0 0 , 生成指令 0 , 0 → ε 0, 0 \to \varepsilon 0,0ε ;

    1 1 1 出栈 : 每读取一个 1 1 1 , 从栈里拿走一个 0 0 0 , 生成指令 1 , 1 → ε 1, 1 \to \varepsilon 1,1ε ;

    在这里插入图片描述


    6 . 栈清空 , 跳转到最后的 接受状态 : 上述出栈操作执行若干次后, 总能将栈内的字符取出完毕 , 只剩下一个 S S S 字符 , 该字符是栈底的标识 ; 此时将 S S S 字符从栈内取出即可 ;


    生成如下指令 :

    ε , S → ε \varepsilon , S \to \varepsilon ε,Sε

    指令含义是 读取 ε \varepsilon ε 字符 , 使用 ε \varepsilon ε 字符替换栈中的 S S S 字符 ;


    最后跳转到的状态是接受状态 ;


    当前下推自动机为 :

    在这里插入图片描述





    II . 上下文无关语法 ( CFG ) 等价于 下推自动机 ( PDA )



    假设某语言由 上下文无关语法 ( CFG ) 生成 , 找到一个 下推自动机 ( PDA ) 识别该语言 ;


    构造下推自动机流程 ( PDA ) :


    构造下推自动机 , 包含 3 3 3 个状态 , 开始状态 q s t a r t q_{start} qstart , Loop 循环状态 q l o o p q_{loop} qloop , 可接受状态 q a c c e p t q_{accept} qaccept ;


    1 . q s t a r t q_{start} qstart 开始状态 :

    在这里插入图片描述

    读取 ε \varepsilon ε 字符 , 使用 T S TS TS 替换栈顶的 ε \varepsilon ε , 对应的指令为


    ε , ε → T S \varepsilon , \varepsilon \to TS ε,εTS

    其中的 S S S 是栈顶的标识 , T T T 是栈内的实际字符 ;

    在这里插入图片描述


    2 . q l o o p q_{loop} qloop 循环阶段 , 根据 上下文无关语法 ( CFG ) 做替换 ;


    ① 当栈顶是变元时 , 作变换 , 读取 ε \varepsilon ε , 即什么都不读取 , 将栈顶的变元 替换成 w w w , 生成的 下推自动机 指令为 " ε , A → w \varepsilon , A \to w ε,Aw " , 对应着的上下文无关语法规则为 A → w A \to w Aw ;

    ② 当栈顶是终端字符 ( 常元 ) , 让带子上的 读头 读取一个终端字符 , 对应的栈中 , 将栈顶的终端字符删除 , 相当于使用 ε \varepsilon ε 替换终端字符 , 生成指令 " a , a → ε a , a \to \varepsilon a,aε " ;


    一直读取 终端字符 , 并将栈顶的终端字符删除 , 一直循环该操作 , 直到 栈顶是一个变元 未为止 ;

    在这里插入图片描述


    3 . 跳转到 q a c c e p t q_{accept} qaccept 状态 : 当栈内的字符都出栈后 , 只剩下一个 S S S 字符作为栈底标识 , 此时 S S S 出栈 , 生成对应的 下推自动机指令 " ε , S → ε \varepsilon , S \to \varepsilon ε,Sε " , 即使用空字符 ε \varepsilon ε 替换栈内的 S S S 字符 ;

    之后跳转到最后一个状态 , q a c c e p t q_{accept} qaccept 可接受状态 ;

    在这里插入图片描述

    展开全文
  • 一、下推自动机计算过程、 二、上下文无关文法 CFG 转为下推自动机 PDA 流程



    参考博客 :





    一、下推自动机计算过程



    1 . 下推自动机 ( PDA ) 提升了自动机计算能力 : 在上述自动机的基础上 , 提升该自动机的计算能力 , 引入一个新的栈结构 ;

    栈特点 : ① 后进先出 , ② 存储能力无限 ;


    2 . 下推自动机计算有两个部分 , 一个是字符的读取 , 一个是栈内字符的存取 , 栈内只有最上面的字符会被替换 ;


    3 . 下推自动机 ( PDA ) 的指令格式 : 该指令包含了 上述讲的两个操作 ;


    1 , 0 → ε 1 , 0 \to \varepsilon 1,0ε


    ① 自动机字符读取 : 左侧的 1 1 1 是从带子上读取的字符 ;

    ② 栈内字符存取操作 : 0 → ε 0 \to \varepsilon 0ε 是需要在栈上进行的操作 , 将栈顶的 0 0 0 取出 , 然后将 ε \varepsilon ε 放入到栈中 , 相当于在栈中 , 使用 ε \varepsilon ε 将栈顶的 0 0 0 替换掉 ;





    二、上下文无关文法 CFG 转为下推自动机 PDA 流程



    上下文无关文法 CFG 转为下推自动机 PDA 流程 :

    ① 开始状态 : 开始状态 q s t a r t \rm q_{start} qstart , 跳转到 q l o o p \rm q_{loop} qloop 状态的指令 ε , ε → K \rm \varepsilon , \varepsilon \to K ε,εK , 使用 K \rm K K 替换栈内空字符 ε \varepsilon ε , 即将 K \rm K K 放入栈中 ;

    ② 循环状态 : q l o o p \rm q_{loop} qloop 状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;

    基本指令 S → a T b ∣ b \rm S \to aTb|b SaTbb ,
    生成为 " ε , S → a T b \rm \varepsilon , S \to aTb ε,SaTb " 和 " ε , S → b \rm \varepsilon , S \to b ε,Sb " 两条指令 , 前面都是读取空字符作为栈读取的信息 ;

    终端字符指令 , 如果存在终端字符 a \rm a a b \rm b b , 那么生成 a , a → ε \rm a, a \to \varepsilon a,aε b , b → ε \rm b, b \to \varepsilon b,bε 两条指令 , 含义是读取栈顶 a \rm a a 字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;


    ③ 接受状态 : q l o o p \rm q_{loop} qloop 状态跳转到 q a c c e p t \rm q_{accept} qaccept 指令是 ε , K → ε \rm \varepsilon , K \to \varepsilon ε,Kε , 栈顶读取到 K \rm K K 字符删除 ;

    ④ 拆分指令 : 在循环状态 q l o o p \rm q_{loop} qloop 中的基本指令中存在多字符指令 , 如 ε , S → a T b \rm \varepsilon , S \to aTb ε,SaTb , S \rm S S 读取到空字符 ε \varepsilon ε , 使用 a T b \rm aTb aTb 字符替换栈顶的 S \rm S S 字符 , 这是 3 3 3 个字符 , 肯定不行 , 需要逐个放进去 , 先放 b \rm b b , 再放 T \rm T T , 最后放 a \rm a a ;

    最终分解为
    ε , S → b \rm \varepsilon , S \to b ε,Sb 读取空字符放入 b \rm b b 到栈顶 ,
    ε , ε → T \rm \varepsilon , \varepsilon \to T ε,εT 读取空字符放入 T \rm T T 到栈顶 ,
    ε , ε → a \rm \varepsilon , \varepsilon \to a ε,εa 读取空字符放入 a \rm a a 到栈顶 ;

    展开全文
  • I . 下推自动机 II . 下推自动机 计算过程 III . 下推自动机 计算结果 IV . 下推自动机 计算示例





    一、 下推自动机



    1 . 下推自动机 由来 : 下推自动机 ( PDA ) 是在 确定性有限自动机 ( DFA ) 基础上 扩展而来的 ;


    2 . 下面是 下推自动机 ( PDA ) 的示意图 :

    在这里插入图片描述

    ① 输入字符串 : 将输入的字符写在右侧的带子上 ;

    ② 开始状态 : 读取指针 ( 读头 ) 开始指向最左端字符 , 此时处于开始状态 ;

    ③ 启动自动机 , 自动机根据读取的指令进行计算 ;

    ④ 读取指令 : 每读取一个字符 , 自动机跳转到一个新的状态 , 指针向后移动一个格子 ;

    ⑤ 自动机停止 : 当读取指针指向输入的最右端 , 此时自动机就停止了 , 此时查看当前状态 , 如果当前是接受状态 , 称自动机接受该字符串 ( 带子上写的字符组成的字符串 ) , 反之 , 自动机不接受该字符串 ;





    二、下推自动机 计算过程



    1 . 下推自动机 ( PDA ) 提升了自动机计算能力 : 在上述自动机的基础上 , 提升该自动机的计算能力 , 引入一个新的栈结构 ;

    栈特点 : ① 后进先出 , ② 存储能力无限 ;


    2 . 下推自动机计算有两个部分 , 一个是字符的读取 , 一个是栈内字符的存取 , 栈内只有最上面的字符会被替换 ;


    3 . 下推自动机 ( PDA ) 的指令格式 : 该指令包含了 上述讲的两个操作 ;


    1 , 0 → ε 1 , 0 \to \varepsilon 1,0ε


    ① 自动机字符读取 : 左侧的 1 1 1 是从带子上读取的字符 ;

    ② 栈内字符存取操作 : 0 → ε 0 \to \varepsilon 0ε 是需要在栈上进行的操作 , 将栈顶的 0 0 0 取出 , 然后将 ε \varepsilon ε 放入到栈中 , 相当于在栈中 , 使用 ε \varepsilon ε 将栈顶的 0 0 0 替换掉 ;





    三、下推自动机 计算结果



    1 . 下推自动机 ( PDA ) 是否接受字符串 : 将带子上的字符全部读取完毕后 , 此时的状态如果是 接受状态 , 那么带子上的字符组成的字符串就可以被 下推自动机接受 ;


    2 . 计算能力 : 下推自动机 ( PDA ) 比 确定性有限自动机 ( DFA ) 多了栈上的操作 , 下推自动机 ( PDA ) 的计算能力比有限自动机 ( DFA ) 计算能力高 ;


    3 . 语言识别能力 : 确定性有限自动机 ( DFA ) 是不能识别 { 0 n 1 n : n ≥ 0 } \{ 0^n 1^n : n \geq 0\} {0n1n:n0} 语言的 , 但是 下推自动机 ( PDA ) 是可以认识该语言的 ;





    四、下推自动机 计算示例



    在这里插入图片描述

    上图的下推自动机有 4 4 4 个状态 q 1 , q 2 , q 3 , q 4 q_1 , q_2 , q_3 , q_4 q1,q2,q3,q4 ;

    读取 0011 0011 0011 字符串 , 并给出 下推自动机 计算过程 ;


    ε , ε → S \varepsilon , \varepsilon \to S ε,εS 指令含义 : 当读取 ε \varepsilon ε 字符后 , ε → S \varepsilon \to S εS 指的是在栈上的操作 , 从栈内取出 ε \varepsilon ε 字符 , 向栈内放入一个 S S S 字符 , 本质是在栈中使用 S S S 替换 ε \varepsilon ε 字符 ;





    1 . 开始状态 是 q 1 q_1 q1 , 此时读头指向 0 0 0 位置 , 栈内是空的 ;

    在这里插入图片描述


    2 . 开始状态 q 1 q_1 q1 : 读取 ε , ε → S \varepsilon , \varepsilon \to S ε,εS 指令 , 读取 ε \varepsilon ε 字符后 , ε → S \varepsilon \to S εS 指的是在栈上的操作 , 从栈内拿走 ε \varepsilon ε , ε \varepsilon ε 是空字符 , 相当于不用拿 , 并将 S S S 字符放入栈 , 相当于使用 S S S 替换 栈内 空字符 ε \varepsilon ε ,

    S S S 字符的作用 : 下推自动机是无法识别栈底的 , S S S 作用是辅助下推自动机识别栈底元素 , 当下推自动机读取到 S S S 时 , 就知道已经读取到栈底了 ;

    开始状态 读取字符 操作 ε , ε → S \varepsilon , \varepsilon \to S ε,εS , 最终向栈中放入了字符 S S S ;

    状态跳转 : 此时 自动机状态 跳转到了 q 2 q_2 q2 状态 ;

    在这里插入图片描述


    3 . q 2 q_2 q2 状态 : 读取 0 , ε → 0 0 , \varepsilon \to 0 0,ε0 指令 , 读取到一个 0 0 0 , 从栈内拿走 ε \varepsilon ε , 使用 0 0 0 替换 ε \varepsilon ε , 并将该替换后的 0 0 0 放入栈中 ; 相当于在栈中 , 使用 0 0 0 替换 ε \varepsilon ε ; 之后依然保持 q 2 q_2 q2 状态不变 ;

    状态跳转 : 下推自动机状态 仍保持 q 2 q_2 q2 状态 ;

    在这里插入图片描述


    4 . q 2 q_2 q2 状态 : 再次读取 0 , ε → 0 0 , \varepsilon \to 0 0,ε0 指令 , 读取到一个 0 0 0 , 从栈内拿走 0 0 0 字符 , 使用 0 0 0 替换 ε \varepsilon ε , 并将该替换后的 0 0 0 放入栈中 ; 之后依然保持 q 2 q_2 q2 状态不变 ;

    状态跳转 : 下推自动机状态 仍保持 q 2 q_2 q2 状态 ;
    在这里插入图片描述


    5 . q 2 q_2 q2 状态 , 读取 1 , 0 → ε 1 , 0 \to \varepsilon 1,0ε 指令 , 读取到一个 1 1 1 , 从栈中拿走一个 0 0 0 , 并将 ε \varepsilon ε 放入栈中 , ε \varepsilon ε 是空字符串 , 从栈内拿取放入 ε \varepsilon ε 栈不变 , 相当于将一个 0 0 0 从栈内拿出 ;

    状态跳转 : 下推自动机状态 从 q 2 q_2 q2 状态跳转到 q 3 q_3 q3 状态 ;

    在这里插入图片描述


    6 . q 3 q_3 q3 状态 : 读取 1 , 0 → ε 1 , 0 \to \varepsilon 1,0ε 指令 , 从栈中 , 拿走一个 0 0 0 , 将 ε \varepsilon ε 放入栈内 , 相当于在栈内使用 ε \varepsilon ε 空字符 替换 0 0 0 , 操作完成后 , 栈内少一个 0 0 0 ;

    状态跳转 : 下推自动机状态 仍保持 q 3 q_3 q3 状态 ;

    在这里插入图片描述


    7 . q 3 q_3 q3 状态 , 读头读取到了最右端 , 所有字符都读取完毕 , 此时不需要读取任何字符 , 读取 ε , S → ε \varepsilon , S \to \varepsilon ε,Sε 指令 , 从栈内拿走 S S S , 将 ε \varepsilon ε 放入栈中 , 跳转到 q 4 q_4 q4 状态 ;

    在这里插入图片描述

    此时 , 栈清空 , 下推自动机停止计算 ;

    q 4 q_4 q4 是个双圈 , 接受状态 , 说明该下推自动机接受该 0011 0011 0011 字符串 ;

    展开全文
  • 下推自动机的半环方法扩展,麻勇军,刘耀军,本文利用半环代数理论讨论了下推自动机,给出了下推自动机在字母表的幂集半环上的定义,特别是在字母表的幂集矩阵半环概念的基础
  • 上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA ) II . 下推自动机 ( PDA ) 三个状态 III . 下推自动机 ( PDA ) q_{start}qstart状态 IV . 下推自动机 ( PDA ) q_{loop}qloop状态 V . 下推自动机 ( PDA ) q_{accept...





    I . 上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )



    上下文无关语法 ( CFG ) :

    S → a T b ∣ b S \to aTb | b SaTbb
    T → T a ∣ ε T \to Ta|\varepsilon TTaε


    将上述 上下文无关语法 ( CFG ) 转为 下推自动机 ;





    II . 下推自动机 ( PDA ) 三个状态



    该 自动机 共包含 3 3 3 个状态 , q s t a r t q_{start} qstart , q l o o p q_{loop} qloop , q a c c e p t q_{accept} qaccept , 最后一个状态是 可接受状态 ;

    在这里插入图片描述





    III . 下推自动机 ( PDA ) q s t a r t q_{start} qstart 状态



    1 . 首先在 栈顶 放入 K K K 字符 , 用于当做栈底的标识 ;


    生成指令 : ε , ε → K \varepsilon , \varepsilon \to K ε,εK ;

    开始状态 q s t a r t q_{start} qstart 状态 , 读取 ε , ε → K \varepsilon , \varepsilon \to K ε,εK 指令 , 读取空字符 , 使用 K K K 替换栈顶的空字符 , 就是将 K K K 放入栈中 ;

    状态跳转 : 之后跳转到 q l o o p q_{loop} qloop 状态 ;


    当前的 下推自动机 ( CFG ) 设计 :
    在这里插入图片描述





    IV . 下推自动机 ( PDA ) q l o o p q_{loop} qloop 状态



    1 . q l o o p q_{loop} qloop 状态下 在栈中模仿 上下文无关语法 ( CFG ) 的规则替换 ;


    上下文无关语法 ( CFG ) :

    S → a T b ∣ b S \to aTb | b SaTbb
    T → T a ∣ ε T \to Ta|\varepsilon TTaε


    2 . 对照上述 上下文无关语法 ( CFG ) , 逐条生成指令 :


    S → a T b S \to aTb SaTb 对应的指令 : ε , S → a T b \varepsilon , S \to aTb ε,SaTb , 读取 ε \varepsilon ε 时 , 使用 a T b aTb aTb 替换栈顶的 S S S ; 即如果栈顶是 S S S , 使用 a T b aTb aTb 替换栈顶的 S S S ;

    S → b S \to b Sb 对应的指令 : ε , S → b \varepsilon , S \to b ε,Sb , 读取 ε \varepsilon ε 时 , 使用 b b b 替换栈顶的 S S S ; 即如果栈顶是 S S S , 使用 b b b 替换栈顶的 S S S ;

    T → T a T \to Ta TTa 对应的指令 : ε , T → T a \varepsilon , T \to Ta ε,TTa , 读取 ε \varepsilon ε 时 , 使用 T a Ta Ta 替换栈顶的 T T T ; 即如果栈顶是 T T T , 使用 T a Ta Ta 替换栈顶的 T T T ;

    T → ε T \to \varepsilon Tε 对应的指令 : ε , T → ε \varepsilon , T \to \varepsilon ε,Tε , 读取 ε \varepsilon ε 时 , 使用 ε \varepsilon ε 替换栈顶的 T T T ; 即如果栈顶是 T T T , 使用 ε \varepsilon ε 替换栈顶的 T T T ;

    如果栈上有终端字符 a a a , 要将栈里的终端字符 a a a 移除 , 对应指令是 a , a → ε a , a \to \varepsilon a,aε , 如果读取到字符 a a a 时 , 从栈顶将字符 a a a 移除 ;

    如果栈上有终端字符 b b b , 要将栈里的终端字符 b b b 移除 , 对应指令是 b , b → ε b , b \to \varepsilon b,bε , 如果读取到字符 b b b 时 , 从栈顶将字符 b b b 移除 ;

    在这里插入图片描述





    V . 下推自动机 ( PDA ) q a c c e p t q_{accept} qaccept 状态



    1 . q a c c e p t q_{accept} qaccept 状态 :


    q l o o p q_{loop} qloop 状态下 , 将栈内的除 K K K 外所有的字符都移除完毕 , 开始向 q a c c e p t q_{accept} qaccept 状态跳转 ;

    此时需要生成指令 ε , K → ε \varepsilon , K \to \varepsilon ε,Kε , 读取 空字符 ε \varepsilon ε , 使用 空字符 ε \varepsilon ε 替换栈顶的 K K K 字符 , 此时栈清空了 ;

    在这里插入图片描述





    VI . 下推自动机 ( PDA ) 指令分解



    1 . 非法指令分解


    上述生成的

    • ε , S → a T b \varepsilon , S \to aTb ε,SaTb
    • ε , T → T a \varepsilon , T \to Ta ε,TTa

    两个指令是不合法的 , 在栈中 , 一个字符 ( 或空字符串 ε \varepsilon ε ) 只能由 一个字符 ( 或空字符串 ε \varepsilon ε ) 替换 ;


    上述不合法的规则 , 多个字符替换栈顶的一个字符 , 需要进行分解操作 ;



    2 . ε , S → a T b \varepsilon , S \to aTb ε,SaTb 指令分解流程 :


    q l o o p q_{loop} qloop 状态 跳转到 新的状态 q l o o p 1 q_{loop1} qloop1 , 跳转读取的指令时 ε , S → b \varepsilon , S \to b ε,Sb , 读取空字符 , 然后使用 b b b 替换栈顶的 S S S 字符 ;

    在这里插入图片描述


    q l o o p 1 q_{loop1} qloop1 状态 跳转到 新的状态 q l o o p 2 q_{loop2} qloop2 , 跳转读取的指令时 ε , ε → T \varepsilon , \varepsilon \to T ε,εT , 读取空字符 , 然后使用 T T T 替换栈顶的 ε \varepsilon ε 字符 , 相当于在栈中放入了 T T T 字符 ;

    在这里插入图片描述

    q l o o p 2 q_{loop2} qloop2 状态 跳转到 原来的状态 q l o o p q_{loop} qloop , 跳转读取的指令时 ε , ε → a \varepsilon , \varepsilon \to a ε,εa , 读取空字符 , 然后使用 a a a 替换栈顶的 ε \varepsilon ε 字符 , 相当于在栈中放入了 a a a 字符 ;

    在这里插入图片描述


    分解 ε , S → a T b \varepsilon , S \to aTb ε,SaTb 后的 3 3 3 个指令 :

    • ε , S → b \varepsilon , S \to b ε,Sb
    • ε , ε → T \varepsilon , \varepsilon \to T ε,εT
    • ε , ε → a \varepsilon , \varepsilon \to a ε,εa

    上述三个指令都是合法的 , 上述 3 3 3 个指令 串联后的效果等价于 ε , S → a T b \varepsilon , S \to aTb ε,SaTb 操作 , 等价于上下文无关语法的 S → a T b S \to aTb SaTb 规则效果 ;



    3 . ε , T → T a \varepsilon , T \to Ta ε,TTa 指令分解流程 :


    q l o o p q_{loop} qloop 状态 跳转到 新的状态 q l o o p 3 q_{loop3} qloop3 , 跳转读取的指令时 ε , S → a \varepsilon , S \to a ε,Sa , 读取空字符 , 然后使用 a a a 替换栈顶的 S S S 字符 ;

    在这里插入图片描述

    q l o o p 3 q_{loop3} qloop3 状态 跳转到 原来的状态 q l o o p q_{loop} qloop , 跳转读取的指令时 ε , ε → T \varepsilon , \varepsilon \to T ε,εT , 读取空字符 , 然后使用 T T T 替换栈顶的 ε \varepsilon ε 字符 , 相当于在栈中放入了 T T T 字符 ;

    在这里插入图片描述


    分解 ε , T → T a \varepsilon , T \to Ta ε,TTa 后的 2 2 2 个指令 :

    • ε , S → a \varepsilon , S \to a ε,Sa
    • ε , ε → T \varepsilon , \varepsilon \to T ε,εT

    上述 2 2 2 个指令都是合法的 , 上述 2 2 2 个指令 串联后的效果等价于 ε , T → T a \varepsilon , T \to Ta ε,TTa 指令 , 等价于上下文无关语法的 T → T a T \to Ta TTa 规则效果 ;





    VII . 最终转换成的 下推自动机 ( PDA ) 结果



    最终的 上下文无关语法 ( CFG ) 转为的 下推自动机 ( PDA ) 样式 :

    在这里插入图片描述

    上下文无关语法 ( CFG ) 与 下推自动机 ( PDA ) 是等价的 , 给定一个 下推自动机 ( PDA ) , 构造 上下文无关语法 ( CFG ) , 该语法生成的语言 , 就是该 下推自动机 ( PDA ) 所认识的语言 ;

    展开全文
  • 形式语言自动机——上下文无关文法与下推自动机四PPT学习教案.pptx
  • 为不同类型的自动机定义应用实例:有限状态机、下推自动机和队列自动机。 我使用该库来编写解析器:队列自动机应用程序将使用广度优先搜索策略专门解析上下文无关语法,也可用于模拟并行运行的计算。
  • PDA下推自动机c++程序

    2009-11-09 19:41:39
    Pushdown Automata(PDA)下推自动机的c++程序。
  • 该文引入1墨水点2方向交替式下推自动机,它是1个具有额外能力的2方向交替式下推自动机,能够用1个墨水点在输入带上标记出最多1个单元格。对具有1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系...
  • 匹配器 Code Puzzle 中特殊括号的字符串匹配器。 === 匹配算法 首先,我使用正则表达式和 if else 来制作这个应用... 确定性下推自动机可以识别所有确定性上下文无关语言,而非确定性下推自动机可以识别所有上下文无
  • 挺好的,有助于理解下推自动机,以及极其模拟过称。
  • 确定下推自动机、非确定下推自动机(Pushdown Automaton) 对任何CFA都能找到一种具有特有形式 的等价CFG(Context-Free Grammar) 上下文无关文法对应的识别器是下推自动机。 确定的下推自动机对应于上下文无关...
  • 一、上下文无关文法 CFG 转为下推自动机 PDA 流程、 二、上下文无关文法 CFG 转为下推自动机 PDA 示例 2
  • 一、上下文无关文法 CFG 转为下推自动机 PDA 流程、 二、上下文无关文法 CFG 转为下推自动机 PDA 示例 1
  • 自动机是一个Python 3库,它实现了有限自动机,下推自动机和图灵机的结构和算法。 该库要求使用Python 3.5或更高版本。 非常感谢和为该项目做出了宝贵的贡献! 迁移至v4 如果您希望从旧版本迁移到Automata v4,请...
  • 下推自动机(PDA)在程序设计中的应用 (一)下推自动机简介(Pushdown Automation) 下推自动机﹙PDA﹚是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态自动机复杂:除了有限状态组成...
  • 计算理论导引实验二:构造下推自动机实验描述形式化定义状态图描述问题解决状态转移关系类键盘录入及逻辑处理类测试运行输入ccabcbbbca时输入为cbabcac时代码下载及说明代码下载说明 关于下推自动机的概念,可以从书...
  • 实验题目:构造下推自动机 一、实验题目解答 对解题的整体思路、过程进行提炼和描述,包括算法描述、程序结构、主要变量 说明、设计技巧、调试情况、运行结果、心得体会等。 二、NFA正则表达式 1.形式化定义 根据...
  • JSON_checker 是一个下推自动机,能够快速判断一个JSON文本的语法是否正确
  • 下推自动机(PDA)实现,用于验证Java中的计算器语法。 例如2*(3/(4+5+6))有效,或1+(2*3无效)。 介绍 什么是PDA? 下推自动机(PDA)是涉及堆栈的一种自动机。 PDA比状态机更强大。 这个项目是关于什么的? 在...
  • 文章目录上下文无关文法上下文无关文法的定义上下文无关文法举例上下文无关文法的二义性(Ambiguity)下推自动机下推自动机的定义下推自动机举例判断一个字符串是否属于 PDA 表示的语言(是不是 PDA 可以 accept 的...
  • Lua语言的双向下推自动机 凯文·史蒂文斯(Kevin Stevens) 荣誉学院的Barrett提出的部分满足毕业要求的论文 巴雷特荣誉论文委员会于2020年5月批准: 董事严Shoshitaishvili 王若愚 亚利桑那州立大学 2020年5月 ...
  • 下推自动机 正则语言 泵引理

    千次阅读 2016-03-09 05:44:29
    下推自动机动画演示: L = {0^n1^n| n ≥ 1} https://www.youtube.com/watch?v=Iz9x2UOt0xQ 自动机原理,体验印度英语: https://www.youtube.com/playlist?list=PLEbnTDJUr_IdM___FmDFBJBz0zCsOFxfK 其中41-45 ...
  • 一、下推自动机(pushdown automata) 下推自动机是一个带栈的自动机,用于信息暂存和比对。非确定型下推自动机由一个七元组定义: [例]针对语言 L={w∈{a,b}*:na(w)=nb(w)}构造一个npda。 在处理baab过程...
  • 象征性的下推自动机及其所有算法 符号流式串换能器 符号有限换能器(您可以在此处阅读有关SFT的更多信息: : ) 区间特征理论 安装前 如果要从运行基准测试,使用以下说明 克隆后运行: git子模块初始化 git子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,234
精华内容 1,693
关键字:

下推自动机