CODEWITHSUNDEEP
stringexpressioncomputation
Haya Hallian
Haya Hallian

Reputation: 153

Constructing Regular expression that generates a given languge

This is an example ginen in my textbook "Introduction to theory of Computation". Given that the alphabet ∑ as{0,1}, 

{w|every 0 in w is followed by atleast one 1}}

a regular expression for it is shown as (01+)*. 1+ means only a single instance of 1. Now what I understand is that (01+)* would mean string like 0101010101010101.... what if I have a string 11111101 or 011111111 or just 1 These string do fulfill the given criteria. But the regular expression (01+)* will not generate them.

Secondly for `{w|w starts and ends with same symbol}` the expression is given as `0∑*0 U 1∑*1 U 0 U 1.`

As far as I have learnt the union of two things means either first one, or second one OR BOTH. If I take a string 01110 for 0∑*0 and another string for 10001 1∑*1 and then take union of these two 0111010001the union string DOESNOT start and end with same symbol. Does it mean that union cannot combine both or the expression is not correct?

Upvotes: 0

Views: 250

Answers (1)

uba
uba

Reputation: 2031

1+ means 'one or more 1s'. Therefore, it generates 1, 11, 111, and so on. So the regular expression (01+)* actually generates the strings in which "every 0 is followed by one or more 1s and the first symbol in the string is not a 1".

To get {w|every 0 in w is followed by atleast one 1} the regular expression would be slightly different. It would be 1*(01+)*

In the second question, what you have taken is concatenation. 01110 concatenated with 10001 is 0111010001. Union of two sets is a set containing all the elements of both sets

Upvotes: 1

Related Questions