形式语⾔与编译五正则语⾔的三个性质
⾮正则语⾔
NFA、ε−NFA⾯向⼈构造系统
DFA⾯向机器构造系统
⾃动机理论⾮常完美！！
⾃动机的表述有纯数学形式的五元组形式(⽤来科学定义以及证明)、状态转移图(⽤来直观理解，也是⼀种数学⼯具)、状态转移表(编程⽤，⽤来定义数据结构⽐较好，⾯向计算机存储)
乔姆斯基把语⾔进⾏分类，0型、1型、2型、3型
每⼀种语⾔都有对应的处理装置：⽐如正则语⾔——有穷⾃动机（正则表达式也⾏，以代数⾓度）、上下⽂⽆关语⾔——下推⾃动机、 0型语⾔——图灵机
现阶段我们还是研究正则语⾔为主
接下来以研究正则语⾔（3型）的性质为主。
⾸先要讲额就是正则语⾔是有局限性的！！(⽽这个局限性就让我们在以后有发现上下⽂⽆关语⾔（2型）、上下⽂有关（1型语⾔）、0型语⾔的兴趣) 也就是其描述能⼒有限！！但是也要知道即使是更强的上下⽂⽆关⽂法，其描述能⼒也是受限的。
注意：这⾥我们衡量语⾔的描述能⼒，⽐较抽象，不好说。所以我们以语⾔对应处理装置的⾃动机处理能⼒为标准衡量语⾔描述能⼒
也就是0型语⾔对应的图灵机处理能⼒是最强的！
正则语⾔性质：
有限性
封闭性
判定性
有限性：
现在我们来看看，什么语⾔不能被正则语⾔对应的有限⾃动机处理
上⾯的B、C不到正则表达式，也就不到有限⾃动机(如果是正则语⾔，必然有它的处理装置——正则表达式或者DFA)
D能到DFA。。
也就是有些语⾔不是正则语⾔
DFA中的F指的是有限状态。⽽正则语⾔可能是有限的、也可能是⽆限的。我们的有限⾃动机理论厉害之处就是⽤有限的状态竟然可以描述多达⽆穷的语⾔。可怕！！ Nb！
有穷的描述来处理⽆穷的东西，太屌了！！
抽屉原理呗！
也就是串不能过长，串太长就不能满⾜正则语⾔了(参考泵定理)
封闭性
如果有⼀个正则语⾔，那么在这个正则语⾔经过特定规定运算(并、连接、Kleene闭包)后仍然是正则的
在交、逆、同态、逆同态下也是封闭的
以数学⽅⾯的正则表达式⽅向证明：
有时候，⽤补语⾔的正则表达式我们可以分析出，但是类别太多，巨⿇烦。换思路：⾃动机。我们可以试着写出补语⾔的DFA，嘻嘻
上⾯对⾃动机求补，只能是DFA，不能对NFA求补
要是求NFA的补，先把NFA变成DFA，再对DFA求补
还要⼀点要记住，正则表达式不能直接转化为DFA，他要通过NFA过渡，准确的说是ε -NFA。
逆也封闭，证明略
除此之外，还有幂次⽅、同态、逆同态也都是封闭的。证明略
duplicate运算不封闭
判定性
上⾯三个问题输进来，判断是否
w是否属于L
L是否是空
L有穷或者⽆穷
可以判定语⾔是否是有穷还是⽆穷(因为有限⾃动机的有限指的是状态数有限，语⾔集合有可能有穷，也有可能⽆穷)
特征正则化的作用给出正则语⾔，根据正则语⾔可以写出⾃动机，然后对⾃动机做如下删减，可以判定该⾃动机(或者说该正则语⾔)是有穷还是⽆穷。。Processing math: 100%

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。