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$ 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$ Commented Sep 9, 2015 at 3:28

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.