Search This Blog

Wednesday, March 15, 2006

The Challenge

I just had my first test in High Level Languages, a third-year course about the structures common to most/all high level languages, and how high level languages in general work. I thought one of the questions on the test was absolutely godly (and from what the teacher said, I was the only one in the class who figured out how to do it; however, I don't know if this is because nobody could figure out how to do it, or they made some critical typographical errors in their answers). I suggest you try and solve it, because it's an awesome question. It goes like this:

Create a grammar (BNF, EBNF, syntax diagram, whatever kind of formal metalanguage you want) rule for binary numbers of any length, containing an even number of 0s (0 inclusive) and an odd number of 1s, in any order.
You have fifteen minutes. Go!


Anonymous said...

Did I get it?

<number> ::= "1" <number> "1"
::= "11" <number>
::= <number> "11"
::= "0" <number> "0"
::= "00" <number>
::= <number> "00"
::= "1"

Anonymous said...

no, i don't get it. 1001010 can't be expressed. i give up!

Anonymous said...

okay, i actually got it this time, but the answer is so awesome i won't post it.