CODEWITHSUNDEEP
regex
user256415
user256415

Reputation: 11

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

Upvotes: 1

Views: 2284

Answers (6)

Haji Akhundov
Haji Akhundov

Reputation: 33

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

Upvotes: 1

Hans Kesting
Hans Kesting

Reputation: 39284

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.

Upvotes: 0

jspcal
jspcal

Reputation: 51904

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?

Upvotes: 0

Learning
Learning

Reputation: 8175

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.

Upvotes: 2

Amarghosh
Amarghosh

Reputation: 59451

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

Upvotes: 1

Max Shawabkeh
Max Shawabkeh

Reputation: 38603

  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?

Upvotes: 1

Related Questions