正则表达式：数学与编程

是否有人，这是非常熟悉数学的正则表达式理论相符这两个正则表达式在语义上是相同的？

只是为了澄清一下，问题标题的“与程序化”部分是什么意思？ – 2010-08-08 06:30:40

@Greg：我用“数学”猜测OP意味着计算理论中的常规语言，而“编程”指的是正则表达式实现（它比普通语言更能识别）。 – polygenelubricants 2010-08-08 10:56:30

@polygenelubricants：你猜对了:-) – 2010-08-09 19:10:51

是的，这两个正则表达式是相同的，因为它们都识别相同的语言。他们不完全一致的事实只是一个符号问题。

2010-08-08 06:34:52 bcat

这个答案使用从正则表达式理论中提取的术语具有数学品味。 – 2010-08-09 19:23:52

他们是否描述相同的语言？是。他们是否对试图解释该语言的人有同样的意思？没有。第二个告诉我，我应该对7s更感兴趣。

2010-08-08 06:32:15 Cirdec

以编程方式（如通过语言的正则表达式引擎评估），它仅在所产生的capturing groups中有所不同。

除此之外，它们是相同的。这是写作((7) + (1))而不是7 + 1。他们 ~~评估到~~ 是相同的。（是的，从数学角度来说，普通语言不会评估任何东西）

2010-08-08 06:35:04 Chubas

我不明白你的意思，“在数学上，常规语言不计算任何东西”。正则表达式以数学方式评估为确切的东西。 – 2010-08-09 19:22:13

我甚至不确定这个。正则表达式描述语言，然后可以由确定性有限状态机进行分析。这种评估的结果不是真或假，而是语言本身没有价值（取决于你解析的FSM）。如果我错了，请纠正我。 – Chubas 2010-08-10 14:46:20

第二个缩小到第一个。你是否同意

ab+

和

a(b)+

和

(ab)+

在语义上有什么不同？

2010-08-08 06:36:57 djna

那么，在数学上ab +和a（b）+在语义上是相同的。 – 2010-08-09 19:25:49

是的，但（ab）+不是，这就是为什么括号很重要。如果选择一个极简主义的例子（按照前两个），那么重要的差异就会丢失，这就是为什么我们需要第三个。 – djna 2010-08-09 19:55:38

唯一的区别是parens将封闭的模式分配给一个组，因此您可以在评估后引用该小块。

2010-08-08 06:38:39

不，程序化地他们不同于此。尝试使用re.findall（）在Python中匹配两个正则表达式，或者在C中使用POSIX regex（）匹配“777”。结果非常不同。 – 2010-08-09 19:15:07

对不起，我认为re.findall（）不是regex（）的同义词。所以，是的，它们在编程上只是在组合上有所不同。但是，我对数学感兴趣。 – 2010-08-09 19:19:30

回答