# Syntax Fun/Challenge

## Recommended Posts

Catafriggm    296
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. If you know anything about formal grammars, you should try it for fun, because it's an awesome question (if you can come up with the answer, you'll realize why it's such 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 ten minutes. Go!

##### Share on other sites
BeanDog    1065

All strings w such that w matches the pattern:
(00|01(11)*10)*(1|01(11)*0)((0(11)*0)|(1|0(11)*10(00|01(11)*10)*(1|01(11)*0)))*

It's a simple parity problem. A four-state deterministic finite state machine describes it easily. The construction of a regular expression from a DFA is mechanical--you could literally write a program to produce the string I did by hand above.

 Missed a paren

[Edited by - BeanDog on March 18, 2006 1:32:14 AM]

##### Share on other sites
Catafriggm    296
Ding, ding. I have no idea what that regular expression means (I don't know regular expressions), but your description is exactly what I came up with. I even made this beautiful graph to show the machine for my blog, as well as this variation, where 'even number of 0s' is 0-exclusive. Now, isn't that an awesome question? :P

##### Share on other sites
hymerman    221
You get excited too easily :P