What is the regular expression for the language 0m1n where m+n is even?
+13
A:
If you mean a string 000...111... where the length of the string is even, you can use ^(00)*(01)?(11)*$
SLaks
2010-03-09 15:31:07
this is not an answer because it also validates 00 01 1 11 whose lenght is not even.
erasmus
2010-03-09 15:53:32
That's because I forgot to anchor the regex. It works correctly now.
SLaks
2010-03-09 15:55:09
+1 for the answer. Now, how do I up-vote you for understanding the question in the first place?
Amarghosh
2010-03-09 16:06:21
My 1600th answer, and a fitting one too.
SLaks
2010-03-10 01:31:08
+1
A:
Ok, so you need to consider for zero the cases when there are odd and when they are even. This requires two states, one for even zeros, one for odd zeros. Then for the odd zero case you need to have 1 one then an even number of ones. For the even case you just need an even number of ones.
Its easy to write the DFA, but I don't know how to plot it here, so I'm going to hazard a guess at the regular expression:
(0 (00)* 1 (11)*) \/ (00)*(11)*
Il-Bhima
2010-03-09 16:02:08
Here're plotted machines for that regex. Full NFA: http://static.max99x.com/misc/nfa.png. Cleaned NFA: http://static.max99x.com/misc/nfa2.png. Minimized DFA: http://static.max99x.com/misc/dfa.png.
Max Shawabkeh
2010-03-09 19:13:08
@Max: Awesome! Is that a tool of your own design? I remember implementing a NFA to minimal DFA converter many years ago, but it never occurred to me to render it with graphviz :)
Il-Bhima
2010-03-09 21:59:55
@Il-Bhima: Yeah. http://max99x.com/school/automata-editor. Might be somewhat buggy, though, since it was a quick school project.
Max Shawabkeh
2010-03-09 22:16:02