Regexes for integer constants and for binary numbers

I have tried 2 questions, could you tell me whether I am right or not?

1. Regular expression of nonnegative integer constants in C, where numbers beginning with 0 are octal constants and other numbers are decimal constants.

   I tried 0([1-7][0-7]*)?|[1-9][0-9]*, is it right? And what string could I match? Do you think 034567 will match and 000083 match?

2. What is a regular expres开发者_StackOverflowsion for binary numbers x such that h^x + i^x = j^x?

I tried (0|1){32}|1|(10)).. do you think a string like 10 will match and 11 won’t match?

Please tell me whether I am right or not.

You can always use http://www.spaweditor.com/scripts/regex/ for a quick test on whether a particular regex works as you intend it to. This along with google can help you nail the regex you want.

1. 0([1-7][0-7])?|[1-9][0-9] is wrong because there's no repetition - it will only match 1 or 2-character strings. What you need is something like 0[0-7]*|[1-9][0-9]*, though that doesn't take hexadecimal into account (as per spec).
2. This one is not clear. Could you rephrase that or give some more examples?

Your regex for integer constants will not match base-10 numbers longer than two digits and octal numbers longer than three digits (2 if you don't count the leading zero). Since this is a homework, I leave it up to you to figure out what's wrong with it.

Hint: Google for "regular expression repetition quantifiers".

Question 1:

Octal numbers:

A string that start with a [0] , then can be followed by any digit 1, 2, .. 7 [1-7](assuming no leading zeroes) but can also contain zeroes after the first actual digit, so [0-7]* (* is for repetition, zero or more times).

So we get the following RegEx for this part: 0 [1-7][0-7]*

Decimal numbers:

Decimal numbers must not have a leading zero, hence start with all digits from 1 to 9 [1-9], but zeroes are allowed in all other positions as well hence we need to concatenate [0-9]*

So we get the following RegEx for this part: [1-9][0-9]*

Since we have two options (octal and decimal numbers) and either one is possible we can use the Alternation property '|' :

L = 0[1-7][0-7]* | [1-9][0-9]*

Question 2:

Quickly looking at Fermat's Last Theorem:

In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two. (http://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem)

Hence the following sets where n<=2 satisfy the equation: {0,1,2}base10 = {0,1,10}base2

If any of those elements satisfy the equation, we use the Alternation | (or)

So the regular expression can be: L = 0 | 1 | 10 but can also be L = 00 | 01 | 10 or even be L = 0 | 1 | 10 | 00 | 01

Or can be generalized into:

1. {0} we can have infinite number of zeroes: 0*
2. {1} we can have infinite number of zeroes followed by a 1: 0*1
3. {10} we can have infinite number of zeroes followed by 10: 0*10

So L = 0* | 0*1 | 0*10

max answered the first question.

the second appears to be the unsolvable diophantine equation of fermat's last theorem. if h,i,j are non-zero integers, x can only be 1 or 2, so you're looking for

^0*10?$

does that help?

There are several tool available to test regular expressions, such as The Regulator.

If you search for "regular expression test" you will find numerous links to online testers.