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

Question

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

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

编辑:在我疯狂地投票之前,如果有人能告诉我解决这些问题的步骤,我会很感激,而不仅仅是解决方案.也许甚至可以让我走过一条路,所以我可以独自完成其余的工作.

谢谢!

Answer 1

编辑:简短回答,*意味着几乎所有正则表达式/语法语法中的"零次或多次重复"包括perl5和RFC 5234. *通常比连接和交替更紧密地绑定.

你说你要过字母表语言(A,B),但包括c和U在你的表情.我假设你想要一个像BNF那样的字母表中的语言语法(a,b,c)给定一个正则表达式,其中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那么您可以x*这样处理:

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

使用相同的非终结符,<X> ::= x您可以x+这样处理:

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

这会让你重复运算符*并+离开?. x?很简单

L ::= epsilon
    | <X>