I'm having trouble constructing a regular expression to meet the following criteria:

$$\sum = \{0,1\}$$

$$\epsilon \in L$$

$$0 \in L$$

$$1 \in L$$

$$\forall x \in L, 110x \in L \land x01 \in L$$

What I have so far is: $$((1^*0)^*(0+1)^*(01)^*)^* \text{ or } (1^*(0+1)^*)$$

However I dont believe this to be fully correct because the $1^*$ implies that not only can $110x \in L$ be true, but so can $1111110x \in L$. Not sure to to structure it such that only the first exists or doesnt.

What really throws me off is Kleene's closure. Because say $(1^*0)^*$ is grouped with a $^*$, that means it may be any combination of whats inside, including nothing at all right? The $\epsilon$ string?

Surely it is not as easy as:


Because $1100000001010101011101010$ would be captured by that expression right?

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. If you want to know whether your proposed solution is correct, try proving it correct! Have you checked whether it meets each of the criteria you list? $\endgroup$
    – D.W.
    Feb 12 '18 at 0:08
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/87986/755, math.stackexchange.com/q/2646540/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W.
    Feb 12 '18 at 0:13

To check whether your proposed solution is correct, check each of the criteria to see whether the criteria is met. Then you will know whether your candidate solution is correct.

Yes, the language $(1^*0)^*$ includes the empty string. That follows from the definition of the Kleene star. When it doubt, look up the definition and see what it says.

If you want a more systematic way to find a solution to this kind of problem -- or if you want to find the smallest language that satisfies these conditions, as you later suggest in a comment -- here's a big hint for how to do that:

Construct a grammar for a language that meets these criteria. What kind of grammar is it? What can you do with that?

It's your exercise, so I'll let you work out the details for yourself and have the joy of solving it on your own.

  • $\begingroup$ Problem is the wording. Finding the "smallest language L over the alphabet". Well the smallest language is constantly "growing" if for each member "x in L" has to have a "110x & x01" also in L. Meaning 110101 has 110110101 which has 110110110101, etc...; how can the "smallest" be defined if each successive element must also have those variants? $\endgroup$
    – pstatix
    Feb 12 '18 at 0:20
  • $\begingroup$ @pstatix, well, you didn't include that in the question, so I don't know how we could possibly be expected to know that. When you leave important information like that out of the question, you're asking people to volunteer to spend their time on something that is useless to you. It's important to make sure your question includes all relevant information from the start. In any case, my "more systematic way" handles that version of the problem. $\endgroup$
    – D.W.
    Feb 12 '18 at 0:24
  • $\begingroup$ Even still, the smallest language is never a finite regular set. If each member of L must have a 110x and x01 variant, then it must continually grow. I've worked out the issue, I'm seeking advice/help on how to refine it to become the "smallest language of L". $\endgroup$
    – pstatix
    Feb 12 '18 at 0:33
  • $\begingroup$ $(0+1)^*$ gets me $\{0, 1, \epsilon\}$; but the "for each x in L" would mean each would need 1 or more preceding or ending terms (since each new string becomes a new x in L and thus also needs its own). $\endgroup$
    – pstatix
    Feb 12 '18 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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