Re^2: back translating regular expressions

What on earth does that have to do with the halting problem? A computer going into an infinite loop is not the halting problem. If you meant that you can't tell whether a regular-expression denotes an infinite language, that's not quite right either. It's infinite if and only if it contains an infinite quantifier (+, *, {m,}), which is an easy property to check.

blokhead

Comment on Re^2: back translating regular expressions

Replies are listed 'Best First'.
Re^3: back translating regular expressions by Anonymous Monk on Mar 03, 2005 at 10:05 UTC
`/a/` [download] does not contain a quantifier, but there are an infinite amount of strings it will match. And if you only want to consider anchored strings: `my $q1; $q1 = qr /a(??{$q1})?/; my $q2 = qr /^$q1$/;` [download] matches all strings containing nothing but a's. But it doesn't use any of the quantifiers you mentioned. Also, `/^(?!)$/` [download] contains a `` quantifier, but it doesn't actually match any string. Perhaps you want to discount lookahead. Then I give you: `/^(\|)$/` [download] It'll give a warning, but all it matches is the empty string. But it does have a `` quantifier.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: back translating regular expressions
by Anonymous Monk on Mar 03, 2005 at 10:05 UTC

    /a/
[download]

    my $q1;
       $q1 = qr /a(??{$q1})?/;
    my $q2 = qr /^$q1$/;
[download]

Also,

    /^(?!)*$/
[download]

*

    /^(|)*$/
[download]

*

[reply]
[d/l]
[select]