regex - Regular expression for equal number of 0 and 1

Question

How to find regular expression with equal number of 1 and 0. I am also interested in how you think such solution ?

example: should match : 1100, 00100111 , 01 . shouldn't match: 110 , 0, 11001.

I need regular expression which gives set of all such string . If length of string in set given by regular expression in 2n then number of 0s should be equal to number 1s = n.

Answer 1

It is not possible to generate a regular expression for the language L = (0,1) (same number of 1s and 0s). This is not a regular language, so cannot be described with a regular expression. It's not regular because an automaton which accepts it would need differing amounts of memory depending on the length of the input. A regular language is one which uses constant memory, regardless of the length of the input. The language you describe can be generated by a Context Free Grammar, but not a regular expression. The following CFG generates strings where the numbers of 0s and the number of 1s are equal. If S is any word in the language: S -> SS; S -> 0S1; S -> 1S0; S -> e the empty word For this language you need a stack, and a pushdown automaton could be designed to accept it, or a Turing machine.