Sign in to follow this  
Catafriggm

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


Link to post
Share on other sites
BeanDog    1065
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
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this