Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^2: back translating regular expressions

by blokhead (Monsignor)
on Mar 03, 2005 at 05:27 UTC ( [id://436096]=note: print w/replies, xml ) Need Help??


in reply to Re: back translating regular expressions
in thread 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]

In Section Seekers of Perl Wisdom

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://436096]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2024-04-25 09:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found