The Gateway to Computer Science Excellence
0 votes
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 by (167 points) | 178 views
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*(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 ?

2 Answers

+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.
by Active (5k points)
selected by
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
by (11 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,242 answers
95,936 users