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?

Improve this question
$\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ė
    Commented Jan 19, 2014 at 8:29

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jan 19, 2014 at 23:24

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.