Jump to content
  • Advertisement
Sign in to follow this  
Catafriggm

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
How about a regular expression?

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.

[edit] Missed a paren

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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!