how to express the following regular expression?

[Joona I Palaste]

Carl Howells <chowells at cs.uoregon.edu> scribbled the following
on comp.lang.java.programmer:
> "Stephen" <fungho at sinaman.com> wrote...
>> I want to search the following formats:
>>
>> ([1234567890]*)R
>> or
>> P([1234567890]*)
>>
>> this means there must be a 'P' before the number or a 'R' after the
>> number. However, I think I can't use this:
>> P?([1234567890]*)R?
>> because the number without P and R is also matched!
>>
>> How can I express it?

> Exactly you you'd expect...  One or the other:

> (P\d*)|(\d*R)

> You could also use [0-9] in place of \d, if you were really set on using the
> [] notation.  But there's no reason to use [1234567890].

This is indeed the only way. Regular expressions don't remember
things. When the regular expression "gets" to the R part, it
forgets what it did when it "was" in the P part.
This is the main reason why a criterion such as:

(((1234))) where the number of left parantheses is equal to the
number of right parantheses

cannot be expressed as a regular expression.
Noam Chomsky has written a definition of languages which addresses
this problem.
Context-free grammars are more powerful than regular expressions.
For example my criterion above can be expressed as the following
grammar (BNF notation):

TARGET ::= STRING
STRING ::= '(' STRING ')'
         | DIGITS
DIGITS ::=
         | ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
           DIGITS

The OP's criterion can be expressed as follows:

TARGET ::= STRING
STRING ::= 'P' DIGITS
         | DIGITS 'R'
DIGITS ::=
         | ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
           DIGITS

-- 
/-- Joona Palaste (palaste at cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste       W++ B OP+                     |
\----------------------------------------- Finland rules! ------------/
"All that flower power is no match for my glower power!"
   - Montgomery Burns