Regular expression problem

Question

What is the regular expression for the language 0^m1ⁿ where m+n is even?

Doubleripper

Either I'm tired or your question makes very little sense. – Skinnydip

I don't think this has anything to do with regexp... – Skinnydip

@Andy E: It's not because you're tired mate. – Gokey

Yes, it does. I'd explain it, but all I'd be doing is copying the question here -- I don't think it can be much simpler than that. – Woodhead

How do we know this is programming related? – Baronetage

Why people above don't try to help but joke with the question? it can be wrong or very simple. that doesn't mean, it doesn't have an answer. – Doubleripper

@Binary Worrier: Thanks, I thought my brain was going to explode trying to make sense of this question. – Skinnydip

Why was this question closed? Its a question about computation which is the basis of programming. Its a valid question although definitely homeworkish. Its a pretty interesting boundary case of a regular language that doesn't look regular. – Homovec

@Binary Worrier, @Andy E please explain what is wrong for you with this question? People want to learn here. why their questions are closed and mocked? – Doubleripper

The sad part is, if the question claimed to be about a C# 1.0 program, but posed exactly the same problem, nobody would have dared challenge it. Has SO finally crossed the line, from being hesitant to help with homework, to full-on anti-intellectualism? – Skilful

@Doubleripper How about rephrasing it to "Regex for a string of consecutive zeros followed by consecutive ones, whose total length is even?" Or at least adding one or two examples? – Guenther

@erasmus, @Ken: I voted to close this because the question looks like nonsense. Granted, it appears to be a valid question, but that doesn't change the fact that it looks like nonsense to me.. I've voted to close on hundreds of questions over the last year and a half, of those a decent percentage are ones that look like garbage. This is only the second time I've been wrong, and for being wrong I apologise. However I do not apologies for closing questionable questions. There are trolls on SO that ask unanswerable questions ONLY so they can see folks tie them selves . . . – Gokey

. . . in knots trying to provide an answer, those questions and other unanswerable questions should be closed. In my opinion – which is provided as is, and which you are of course allowed to disagree with – this question is poorly constructed and is too brief, the asker could have provided some context/background. – Gokey

@Binary Worrier, this question is not brief and provides everything for a possible answer. No background is needed. if you have a regex question like this, you can just ask it. secondly, besides closing the question with wrong decision you mocked with it. you said "@Andy E: It's not because you're tired mate. – Binary Worrier" What is this? I think you should be more kind. The aim here should be to help people not mock them. – Doubleripper

@earsmus: I again apologise for closing the question. I will also apologise for hurting your feelings. Andy commented "Either I'm tired or your question makes very little sense", I simply agreed with Andy (I'm sorry but without reading the answers I would still not "get" your question). I've often received much harsher and more pointed sarcasm on answers I've posted. I fear I'll offend you again with this advice, but I suggest for your own sake you learn to be a bit more thick skinned when reading comments on your posts. I'm sorry for making you feel bad, it is not and was never my intention. – Gokey

Answer 1

If you mean a string 000...111... where the length of the string is even, you can use ^(00)*(01)?(11)*$

Hussar

this is not an answer because it also validates 00 01 1 11 whose lenght is not even. – Doubleripper

That's because I forgot to anchor the regex. It works correctly now. – Hussar

+1 for the answer. Now, how do I up-vote you for understanding the question in the first place? – Guenther

My 1600th answer, and a fitting one too. – Hussar

Yes, +1 for understanding the question in the first place, then answering so casually! Wow, that's style. :) @Amarghosh, if you remember your comment from four years ago, I took care of that for you. :) – Disharmonious

Answer 2

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)*

Homovec

Here're plotted machines for that regex. Full NFA: static.max99x.com/misc/nfa.png. Cleaned NFA: static.max99x.com/misc/nfa2.png. Minimized DFA: static.max99x.com/misc/dfa.png. – Jared

@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 :) – Homovec

@Il-Bhima: Yeah. max99x.com/school/automata-editor. Might be somewhat buggy, though, since it was a quick school project. – Jared