如何从正则表达式中找到语言？

Question

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

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

编辑：在我疯狂地被否决之前，如果有人能向我展示解决这些问题的步骤，而不仅仅是解决方案，我将不胜感激。也许甚至可以引导我完成其中一个，这样我就可以自己完成剩下的事情。

谢谢！

Answer 1

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

您说您想要一种基于字母表 (a, b) 的语言，但在表达式中包含 c 和 U 。我假设您想要一个字母表（a、b、c）上的语言语法，其形式类似于 BNF 给定正则表达式，其中 U 是低优先级联合运算符，类似于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*：

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

使用相同的非终结符 ; ::= x 那么你可以这样处理 x+：

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

这会得到重复运算符 * 和 + ，剩下 ？。 x? 很简单

L ::= epsilon
    | <X>

Answer 2

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

Answer 3

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

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

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}}
...

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