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?

  • $\begingroup$ Are you asking for someone to list all elements of L? What exactly is your question? What approaches have you considered and what progress have you made? In what context did you encounter this problem, and can you credit the original source? $\endgroup$
    – D.W.
    Commented Jul 27, 2023 at 18:00
  • $\begingroup$ First of, thank you for your reply. I am mostly wondering about what the t' allows us to produce on this given language. I don't know the original source but it was presented in a class I was taking. I can understand most formal language definitions but for this one I am not sure. The t' can probably be replaced by either parts of the L bracket but does it also allow to t' into t' into t' and so on, basically never stopping? And if the last t' grabs a ba, do the other t' also have to write a part of L? Making it very long words? $\endgroup$ Commented Jul 27, 2023 at 18:45

2 Answers 2


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$?

  • $\begingroup$ That is a very indepth answer. Thank you so much for taking the time to write out all of this. I agree with you that it just doesn't make sense and is not well defined. The "solution" to this problem is supposed to be a Turing machine that loops over a bunch of 01s and eventually decides to jump to aba and stop (yes, they are making us read it from right to left for whatever reason). But I just don't see that. Then again a lot of "solutions" had mistakes in them so I don't doubt this is also one of them... (edited out the right/left mistake) $\endgroup$ Commented Jul 27, 2023 at 19:07
  • $\begingroup$ Sorry, I meant to say, they make us read from right to left basically starting at the empty cell right next to the word $\endgroup$ Commented Jul 27, 2023 at 19:09
  • $\begingroup$ I don't see why the language $L$ you propose (which is simply a more rigorous notation for what probably the question meant; an even more rigorous way would be to talk about fix-points, but probably above the level of the class) is not unique. As for my argument for uniqueness, to see that membership is well-defined for a my word, let $n$ be the length of the shortest word whose membership is not well-defined; if it doesn't start with "10" or "010" then it's for sure not in L. If it start with "10", or "010", then by hypothesis its suffix of length n-2 (n-3 resp.) has well-defined membership. $\endgroup$ Commented Jul 27, 2023 at 19:33
  • $\begingroup$ @BernardoSubercaseaux, thank you for the feedback. I agree with you. I've updated my answer based on your feedback. $\endgroup$
    – D.W.
    Commented Jul 27, 2023 at 21:05

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$.

  • $\begingroup$ Thank you! And yes, that is how I see it aswell but in my given solution they seem to only allow a recursion on the 10 part and define it as if you end up with a 010, you stop the process, which just can't be true. I found a variation of this problem. Does this change anything? Given: L := {w elementof {0,1}* : w=(010 | 10 |(10 | t') )} $\endgroup$ Commented Jul 28, 2023 at 0:25
  • $\begingroup$ @NothingAgent: why didn't you show the given solution ??? $\endgroup$
    – user16034
    Commented Jul 28, 2023 at 5:31
  • $\begingroup$ Because the given solution was/is wrong. That is what it is all about. It doesn't make sense so we were trying to make sense out of it here. The other Language I posted has nothing to do with the first question asked. It is just a variation of the problem that I have found these days $\endgroup$ Commented Jul 28, 2023 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.