做网站收费标,临沂手机建站模板,html怎么添加图片,网站虚拟空间购买NFADFA
在正规式的等价证明可以借助正规集#xff0c;也可以通过有限自动机DFA来证明等价#xff0c;以下例题是针对DFA证明正规式的等价#xff0c;主要步骤是①NFA#xff1b;②状态转换表#xff1b; ③状态转换矩阵#xff1b; ④化简DFA#xff1b; 文法和语… NFADFA
在正规式的等价证明可以借助正规集也可以通过有限自动机DFA来证明等价以下例题是针对DFA证明正规式的等价主要步骤是①NFA②状态转换表 ③状态转换矩阵 ④化简DFA 文法和语言 文法通常表示成 四元组 G[S] ( V T V N S ξ): (1) V T 为终结符号集 这是一个非空有限集它的每个元素 称为 终结符号 。 (2) V N 为非终结符号集 它也是一个非空有限集每个元 素称为 非终结符号 且有 V T ∩V N Φ (3) S 为文法开始符 是一个特殊的非终结符号即 S ∈ V N (4) ξ /ksi/ 是产生式的非空有限集 其中每个产生式 ( 或称规 则 ) 是一序偶 (α β) 通常写作 α → β 或 α :: β α 、 β 是由终结符和非终结 符组成的符号串 α ∈ (V T ∪ V N ) 且至少有一个非终结符 而 β ∈ (V T ∪ V N ) * 。 例产生标识符的文法 例奇数集合不允许出现以0开头的奇数文法 例上下文无关文法描述正规表达式 基本概念
① 句子仅含有终结符是特殊的句型
②文法开始符号一定是句型
③文法产生的句子的全体为文法产生的语言(标识符、表达式ii*i都是语言都由非终结符组成)
④文法确定则语言一定确定反之不一定可以由语言唯一确定文法
⑤文法产生语言的过程中必须经过‘’次推导(至少进行一次推导)
形式语言分类
(1) 0型文法与语言
对应图灵机
文法G[S]的每一个产生式 都有 α-β
α 作为产生式左端至少有一个非终结符
β 作为产生式右端不做要求(甚至可以为空)
(2) 1型文法与语言
线性界限自动机自然语言
在0型文法的基础上要求文法产生式左端的长度要 小于等于 右端的长度 (3) 2型文法与语言
对应下推自动机程序设计语言
文法G[S]的每一个产生式 都有 A-α
A∈非终结符
α∈(终结符和非终结符的闭包)
(4) 3型文法与语言
对应有限自动机
文法G[S]的每一个产生式 都有 A-α 或者 A-αB[右线性] 或者 A-Bα[左线性]
A∈非终结符
α∈(终结符的闭包)
关系和区别
① 1-3型文法属于 0 型文法
② 2型 和 3型 文法不一定属于 1型 文法
③ 1型文法 不允许有形如“”A-ε”, 2、3型文法允许
④ 0、1型文法左边产生式 可以含有终结符或者两个以上终结符 2、3型文法左端产生式要求单个非终结符(单非)
