4
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 9, 2015 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
    Commented Sep 9, 2015 at 3:28

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.