正则表达式、正则语法和正则语言

如中所述 乔姆斯基等级制度 正则语言是最受限制的语言类型，被有限自动机所接受。 正则表达式 正则表达式用于表示正则语言。如果满足以下条件，则表达式为正则表达式：

• ɸ是正则语言ɸ的正则表达式。
• ɛ是正则语言{ɛ}的正则表达式。
• 如果∈ ∑（代表 输入字母表 )，a是语言{a}的正则表达式。
• 如果a和b是正则表达式，那么a+b也是语言为{a，b}的正则表达式。
• 如果a和b是正则表达式，那么ab（a和b的串联）也是正则表达式。
• 如果a是正则表达式，则a*（0或更多乘以a）也是正则表达式。
  

  	正则表达式	常规语言
  一套vovels	（a）∪ E∪ 我∪ o∪ u）	{a，e，i，o，u}
  a后跟0或更多b	（a.b.） * )	{a，ab，abb，abbb，…]
  任意数量的元音后跟任意数量的辅音	五、 * C * （其中v为元音，c为辅音）	{ε，a，aou，aiou，b，abcd….}其中ε表示空字符串（在0个元音和o个辅音的情况下）

  常规语法： 如果语法规则的形式是A->A或A->aB或A->ɛ，其中ɛ是一个称为NULL的特殊符号，那么它就是正则的。 常规语言： 如果一种语言可以用正则表达式来表达，那么它就是正则的。 正则语言的闭包性质 工会： 如果L1和L2是两种正则语言，那么它们的联合就是L1∪ L2也将是常规的。例如，L1={a ^N |n≥ 0}和L2={b ^N |n≥ 0} L3=L1∪ L2={a ^N ∪ B ^N |n≥ 0}也是规则的。 交叉： 如果L1和L2是两种正则语言，那么它们的交集是L1∩ L2也将是常规的。例如 L1={a ^M B ⁿ |n≥ 0和m≥ 0}和L2={a ^M B ^N ∪ B ^N 一 ^M |n≥ 0和m≥ 0} L3=L1∩ L2={a ^M b ^N |n≥ 0和m≥ 0}也是规则的。 连接： 如果L1和L2是两种正则语言，则它们的连接为L1。L2也将是常规的。例如 L1={a ^N |n≥ 0}和L2={b ^N |n≥ 0} L3=L1。L2={a ^M B ^N |m≥ 0和n≥ 0}也是规则的。 Kleene闭包： 如果L1是一种正则语言，那么它的Kleene闭包L1*也将是正则的。例如 L1=（a）∪ b） L1*=（a）∪ b）* 补充： 如果L（G）是正则语言，它的补语L’（G）也将是正则的。一种语言的补码可以通过从所有可能的字符串中减去L（G）中的字符串来找到。例如， L（G）={a ^N |n>3} L’（G）={a ^N |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） {A ^N B ^M |n，m≥ 0} （B） {w∈ {a，b}*|w有相等数量的a和b} （C） {a ^N |n≥ 0} ∪ {b ^N |n≥ 0} ∪ {a ^N B ^N |n≥ 0} （D） {a，b}*

  解决方案： 选项（A）表示它将有0个或更多的A，后面跟着0个或更多的b。但是S->bS=>baS=>ba也是语言的一部分。所以（A）是不正确的。 选项（B）表示a和B的数量相等，但s->B=>B也是语言的一部分。所以（B）是不正确的。 选项（C）表示它将有0个或多个a，或0个或多个b，或a后跟b。但如选项（a）所示，ba也是语言的一部分。所以（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={&epsilon，a，b，bb，ab，aba，ba，bab，baba，abab，…}。

  在选项（A）中，“ab”被认为是找出所需正则表达式的构造块。（b+ab）*涵盖所有以“b”结尾的字符串。（b+ab）*a涵盖了以a结尾的字符串的所有情况。

  对选项（B）应用类似的逻辑，我们可以看到正则表达式是以“ba”为构建块推导出来的，它涵盖了以a开头和以B开头的字符串的所有情况。

  本文由Sonal Tuteja撰稿。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论