编译原理 正则语言 二义文法 急~

Question

什么样的叫正则语言？什么样的叫二义文法？
越详细越好 在线等
如果给定一个文法 有没有直观一点的方法判断它所表示的语言是不是正则语言？
例如： S -> AP | PB
P -> aPb | ε
A -> Aa | a
B -> Bb | b
这个怎么判断？

Answer 1

这个没有一个好老师，自己咬文嚼字看懂是很累的
二义性文法

【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。

二义性文法会引起歧义，应尽量避免之！
G(E)：E -> E+E | E*E | (E) | i
这两种展开
E E
E + E E * E
i E * E E + E i
i i i i

都可以表示i+i*i

所以;文法具有二义性。

Answer 2

正规语言又称正则语言是满足下述相互等价的一组条件的一类形式语言：
可以被确定有限状态自动机识别；
可以被非确定有限状态自动机识别；
可以被只读图灵机识别；
可以用正则表达式描述；
可以用正则文法生成。
可以用前缀文法生成。
例子

所有的有限语言都是正则的。
字母表 {a, b} 上包含偶数个 a 的所有字串构成的语言是正则的。
字母表 {a, b} 上取若干个 a 后紧跟若干个 b形式的所有字串构成的语言是正则的。
定义

在字母表集合 ∑上的正规语言定义如下：
空集合Ø是正规语言
只包含一个空字串的语言{ε}是正规语言
对所有，{a}是正规语言
若A, B是正规语言，则(kleene星号)都是正规语言
除此之外都不是正规语言
如果一个语言不是正规语言，它需要一个内存至少是Ω(log log n)的自动机才能辨认。换句话说，DSPACE(o(log log n))等于所有正规语言的集合。实际上，大部份的非正规语言需要至少O(log n)的空间。
封闭性质

这里语言的运算参见条目形式语言。
正则语言的交、并、差、补运算得到的语言仍然是正则语言；
两个正则语言连接（把第一个语言的所有字串同第二个语言的所有字串连接起来）后得到的语言仍然是正则语言；
正则语言闭包运算后得到的语言仍然是正则语言；
正则语言的每个字串转置后得到的语言仍然是正则语言；
正则语言被任意语言的字符串商（左商或右商)后得到的语言仍然是正则语言。
正则语言字符串代换后得到的语言仍然是正则语言。
与正则语言字符串同态或逆同态的语言仍然是正则语言。本回答被提问者采纳