Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$

I know that there is a DFA that accepts this language, and furthermore, that the regular expression is: $$ (0 \cup 10)^* 1^* $$

I'm asked to obtain a formal recursive definition of $L_1$, that is, find a basis $B \subset \Sigma^*$ and a finite set of functions on strings $\mathcal{F}$ such that $L_1$ is the closure of $B$ under $\mathcal{F}$, i.e. $L_1 = \langle B \rangle_{\mathcal{F}}$

I'm not sure how to go about this. Every way I can think to "encode" the regular expression into "functions" that build the language they're really ugly or involve piecewise definitions (if $x$ doesn't end with 1, otherwise, etc.)

Is there a simple and clean way to do this?


Just replace Kleene stars with $\epsilon$ to find the basis and position, then extend to both direction.



$L_1 = \langle B \rangle_{\mathcal{F}}$

| cite | improve this answer | |
  • $\begingroup$ I think I'm almost getting it (I can see that your collection of functions is correct), but could you explain what you mean by "collapse" the Kleene stars? $\endgroup$ – cemulate Sep 9 '15 at 2:53
  • $\begingroup$ @ChaseMeadors That's just my expression on the method. I've edited the answer to make it clear. $\endgroup$ – Terence Hang Sep 9 '15 at 3:28

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.