自己创业做网站极速云建站
NFA&DFA
在正规式的等价证明可以借助正规集，也可以通过有限自动机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开头的奇数文法
例：上下文无关文法描述正规表达式
基本概念：
① 句子仅含有终结符，是特殊的句型；
②文法开始符号一定是句型；
③文法产生的句子的全体为文法产生的语言；(标识符、表达式i+i*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型文法左端产生式要求单个非终结符(单非)；