Mixing
![How to deal with constant anxiety about job security [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjbpfN9tAutmK93bJRC3ZoROZzi2TJDms5n8_qJuhgE0a9b52OOHayv3NGT8igAdFL7byXNst-_1DZK5SjrIJ28_6RQPUpBROqMs5s6jo-ZsjX8kjDwfxJufIitH3TaQRXWaGSQKRQib-f/s72-c/1.jpg)
Prove that A** = A*, where A is a language over Σ*
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let $mathcal A$ be an arbitrary language over $Sigma^*$
Proof.
To prove, $mathcal A^** = mathcal A^* $
$mathcal A^** = left( mathcal A^0 cup mathcal A^1 cup ... cup mathcal A^n right)^*$ by definition of Kleene Star
My idea is that kleene star distribute over the union of the languages but then, I dont know what's next.
I need some directions
regular-languages automata proof-techniques
asked 4 hours ago
Mustafa Ali Saba
132
add a comment |Â
up vote
1
down vote
favorite
Let $mathcal A$ be an arbitrary language over $Sigma^*$
Proof.
To prove, $mathcal A^** = mathcal A^* $
$mathcal A^** = left( mathcal A^0 cup mathcal A^1 cup ... cup mathcal A^n right)^*$ by definition of Kleene Star
My idea is that kleene star distribute over the union of the languages but then, I dont know what's next.
I need some directions
regular-languages automata proof-techniques
asked 4 hours ago
Mustafa Ali Saba
132
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $mathcal A$ be an arbitrary language over $Sigma^*$
Proof.
To prove, $mathcal A^** = mathcal A^* $
$mathcal A^** = left( mathcal A^0 cup mathcal A^1 cup ... cup mathcal A^n right)^*$ by definition of Kleene Star
My idea is that kleene star distribute over the union of the languages but then, I dont know what's next.
I need some directions
regular-languages automata proof-techniques
asked 4 hours ago
Mustafa Ali Saba
132
Let $mathcal A$ be an arbitrary language over $Sigma^*$
Proof.
To prove, $mathcal A^** = mathcal A^* $
$mathcal A^** = left( mathcal A^0 cup mathcal A^1 cup ... cup mathcal A^n right)^*$ by definition of Kleene Star
My idea is that kleene star distribute over the union of the languages but then, I dont know what's next.
I need some directions
regular-languages automata proof-techniques
regular-languages automata proof-techniques
asked 4 hours ago
Mustafa Ali Saba
132
asked 4 hours ago
Mustafa Ali Saba
132
asked 4 hours ago
Mustafa Ali Saba
132
asked 4 hours ago
Mustafa Ali Saba
132
asked 4 hours ago
Mustafa Ali Saba
132
132
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
Since $L subseteq L^*$ for all $L$, we have $mathcalA^* subseteq mathcalA^**$. In the other direction, suppose that $w in mathcalA^**$. Then there exists an integer $n geq 0$ and words $x_1,ldots,x_n in mathcalA^*$ such that $w = x_1 x_2 ldots x_n$. Since $x_i in mathcalA^*$, there exists an integer $m_i$ such that $x_i in mathcalA^m_i$. Thus $w in mathcalA^m_1 + cdots + m_n subseteq mathcalA^*$, and it follows that $mathcalA^** subseteq mathcalA^*$.
answered 4 hours ago
Yuval Filmus
183k12171332
add a comment |Â
up vote
0
down vote
Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.
The inclusion $L subseteq L^*$ always holds, so $mathcal A^* subseteq mathcal A^**$.
We are left with proving $mathcal A^** subseteq mathcal A^*$. For this, recall that $L^*$ can be defined as the least language such that
$$
epsilon cup LL^* = L^*
$$
Hence, $mathcal A^**$ is the least language such that
$$
epsilon cup mathcal A^* mathcal A^** = mathcal A^**
$$
so, if we prove that $mathcal A^*$ also satisfies the same property, i.e. if we prove
$$
epsilon cup mathcal A^* mathcal A^* = mathcal A^*
qquad (*)
$$
by the minimality of $mathcal A^**$, we will obtain the wanted
$mathcal A^** subseteq mathcal A^*$.
Proving $(*)$ is then trivial.
answered 5 mins ago
chi
10.7k1628
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Since $L subseteq L^*$ for all $L$, we have $mathcalA^* subseteq mathcalA^**$. In the other direction, suppose that $w in mathcalA^**$. Then there exists an integer $n geq 0$ and words $x_1,ldots,x_n in mathcalA^*$ such that $w = x_1 x_2 ldots x_n$. Since $x_i in mathcalA^*$, there exists an integer $m_i$ such that $x_i in mathcalA^m_i$. Thus $w in mathcalA^m_1 + cdots + m_n subseteq mathcalA^*$, and it follows that $mathcalA^** subseteq mathcalA^*$.
answered 4 hours ago
Yuval Filmus
183k12171332
add a comment |Â
up vote
2
down vote
Since $L subseteq L^*$ for all $L$, we have $mathcalA^* subseteq mathcalA^**$. In the other direction, suppose that $w in mathcalA^**$. Then there exists an integer $n geq 0$ and words $x_1,ldots,x_n in mathcalA^*$ such that $w = x_1 x_2 ldots x_n$. Since $x_i in mathcalA^*$, there exists an integer $m_i$ such that $x_i in mathcalA^m_i$. Thus $w in mathcalA^m_1 + cdots + m_n subseteq mathcalA^*$, and it follows that $mathcalA^** subseteq mathcalA^*$.
answered 4 hours ago
Yuval Filmus
183k12171332
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Since $L subseteq L^*$ for all $L$, we have $mathcalA^* subseteq mathcalA^**$. In the other direction, suppose that $w in mathcalA^**$. Then there exists an integer $n geq 0$ and words $x_1,ldots,x_n in mathcalA^*$ such that $w = x_1 x_2 ldots x_n$. Since $x_i in mathcalA^*$, there exists an integer $m_i$ such that $x_i in mathcalA^m_i$. Thus $w in mathcalA^m_1 + cdots + m_n subseteq mathcalA^*$, and it follows that $mathcalA^** subseteq mathcalA^*$.
answered 4 hours ago
Yuval Filmus
183k12171332
Since $L subseteq L^*$ for all $L$, we have $mathcalA^* subseteq mathcalA^**$. In the other direction, suppose that $w in mathcalA^**$. Then there exists an integer $n geq 0$ and words $x_1,ldots,x_n in mathcalA^*$ such that $w = x_1 x_2 ldots x_n$. Since $x_i in mathcalA^*$, there exists an integer $m_i$ such that $x_i in mathcalA^m_i$. Thus $w in mathcalA^m_1 + cdots + m_n subseteq mathcalA^*$, and it follows that $mathcalA^** subseteq mathcalA^*$.
answered 4 hours ago
Yuval Filmus
183k12171332
answered 4 hours ago
Yuval Filmus
183k12171332
answered 4 hours ago
Yuval Filmus
183k12171332
answered 4 hours ago
Yuval Filmus
183k12171332
183k12171332
add a comment |Â
add a comment |Â
up vote
0
down vote
Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.
The inclusion $L subseteq L^*$ always holds, so $mathcal A^* subseteq mathcal A^**$.
We are left with proving $mathcal A^** subseteq mathcal A^*$. For this, recall that $L^*$ can be defined as the least language such that
$$
epsilon cup LL^* = L^*
$$
Hence, $mathcal A^**$ is the least language such that
$$
epsilon cup mathcal A^* mathcal A^** = mathcal A^**
$$
so, if we prove that $mathcal A^*$ also satisfies the same property, i.e. if we prove
$$
epsilon cup mathcal A^* mathcal A^* = mathcal A^*
qquad (*)
$$
by the minimality of $mathcal A^**$, we will obtain the wanted
$mathcal A^** subseteq mathcal A^*$.
Proving $(*)$ is then trivial.
answered 5 mins ago
chi
10.7k1628
add a comment |Â
up vote
0
down vote
Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.
The inclusion $L subseteq L^*$ always holds, so $mathcal A^* subseteq mathcal A^**$.
We are left with proving $mathcal A^** subseteq mathcal A^*$. For this, recall that $L^*$ can be defined as the least language such that
$$
epsilon cup LL^* = L^*
$$
Hence, $mathcal A^**$ is the least language such that
$$
epsilon cup mathcal A^* mathcal A^** = mathcal A^**
$$
so, if we prove that $mathcal A^*$ also satisfies the same property, i.e. if we prove
$$
epsilon cup mathcal A^* mathcal A^* = mathcal A^*
qquad (*)
$$
by the minimality of $mathcal A^**$, we will obtain the wanted
$mathcal A^** subseteq mathcal A^*$.
Proving $(*)$ is then trivial.
answered 5 mins ago
chi
10.7k1628
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.
The inclusion $L subseteq L^*$ always holds, so $mathcal A^* subseteq mathcal A^**$.
We are left with proving $mathcal A^** subseteq mathcal A^*$. For this, recall that $L^*$ can be defined as the least language such that
$$
epsilon cup LL^* = L^*
$$
Hence, $mathcal A^**$ is the least language such that
$$
epsilon cup mathcal A^* mathcal A^** = mathcal A^**
$$
so, if we prove that $mathcal A^*$ also satisfies the same property, i.e. if we prove
$$
epsilon cup mathcal A^* mathcal A^* = mathcal A^*
qquad (*)
$$
by the minimality of $mathcal A^**$, we will obtain the wanted
$mathcal A^** subseteq mathcal A^*$.
Proving $(*)$ is then trivial.
answered 5 mins ago
chi
10.7k1628
Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.
The inclusion $L subseteq L^*$ always holds, so $mathcal A^* subseteq mathcal A^**$.
We are left with proving $mathcal A^** subseteq mathcal A^*$. For this, recall that $L^*$ can be defined as the least language such that
$$
epsilon cup LL^* = L^*
$$
Hence, $mathcal A^**$ is the least language such that
$$
epsilon cup mathcal A^* mathcal A^** = mathcal A^**
$$
so, if we prove that $mathcal A^*$ also satisfies the same property, i.e. if we prove
$$
epsilon cup mathcal A^* mathcal A^* = mathcal A^*
qquad (*)
$$
by the minimality of $mathcal A^**$, we will obtain the wanted
$mathcal A^** subseteq mathcal A^*$.
Proving $(*)$ is then trivial.
answered 5 mins ago
chi
10.7k1628
answered 5 mins ago
chi
10.7k1628
answered 5 mins ago
chi
10.7k1628
answered 5 mins ago
chi
10.7k1628
10.7k1628
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f98151%2fprove-that-a-a-where-a-is-a-language-over-%25ce%25a3%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
