Velocity Reviews > Perl > Regular expressions

# Regular expressions

Alexander Schmidt
Guest
Posts: n/a

 01-10-2004
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,
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
Guest
Posts: n/a

 01-10-2004
In article <btq0lj\$a1ij4\$(E-Mail Removed)-berlin.de>,
Alexander Schmidt <(E-Mail Removed)> wrote:
: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., *
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

--
Usenet is one of those "Good News/Bad News" comedy routines.

Anno Siegel
Guest
Posts: n/a

 01-12-2004
Alexander Schmidt <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> 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,

assignment. We don't know that notation, you should ask someone
who knows. Whoever issued the assignmnt is a good bet.

Anno