# Recursive definition of a language given the regular expression

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?

## 1 Answer

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

$B=\{\epsilon\}$

$\mathcal{F}=\{X\to0X|10X|X1\}$

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

• 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? – cemulate Sep 9 '15 at 2:53
• @ChaseMeadors That's just my expression on the method. I've edited the answer to make it clear. – Terence Hang Sep 9 '15 at 3:28