Which strings does L language produce?

46 Views Asked by At

Let $L = 1 \cup (01 \cup 10)(00 \cup 11)^*0$. Which are the strings $L$ produces? I thought the ones that have even number of zeroes and odd number of $1$. But, you can not produce $111$. Then I thought that $0101010$ (four $0$s and three $1$s) can not be produced. Any ideas? I am struggling to find the answer!

1

There are 1 best solutions below

4
On

First, the customary notation for union in regular expressions is a vertical bar, not $\cup$.

Next, a regular expression denotes a language, it doesn't produce one (the same way an algebraic expression describes operations that give a value).

Take the expression apart. First, it is the union of 1 and $(01\mid10)(00\mid11)^*0$. Now analyze the later: It starts 01 or 10, then repeats pairs of 0 or 1, and ends in 0.