Regular expressions

Discussion in 'Perl Misc' started by Alexander Schmidt, Jan 10, 2004.

  1. 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 !
    Alexander Schmidt, Jan 10, 2004
    #1
    1. Advertising

  2. In article <btq0lj$a1ij4$-berlin.de>,
    Alexander Schmidt <> 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,
    :please ?

    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


    --
    Usenet is one of those "Good News/Bad News" comedy routines.
    Walter Roberson, Jan 10, 2004
    #2
    1. Advertising

  3. Alexander Schmidt

    Anno Siegel Guest

    Alexander Schmidt <> 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,
    > 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
    Anno Siegel, Jan 12, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jay Douglas

    Custom Regular Expressions in ASP.net

    Jay Douglas, Nov 2, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    593
    mikeb
    Nov 3, 2003
  2. mark

    Regular expressions

    mark, Jun 30, 2003, in forum: Perl
    Replies:
    4
    Views:
    1,709
  3. Dustin D.
    Replies:
    1
    Views:
    11,131
  4. Jay Douglas
    Replies:
    0
    Views:
    584
    Jay Douglas
    Aug 15, 2003
  5. Noman Shapiro
    Replies:
    0
    Views:
    216
    Noman Shapiro
    Jul 17, 2013
Loading...

Share This Page