6

我如何在字母表 {a, b} 上找到以下正则表达式的语言？

aUb*
(ab*Uc)
ab*Ubc*
a*bc*Uac

编辑：在我疯狂地投票之前，如果有人能向我展示解决这些问题的步骤，而不仅仅是解决方案，我将不胜感激。甚至可能会带我走过一个，这样我就可以自己做剩下的事情了。

谢谢！

4

3 回答 3

6

编辑：简短的回答，*意味着几乎所有正则表达式/语法中的“零次或多次重复”，包括 perl5 和 RFC 5234。 *通常比串联和交替绑定更紧密。

你说你想要一种超越字母表（a，b）的语言，但在你的表达中包含cand 。U我将假设您希望在字母表 (a, b, c) 上使用像 BNF 这样的形式的语言语法，给定一个正则表达式 whereU是一个低优先级联合运算符，类似于|perl re。

在这种情况下，

a|b*

等价于 BNF：

L := a
   | <M>
M := epsilon
   | b <M>

*运算符表示零个或多个，因此第一个子句是M基本情况，第二个子句是M包含终端的递归使用b。

L 只是单个终端a或非终端M。

(ab*|c)

L ::= a <M>
    | c
M ::= epsilon
    | b <M>

M 的推导方式与上述相同，其余的不言自明。

ab*|bc*

L ::= a <M>
    | b <N>
M ::= epsilon
    | b <M>
N ::= epsilon
    | c <N>

N 的推导方式与上述 M 相同。

a*bc*|ac

大多数正则表达式语言中的*绑定比串联更紧密，所以这与

(a*b(c*))|(ac)

归结为

L ::= <M> b <N>
    | a c
M ::= epsilon
    | a <M>
N ::= epsilon
    | c <N>

一般来说，要将正则表达式转换为 BNF，您只需在正则表达式中使用邻接来表示 BNF 中的邻接，U或者|在正则表达式|中使用 BNF 中的邻接。

如果你定义一个非终结符<X> ::= x，那么你可以x*这样处理：

L ::= epsilon
    | <X> <L>

使用相同的非终端<X> ::= x，您可以x+这样处理：

L ::= <X>
    | <L> <X>

这让你得到了重复运算符*和+留下?​​ . x?简直就是

L ::= epsilon
    | <X>
于 2011-10-03T04:13:14.140 回答
2

尽管 Mike 给出了生成由正则表达式表示的语言的语法，但您的作业要求语言本身。因为您正在处理正则表达式，所以您的答案必须是正则集。

回想一下字母表上正则集的定义：

Let Σ be an alphabet. The class of regular sets over Σ is the smallest class
containing ∅, {λ}, and {a}, for all a ∈ Σ, and closed under union, concatenation,
and Kleene star.

现在回想一下字母表上正则表达式的定义：

Let Σ be an alphabet. The class of regular expressions over Σ is the smallest
class containing ∅, λ, and a, for all a ∈ Σ, and closed under union, concat-
enation, and Kleene star.

因此，翻译应该是直截了当的。事实上，它包括在每个字母周围插入大括号！例如：

a ∪ b*  denotes {a} ∪ {b}*
ab* ∪ c denotes {a}{b}* ∪ {c}
...

如果您想用集合构建器表示法表达每个正则表达式的语言，您可以恢复到对正则集合的操作的定义。记起：

Let A and B be regular sets. Then
   1  A ∪ B = {x : x ∈ A ∨ x ∈ B}
   2. AB    = {xy : x ∈ A ∧ y ∈ B}
   3. A*    = ∪[i = 0 -> ∞]A^i

通过替换常规集操作的定义，可以将常规集转换为集构建器符号。为了避免引入嵌套的集合生成器符号，我将相等与串联的定义结合使用来表达常规集合的串联。

{a} ∪ {b}*    = {w : w ∈ {a} ∨ w ∈ ∪[i = 0 -> ∞]{b}^i}
{a}{b}* ∪ {c} = {w : (w = xy ∧ (x ∈ {a} ∧ y ∈ ∪[i = 0 -> ∞]{b}^i)) ∨ w ∈ {c}}
...

您现在应该能够毫无困难地找到其余表达式表示的语言。

于 2011-10-04T07:43:20.077 回答
1

如果您知道星号、联合和串联的含义，这些应该很容易。第一个是工会b星。根据操作顺序，这意味着联合（b 星）。联合表示左侧语言中的任何内容或右侧语言中的任何内容。a 表示由长度为一的字符串 a 组成的语言；b 星表示由任何字符串组成的语言，该字符串由零个或多个 b 符号组成，仅此而已。所以这种语言是{empty, a, b, bb, bbb, bbbb, ...}。在第二个中，ab* 表示由 a 后跟零个或多个 b 符号组成的所有字符串。先做星号，然后是连接，然后是联合，遵守给定的显式括号。

于 2011-10-03T04:20:09.427 回答