[Solved]: Prove that A* is the smallest reflexive and transitive set containing A

Problem Detail: 

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?

Asked By : Srinivas Vasudevan

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19820

3.2K people like this

 Download Related Notes/Documents