正则表达式、正则语法和正则语言
正如乔姆斯基层次中所讨论的，正则语言是最受限制的语言类型，并且被有限自动机所接受。
正则表达式 正则表达式用于表示正则语言。表达式是正则的，如果:
- ɸ是正则语言ɸ.的正则表达式
- ɛ是正则语言{ɛ}.的正则表达式
- 如果 a∈σ(σ代表输入字母表，则 a 是带有语言{a}的正则表达式。
- 如果 a 和 b 是正则表达式，a + b 也是带有语言{a，b}的正则表达式。
- 如果 a 和 b 是正则表达式，ab(a 和 b 的连接)也是正则的。
-
If a is regular expression, a* (0 or more times a) is also regular.
正则表达式 常规语言 一套 vovels (a ∪ e ∪ i ∪ o ∪ u) {a，e，I，o，u} a 后跟 0 或更多 b (甲乙 * ) {a、ab、abb、abb、abb、abb、…。}表示 任何数量的元音后跟任何数量的辅音 v 。c (其中 v-元音和 c-辅音) { ε，a，aou，爱欧，b，abcd…..}其中ε代表空字符串(在 0 元音和 o 辅音的情况下) 规则语法:如果一个语法有形式规则 A - > a 或 A - > aB 或 A - > ɛ，其中ɛ是一个特殊的符号称为空。
正则语言:如果一种语言可以用正则表达式来表达，那么它就是正则的。
正则语言的闭包属性 并集:如果 L1 和 L2 是两种正则语言，那么它们的并集 L1 ∪ L2 也会是正则的。比如 L1 = { an| n≥0 } L2 = { bn| n≥0 } L3 = L1∪L2 = { an∪bn| n≥0 }也是有规律的。 交集:如果 L1 和 L2 是两种正则语言，它们的交集 L1∪L2 也会是正则的。例如， L1 = { ambn| n≥0 且 m≥0 } L2 = { ambn】∪bnam| n≥0 且 m≥0 } L3 = L1∪L2 = { ambn 串联:如果 L1 和 L2 是两种正规语言，它们的串联 L1。L2 也是常客。例如， L1 = { an| n≥0 } L2 = { bn| n≥0 } L3 = L1。L2 = {a m 。b n | m ≥ 0 且 n ≥ 0}也是有规律的。 克莱尼闭包:如果 L1 是正则语言，它的克莱尼闭包 L1也会是正则的。比如 L1 =(a∪b) L1 * =(a∪b) T63】补语:如果 L(G)是正则语言，那么它的补语 L’(G)也会是正则的。一种语言的补语可以通过从所有可能的字符串中减去 L(G)中的字符串来找到。例如， L(G)= { an| n>3 } L '(G)= { an| n<= 3 }
注意:两个正则表达式如果生成的语言相同，则是等价的。例如，(a+b)和(a+b)生成相同的语言。由(a+b)生成的每个字符串也由(a+b)生成，反之亦然。
如何解决正则表达式和正则语言上的问题？
问题 1 : 正则表达式描述了字母表{0，1}上的以下哪种语言？ (0+1)0(0+1)0(0+1) (A)包含子串 00 的所有字符串的集合。 (B)包含最多两个 0 的所有字符串的集合。 (C)包含至少两个 0 的所有字符串的集合。 (D)以 0 或 1 开始和结束的所有字符串的集合。 解决方案:*选项 A 说必须有子串 00。但是 10101 也是语言的一部分，但是它不包含 00 作为子串。所以这不是正确的选择。 选项 B 表示最多可以有两个 0，但是 00000 也是语言的一部分。所以这不是正确的选择。 选项 C 表示必须包含至少两个 0。在正则表达式中，有两个 0。所以这是正确的选择。 选项 D 表示它包含所有以 0 或 1 开头和结尾的字符串。但是它可以生成以 0 开头、以 1 结尾的字符串，反之亦然。所以是不正确的。
问题 2 : 下列哪种语言是由给定的语法生成的？ s->as | bs |∊ (a){ anbm| n，m≥0 } (b){ w∑{ a，b}* | w 具有相等数量的 a 和 b } (c){ an| n≥0 }∞{ bn| n≥0 }
解决方案:选项(A)说它会有 0 个或更多 A 后跟 0 个或更多 b，但是 S - > bS = > baS = > ba 也是语言的一部分。所以(A)是不正确的。 选项(B)表示 a 和 B 的数量相等。但是 S - > bS = > b 也是语言的一部分。所以(B)是不正确的。 选项(C)表示要么有 0 个或更多的 a，要么有 0 个或更多的 b，或者 a 后面跟着 b。但如选项(A)所示，“把”也是语言的一部分。所以(C)是不正确的。 选项(D)表示它可以有任意数量的 a 和任意数量的 b。所以(D)是正确的。
问题 3 : 正则表达式 0(10)表示与 (A)(1 * 0) 1 * (B)0+(0+10) (C)(0+1) 10(0+1) (D)这些都不是 解决方案:如果它们生成的语言相同，那么两个正则表达式是等价的。 选项(A)可以生成 0(10)生成的所有字符串。所以它们是等价的。 选项(B)字符串 null 不能由给定语言生成，但 0(10)可以。所以它们不是等价的。 选项(C)将有 10 作为子串，但 0(10)可能有也可能没有。所以它们不是等价的。
问题 4 : 具有输入字母 A 和 B 的语言的正则表达式，其中两个 A 不在一起: (A)(B+ab)+(B+ab) A (B)A(B+ba)+(B+ba) (C)两个选项(A)和(B) (D)以上都没有
解决方案: 选项(C)说明选项(A)和(B)都是所述问题的正确正则表达式。 问题中的语言可以表示为 L = {&ε、a、b、bb、ab、aba、ba、bab、baba、abab、…}。
在选项(A)中，“ab”被认为是找出所需正则表达式的构造块。(b + ab)涵盖所有以“b”结尾的字符串生成情况。(b + ab)a 涵盖了所有以 a 结尾的字符串生成情况。
对选项(B)应用类似的逻辑，我们可以看到，正则表达式是以“ba”为构建块导出的，它涵盖了以 a 开头和以 B 开头的字符串的所有情况。
本文由 Sonal Tuteja 撰写。
发现有不正确的地方请写评论，或者想分享更多以上讨论话题的信息
版权属于：月萌API www.moonapi.com，转载请注明出处
