Regular expressions

[Alexander Schmidt]

Hi,

I am studying Computer Science and we are currently covering regexps in
Theoretical CS and I guess you Perl guys should know how to handle them and
might be able to help me a bit:

The regular expression

a)
10 + (0 + 11) 0* 1 ( the "+" denotes an OR in our notation and maybe
replaced by a "|" if you prefer - at least I think that it should be an OR)

describes these words:
Either the word 10 OR the word 0 followed by zero or more 0s followed by the
1 OR the word 11 followed by one or more 0s followed by the 1, right ?

Examples:
10
0 1
0 0000000 1
11 1
11 00000000 1

b)
01 (((10)* + 1111) + 0)* 1

describes these words:
The 01 followed by zero or more often the 10 OR the 1111 OR the 0, where the
10s or the 1111s or the 0s can be repeated zero times or more often. Finally
the word ends with a 1.
Right ?

Examples:
01 10 1
01 10101010 1
01 1111 1111 1
01 00000 1
01 1010 1111 00 1111 1010 1 (we can mix it !)

I am not sure if I have understood the priorities correctly, so what to
"execute" first, might someobdy explain them with a few examples perhaps,
please ?
What do I have to take care for ?

So, why can't a generate words like these:
10 followed by one or more zeros followed by the 1 OR 0 followed by one or
more 0s followed by the 1 or 11 followed by one or more 0s followed by the 1
?
Would this be: (10+0+11) 0* 1 ?

So, I do not know in which order to read it and to evaluate the expression,
the rest is clear.
Some examples would be great !

Thanks !

 

[Walter Roberson]

:I am studying Computer Science and we are currently covering regexps in
:Theoretical CS and I guess you Perl guys should know how to handle them and
:might be able to help me a bit:

:The regular expression


:10 + (0 + 11) 0* 1 ( the "+" denotes an OR in our notation and maybe
:replaced by a "|" if you prefer - at least I think that it should be an OR)

:I am not sure if I have understood the priorities correctly, so what to
:"execute" first, might someobdy explain them with a few examples perhaps,
lease ?

In order of decreasing priority:

()
repetition i.e., *
concatenation (adjacent symbols implies concatenation)
alternation i.e., +

You can add [] as you go upwards through this list:

[[10] + [(0 + 11) 0* 1]] first-level alternation
[[[1][0]] + [[(0 + 11)][0*][1]]] first-level concatenation
[[[1][0]] + [[(0 + 11)][[0]*][1]]] first-level repetition
[[[1][0]] + [[([0] + [11])][[0]*][1]]] enter the () and start the cycle there
with the alternation
[[[1][0]] + [[([0] + [[1][1]])][[0]*][1]]] then the concatenation inside the ()
[[[1][0]] + [[([0] + [[1][1]])][[0]*][1]]] there is no repetition in the first
level ()
[[[1][0]] + [[[0] + [[1][1]]][[0]*][1]]] first level () is fully resolved

123 23 21 234 3 45 45 43234 3 23 210

 

[Anno Siegel]

Hi,

I am studying Computer Science and we are currently covering regexps in
Theoretical CS and I guess you Perl guys should know how to handle them and
might be able to help me a bit:

The regular expression

a)
10 + (0 + 11) 0* 1 ( the "+" denotes an OR in our notation and maybe
replaced by a "|" if you prefer - at least I think that it should be an OR)

describes these words:
Either the word 10 OR the word 0 followed by zero or more 0s followed by the
1 OR the word 11 followed by one or more 0s followed by the 1, right ?

[more examples snipped]

Well, it's definitely not Perl notation.

I am not sure if I have understood the priorities correctly, so what to
"execute" first, might someobdy explain them with a few examples perhaps,
please ?

Your question is about the particular regex notation used in the
assignment. We don't know that notation, you should ask someone
who knows. Whoever issued the assignmnt is a good bet.

Anno