自动机正则表达式的例子

范例1：

在∑ = {0，1}上，为该语言编写一个正则表达式，以接受所有以1开头并以0结尾的所有字符串。

解：

在正则表达式中，第一个符号应为1，最后一个符号应为0。如下：

R = 1 (0+1)* 0

范例2：

为该语言以a开头和结尾并且之间包含b的任何组合的语言编写正则表达式。

解：

正则表达式为：

R = a b* b

范例3：

为以a开头但不包含连续b的语言编写正则表达式。

解决方案：必须为该语言构建正则表达式：

L = {a, aba, aab, aba, aaa, abab, .....}

上述语言的正则表达式为：

R = {a + ab}*

范例4：

为接受所有字符串的语言编写正则表达式，在该字符串中，任意数量的a后跟任意数量的b后跟任意数量的c。

解决方案：我们知道，任意数量的a意味着a *任意数量的b意味着b *，任意数量的c意味着c *。由于如问题陈述中所述，b出现在a后面，而c出现在b后面。因此正则表达式可能是：

R = a* b* c*

范例5：

在具有等于字符串长度的∑ = {0}上编写该语言的正则表达式。

解：

必须为该语言构建正则表达式：

L = {ε, 00, 0000, 000000, ......}

上述语言的正则表达式为：

R = (00)*

范例6：

为具有字符串的语言编写正则表达式，该字符串应至少为1且至少为1。

解：

正则表达式为：

R = [(0 + 1)* 0 (0 + 1)* 1 (0 + 1)*] + [(0 + 1)* 1 (0 + 1)* 0 (0 + 1)*]

范例7：

描述以下正则表达式表示的语言

r.e. = (b* (aaa)* b*)*

解：

可以通过查找正则表达式的含义来预测该语言。我们首先将正则表达式拆分为：

回覆。 =（b的任何组合）（aaa）*（b的任何组合）

L = {语言由a组成的三元组字符串组成，b的数量不受限制}

范例8：

在∑ = {0，1}上编写语言L的正则表达式，以使所有字符串都不包含子字符串01。

解：

语言如下：

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

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

R = (1* 0*)

范例9：

用包含{0，1}上的字符串的语言编写正则表达式，其中在任意两次出现的0之间，在两次两次出现的1之间，至少有两次出现1。

解决方案：两次出现的0之间至少有两个1可以表示为（0111 * 0）*。

类似地，如果不出现0，则也允许任何数量的1。因此，所需语言为：

R = (1 + (0111*0))*

范例10：

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

解：

正常的期望是：

R = (011 + 1)*