CODEWITHSUNDEEP
regexcomputer-sciencefinite-automatacomputation-theory
reign
reign

Reputation: 171

Regular Expression Simplification Issue

I'm trying to understand the equivalence between regular expressions α and β defined below, but I'm losing my mind over conflicting information.

a+b:   a or b
ab:    concatenation of a and b
$:     empty string

α = (1*+0)+(1*+0)(0+1)*($+0+1)

β = (1*+0)(0+1)*($+0+1)

https://ivanzuzak.info/noam/webapps/regex_simplifier/ says, that α is equivalent to β.

My school however teaches that concatenation has stronger binding than union, meaning that:

11*+0 =/= 1(1*+0)

Which would mean that my α looks like this with parentheses:

α = (1*+0) + ( (1*+0)(0+1)*($+0+1) )

and that

α =/= ( (1*+0) + (1*+0) ) (0+1)*($+0+1)


I hope it's clear what my problem is, I'd appreciate any kind of help. Thanks.

Upvotes: 0

Views: 63

Answers (2)

reign
reign

Reputation: 171

Alright, it turns out that I have misunderstood why b+b <=> b.

It's that L1∪L2 <=> L2, if L1 is subset of L2.

Upvotes: 0

Roland Illig
Roland Illig

Reputation: 41686

Usually, two regular expressions are considered equivalent when they match the same set of words.

How they match it is not relevant. Therefore it doesn't matter which of the operators has greater precedence.

Note the subtle difference between being equal (in written form) and being equivalent (having the same effect).

Upvotes: 1

Related Questions