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

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?

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: $$ (1 \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 $\mathcal{F}$ such that $L_1$ is the closure of $B$ under $\mathcal{F}$, i.e. $L_1 = <B>_{\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?

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