根据用户给定的语言构建正则表达式。

正则表达式是一种用于描述语言并被有限自动机接受的语言。正则表达式是表示任何语言的最有效方法。设 Σ 为表示输入集的字母表。

Σ 上的正则表达式可以定义如下：

• Φ 是一个正则表达式，表示空集。
• ε 是一个正则表达式，表示集合 { ε}，称为空字符串。
• 对于 Σ 中的每个 ‘a’，‘a’ 是一个正则表达式，表示集合 {a}。
• 如果 r 和 s 是表示语言的正则表达式。
  • 分别为 L1 和 L2，则：
  • r+s 等价于 L1 U L2（并集）
  • rs 等价于 L1L2（连接）
  • r* 等价于 L1*（闭包）

r* 被称为 Kleen 闭包或闭包，表示 r 出现无限次。

问题 1

编写接受集合 l: = {a} 中所有 a 的组合的语言的正则表达式。

解答

所有 a 的组合意味着 a 可以出现零次、一次、两次等等。如果 a 出现零次，则表示空字符串。也就是说，我们期望集合 {E, a, aa, aaa, ....}。因此，我们为其给出如下正则表达式：

R = a*

即 a 的 Kleen 闭包。

问题 2

编写接受集合 l: = {a} 中所有 a 的组合（除了空字符串）的语言的正则表达式。

解答

需要为语言 L = {a, aa,aaa, ....} 构建正则表达式。

此集合表示没有空字符串。因此，我们可以将正则表达式表示为：

R = a+

问题 3

编写集合 l: = {0, 1} 上的语言 L 的正则表达式，使得所有字符串都不包含子字符串 01。

解答

语言如下：

L = {E, 0, 1,00, 11,10,100,.....}

上述语言的正则表达式如下：

R = (1* 0*)

问题 4

编写包含每个 0 后紧跟 11 的字符串的语言的正则表达式。

解答

正则表达式将是：R = (011+ 1)*

Bhanu Priya

更新于: 2021年6月12日

2K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

开始学习