Understanding Language L

Question

Given:

L := {w elementof {0,1}* : w=(010 | 10)(10 | t'), with t' elementof L}

What words can we build with these rules?

01010, 1010, what else? Does the t' allow 010010?

Answer 1

I can understand your confusion. Strictly speaking, this is not a valid definition of $L$, because it is circular: it defines $L$ in terms of itself. So I can understand why you are confused.

I think one more precise way to define the language $L$ would be to say that $L$ is some language that satisfies the equation

$$L = \{w \in \{0,1\}^* \mid w=01010 \text{ or } w=1010 \text{ or } \exists t' \in L . w=010t' \text{ or } w=10t'\}$$

On first glance, it might appear that there could be multiple languages that satisfy this equation, so this is not necessarily yet a unique definition of a language. One standard way to address this is to first prove that there exists at least one language that satisfies this equation, and then define $L$ as the smallest language that satisfies the equation. That would be a satisfactory and unambiguous definition of $L$.

Alternatively, another way to view this is that $L$ is the smallest language that satisfies the following two rules:

1. $\{01010, 1010\} \subseteq L$
2. $(010|10) L \subseteq L$

Now you should be able to answer your questions. Can you prove using the latter two rules that $010010 \in L$? Or, can you write down a language $L$ that satisfies the equation? Once you have done so, does that language contain $010010$?

Answer 2

The definition is recursive.

For the base cases (ignoring $t'$), we consider $(010|10)10$, or $010\,10|10\,10$.

Then, letting $t'$ take these values, we add the four combinations $010\,010\,10|010\,10\,10|10\,010\,10|10\,10\,10$.

Next, eight combinations, $010\,010\,010\,10|010\,010\,10\,10|010\,10\,010\,10|010\,10\,10\,10|10\,010\,010\,10|10\,010\,10\,10|10\,10\,010\,10|10\,10\,10\,10$

Further combinations are longer. You cannot form $010010$. As you can observe, the strings are $(010|10)^+10$.