in Theory of Computation
1,661 views
1 vote
1 vote
Given two Regular expressions are equal or not ?

1) (1+01*0)*        2) 1*(01*0)* 1*

Give proper explanation also.
in Theory of Computation
1.7k views

2 Comments

i ma getting a string 0101010 from first statement which i hope second second could'nt generate making them not equal...please correct me if i did a mistake
1
1

 1*(01*0)*1*  does this regular expression be understood as ::-

while generating the string first 1* will pumped as many times as we want then 01*0 will be pumped then last 1* will be pumped .

correct me if I had misinterpreted ?

0
0

2 Answers

1 vote
1 vote
Best answer
The two regular expressions are not equivalent. The first regular expressions denotes the set of strings having any combination of 1's and 01*0's.  Whereas the second regular expression denotes the set of all strings where any number of 1's are followed by any number of 01*0's followed by any number of 1's. So strings of the form 10101010 are generated by the first regular expression but it isn't generated by the second regular expression.
selected by
0 votes
0 votes
According to me these two regular expressions are not equivalent. As, on simplifying expression 1, we get 1*(01*0)* which is not equivalent to expression 2