ansaurus

Question

Answer 1

+1 A:

i believe it would be like this

((1*)(01)*))* 00 ((11*)0)*1*

Arthur Rizzo 2010-09-20 17:19:21

Answer 2

A:

The sequence:

Anything but 00, ending with 1
00
Anything but 00, starting with 1

Eli Bendersky 2010-09-20 17:19:33

Answer 3

+5 A:

Try this:

1* (011*)* 00 (11*0)* 1*

An explanation:

1*: any amount of leading 1’s
(011*)*: if there is a 0 before the 00, it must not be followed by another 0, thus only one or more 1’s are allowed; this pattern may be repeated any number of times
00: the two 0’s
(11*0)*: if there is a 0 after the 00, it must not preceded by another 0, thus only one or more 1’s; this pattern may be repeated any number of times
1*: any amount of trailing 1’s

Gumbo 2010-09-20 17:28:14

Thank you very much. Explanation helped out a lot.

Seephor 2010-09-20 17:36:04

11* is better written as 1+

brianary 2010-09-20 17:58:28

@brianary: In this case “+” is the alternation operator. So “0 + 1” is either “0” or “1”.

Gumbo 2010-09-20 18:46:10

in some books 1+ is the same thing as 11* . it just depends on where you're getting your theory from.

Arthur Rizzo 2010-09-20 19:01:35

@Arthur Rizzo: It depends on how the syntax of regular expressions is defined. I’ve learned it with “+” as alternation operator while others use “|”.

Gumbo 2010-09-20 19:31:36

It seems unusual to teach theory in a dialect that differs so fundamentally from implementations.

brianary 2010-09-21 16:44:00

@brianary: I think in most theory classes "one or more 1's" is written 1^+ (i.e. the plus is in a superscript). Most implementations don't have superscripts, so they just bring the plus down. It is confusing because it disagrees with the standard use of plus (which is 'or'), but I think that's a limitation of typesetting, not really an issue with either the theory or the implementation. Some theorists (notably Sipser) use the union operator instead of the plus to avoid this confusion.

Xodarap 2010-09-27 16:37:19

@brianary: The basic regular expression syntax in theory class is often only alternation (`α+β`), concatenation (`αβ`), repetition (`α*`), and grouping (`(α)`). More advanced syntax as we know it from modern regular expression implementations is only syntactic sugar: `α?` → `(ε+α)`, `α+` → `αα*`, `[abc]` → `(a+b+c)`, etc.

Gumbo 2010-09-27 17:37:35

Where is this syntax documented? Is it broadly accepted, or a single textbook? I still feel that it is harmful or at least questionable to unnecessarily use a different syntax for theory than is used in any real language. Especially since this is one area where there is so little inconsistency in implementations.

brianary 2010-09-27 23:00:46

ansaurus

tags:

views:

answers:

Finding a regular expression

related questions