Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^3: check for power of a number with regex

by blokhead (Monsignor)
on Oct 26, 2009 at 13:37 UTC ( #803258=note: print w/replies, xml ) Need Help??


in reply to Re^2: check for power of a number with regex
in thread check for power of a number with regex

Any context-free language over a single-character alphabet is also regular (which can be shown using, for example, Parikh's theorem). So since this "language of exponentials" is non-regular, it is also non-context-free. Another way to look at it is that the pumping lemma for CFLs essentially collapses into the pumping lemma for regular languages when applied to single-character alphabets, because the concatenation operator is commutative on strings over a single-character alphabet.

I do stand by my intuition that backrefs alone (i.e., classical regexes + backrefs) won't help. But you are right, I am not able to prove it -- there is just no formal model that I'm aware of that exactly captures the expressivity of those operations, that would be amenable to impossibility proofs. I admit I hadn't thought of the new named captures & rules from 5.10 (I'm a bit behind the times). Clearly the named captures alone won't get you the regex desired in this case, but maybe some clever combination of both named rules & backrefs? I remain slightly skeptical but open-minded ;)

blokhead

  • Comment on Re^3: check for power of a number with regex

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://803258]
help
Chatterbox?
[atcroft]: .oO(Then there is the effect if a site changes their timezone, such as when the International Date Line was moved by the purchase of Alaska by the US from Russia in 1867, or several places (I cannot recall off-hand) that moved from one side of the Date
[atcroft]: Line to the other recently....)
[atcroft]: .oO(Then again, you also have to be careful if you had it to the database, and be aware of any assumptions it makes (such as SQLite assuming Gregorian calendar and a day of exactly 86400 seconds)...)

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2017-04-29 04:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I'm a fool:











    Results (531 votes). Check out past polls.