Skip to main content
Computer Science

Return to Question

deleted 11 characters in body; edited tags
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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

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?

Thanks!

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?

Thanks!

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?

Tweeted twitter.com/#!/StackCompSci/status/424892075893850112
Source Link
Srinivas Vasudevan
Srinivas Vasudevan
  • 55
  • 5

Prove that A* is the smallest reflexive and transitive set containing A

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?

Thanks!