1

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 expression for binary numbers x such that hx + ix = jx?

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.

Improve this question
5
  • I believe 0000047 is a valid octal literal. Commented Jan 22, 2010 at 6:32
  • Also your regex matches 077777777777777777777777777777777777777777777. This compiles but it gives a warning: 'integer constant is too large for its type'. Commented Jan 22, 2010 at 6:38
  • But if an initial 0 means octal, would a value like 07777 be considered a negative 12-bit number (in a 2's complement sense) ? If 034567 is a 15-bit number and 000083 another, both are positive because the MSB is a zero. I'm not looking at your regexes, here: they're too complicated for me. They don't look right. Commented Jan 22, 2010 at 6:44
  • jspcal can u help me with this? Commented Jan 22, 2010 at 7:41
  • 1
    @unknown: you've asked the same question multiple times. The last time you asked the h^x + i^x = j^x question, you got some really good answers. Did you read about Fermat's last theorem on Wikipedia as you were told? Commented Jan 22, 2010 at 8:47

6 Answers 6

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1
  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?
Improve this answer

4 Comments

Hi Max, How did u arrive at this answer, could u throw some light?
It's pretty simple. There's the basic | branch between the octal on the left and the decimal on the right. The octal starts with a zero and is then followed by any number of digits between 0 and 7. Decimals are the same as your original regex.
should there be another [1-7] in front of [0-7]*?
If you want to allow multiple leading zeroes (e.g. 0051) then no.
1

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".

Improve this answer

Comments

1

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

Improve this answer

2 Comments

Please explain your answer!
added some explanation!
0

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?

Improve this answer

2 Comments

but jspcal is my answer to second one ((0|1){32}|1|(10)) correct?
it you remove the first term (0|1){32}| should work.... (prepend 0* if you want to match strings like "000001", and you would need to anchor the pattern (^$)
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.