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

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

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

• Φ 是一个正则表达式，表示空集。

• ε 是一个正则表达式，表示集合 { ε}，称为空串。

• 对于 Σ 中的每个 'a'，'a' 是一个正则表达式，表示集合 {a}。

• 如果 r 和 s 表示语言的正则表达式。

• L1 和 l2 分别然后，

• r+s 等价于 L1 U L2 union

• rs 等价于 L1L2 连接

• r* 等价于 L1* 闭包

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

问题一

在集合 l 上写出接受 a 的所有组合的语言的正则表达式：= {a}

解决方案

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

R = a*

那是克林闭包了。

问题二

编写语言的正则表达式，在集合 l 上接受除空字符串之外的所有 a 组合：= {a}

解决方案

必须为语言 L = {a, aa,aaa, ....} 构建正则表达式

这个集合表示没有空字符串。因此，我们可以将正则表达式表示如下 -

R = a+

问题三

将语言 L 的正则表达式写在 l: = {O, l} 上，使得所有字符串不包含子字符串 01。

解决方案

语言如下 -

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

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

R = (1* O*)

问题四

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

解决方案

常规期望将是：R = (011+ 1)*