# Syntax Fun/Challenge

This topic is 4475 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

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
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
You get excited too easily :P

• 33
• 12
• 10
• 9
• 9
• ### Forum Statistics

• Total Topics
631352
• Total Posts
2999484
×