Regular expression

Question

I'm trying to find Strings of length 4 In this regular expression. However, I'm having trouble understanding how the string is built

$$1(1+00)^*0+(01)^*+(101+0)(10+λ)1^*$$

For example,

for $1(1+00)^*0$, if I decide that * gives me 1 or more I should get $1000$. But if I say * gives me nothing, would that mean that the string is $10$ or is it just $0$? Is my logic correct?

Does the * only affect whats in the brackets or does it affect everything behind it?

Here's an example string That I came up with (This is in regards to the whole expression): $$1001$$

hmakholm left over Monica · Accepted Answer · 2015-06-09T12:00:27.073

3

By convention, the Kleene star oprator $(\cdots)^*$ binds very strongly -- it applies only to the thing immediately before it, unless brackets are used to draw more in.

So $1(1+00)^*0$ means "a 1, followed by zero or more things that are each either 1 or 00, followed by a 0".

Your example 1001 is not matched by the regular expression. In particular it is not matched by $1(1+00)^*0$, because that can only generate strings that end with 0.

edited Jun 09 '15 at 12:00

answered Jun 09 '15 at 11:56

hmakholm left over Monica

286,031

Sorry, the example String refers to the longer regular expression – Daniel Munoz Jun 09 '15 at 11:58
@DanielMunoz: It is not generated by any of the other components either. The only strings they can generate that start with $1$ have to come from the third component and start with $101$. – hmakholm left over Monica Jun 09 '15 at 11:58
So in regards to $1(1+00)^0+(01)^+(101+0)(10+λ)1^*$ what would be an acceptable string providing it has a length of 4? – Daniel Munoz Jun 09 '15 at 12:02
@DanielMunoz: Some of them are 1110 and 1000 and 0101 and 1011. – hmakholm left over Monica Jun 09 '15 at 12:07
@DanielMunoz: The expression is of the form $A+B+C$ which means that each string has to come from $A$ alone, or $B$ alone, or $C$ alone (or perhaps several of these). So not only don't you need to use the entire expression; you must take the summands one at a time and see what they generate. – hmakholm left over Monica Jun 09 '15 at 12:11
Of course, That makes a lot of sense. Could I possibly get 1010 as a string? – Daniel Munoz Jun 09 '15 at 12:16
@DanielMunoz: I don't see any way to make 1010. – hmakholm left over Monica Jun 09 '15 at 12:18
Wouldn't you get: $1(1+00)^0 = 1$ then $(01)^ = 01$ then $(101+0)(10+λ)1^* = 0$. Why would this not work? – Daniel Munoz Jun 09 '15 at 12:24
@DanielMunoz: Because $A+B+C$ does not mean that you can concatenate strings generate by $A$ and $B$ and $C$. You can only get strings that are generated in full by $A$, and also strings that are generated in full by $B$, and also strings that are generated in full by $C$. – hmakholm left over Monica Jun 09 '15 at 12:25
(Also, that's an abuse of equals signs. You don't mean that $1(1+00)^*0$ and $1$ both have the same meaning, right). – hmakholm left over Monica Jun 09 '15 at 12:27
I completely misunderstood the $+$ sign, yes I was concatenating each string together and now I understand. – Daniel Munoz Jun 09 '15 at 12:29

Regular expression

1 Answers1