2
$\begingroup$

I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question:

We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$

Show that A* is a reflexive and transitive set containing A and if B is any other reflexive and transitive set containing A, then $A^*\subseteq B$.

I've shown that Kleene star satisfies these two conditions. I've tried partitioning B into two sets with $A = B \cup C $ and trying a constructive proof but this hasn't led any where. I also am considering a proof by contradition but don't know where to start.

Can you help me with a hint on how to approach this problem?

$\endgroup$
1
  • 1
    $\begingroup$ Do you see how $BB \subseteq B$ implies that $b_1b_2b_3 \in B$ for any $b_1, b_2, b_3 \in B$? $\endgroup$ – Karolis Juodelė Jan 19 '14 at 8:29
1
$\begingroup$

Hint: Try the usual approach to show set inclusion! That is, pick $w \in A^*$ and show that $w \in B$.

Next hint:

Apply transitivity of $B$ repeatedly.

More elaborately:

If $w \in A^*$ then either $w = \varepsilon \in B$ or there are $w_1, \dots, w_k \in A \subseteq B$ with $w = w_1 \cdot \dots \cdot w_k$. Now, because $BB \subseteq B$ we have $w_2' = w_1 w_2 \in B$. For the same reason, $w_2' w_3 \in B$. And so on. Perform induction for the general proof.

$\endgroup$
1
  • $\begingroup$ Thanks Raphael! This was really helpful. I will practice set inclusion proofs more and try to understand these patterns. $\endgroup$ – Srinivas Vasudevan Jan 19 '14 at 23:24

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.