Consider the following regular expressions:
- 7+
- (7)+
Does anyone that is very familiar with regular expression theory in Mathematics agree that the two regular expressions are semantically the same?
A:
Do they describe the same language? Yes. Do they mean the same thing to someone trying to interpret the language? No. The second one tells me that I should be more interested in the 7s.
Cirdec
2010-08-08 06:32:15
+1
A:
Yes, those two regular expressions are the same because they both recognize the same language. The fact that they are not written identically is just a notational issue.
bcat
2010-08-08 06:34:52
This answer has a mathematical taste using terminologies drawn from Regular Expression theory.
Tadeus Prastowo
2010-08-09 19:23:52
+4
A:
Programmatically (as in evaluated by the regular expression engine of a language) it only differs in the capturing groups resulting.
Other than that, they are the same. It is as writing ((7) + (1)) as opposed as 7 + 1. They evaluate to are the same. (Yeah, mathematically speaking, regular languages doesn't evaluate to anything)
Chubas
2010-08-08 06:35:04
I don't get what you mean by "mathematically speaking, regular languages doesn't evaluate to anything". Regular expression mathematically evaluates to something for sure.
Tadeus Prastowo
2010-08-09 19:22:13
I'm not even sure about this one. Regular expression describe languages, that can then be parsed by a deterministic finite state machine. The output of such evaluation is either true or false, but the language doesn't have a value for itself (depends on the FSM you're parsing with). Please correct me if I am wrong.
Chubas
2010-08-10 14:46:20
A:
The second reduces to first. Do you agree that
ab+
and
a(b)+
and
(ab)+
are semantically different?
djna
2010-08-08 06:36:57
Yes, but (ab)+ isn't, and that's why the brackets are important. If a minimalist example is chosen (as per the first two) then important differences are lost, that's why we needed the the third.
djna
2010-08-09 19:55:38
A:
The only difference is the parens assign the enclosed pattern to a group so you can reference that little piece after it's been evaluated.
Matt Williamson
2010-08-08 06:38:39
No, programmatically they differ more than that. Try to match both regular expressions in Python using re.findall() or in C using POSIX regex() to "777". The results are pretty much different.
Tadeus Prastowo
2010-08-09 19:15:07
Sorry, I think re.findall() is not a synonym for regex(). So, yes, programmatically they just differ in the grouping. But, I am interested in the Mathematics.
Tadeus Prastowo
2010-08-09 19:19:30