0
$\begingroup$

Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{βˆ—}$ and $𝑳_2 \subseteq 𝚺^{βˆ—}$ be two non-empty languages.

a. If $𝑳_𝟏 𝚺^{βˆ—} \neq 𝚺^{βˆ—}$ than what can we say about $L_1$.

b.Let $\Lambda \in L_1$ and $\Lambda \in L_2$. Show using axioms and theorems of languages that $𝑳_𝟏 𝚺^{βˆ—}𝑳_2 = 𝚺^{βˆ—}$

For (a), $\Lambda$ should not belong to $L_1$ but I do not know how to prove that.

For (b),we have to prove that $𝑳_𝟏 𝚺^{βˆ—}𝑳_2 \subseteq 𝚺^{βˆ—}$ and $ 𝚺^{βˆ—} \subseteq𝑳_𝟏 𝚺^{βˆ—}𝑳_2$ for equality to exist. We can also distinguish two cases, when $L = \Lambda $, then $\Lambda 𝚺^{βˆ—} \Lambda = 𝚺^{βˆ—}$, but how can we prove that when $L \neq \Lambda $

Any idea

$\endgroup$
1
  • 1
    $\begingroup$ By the way, the culture here is one question per post. Expect a response saying that. $\endgroup$ Feb 13, 2020 at 1:09

2 Answers 2

1
$\begingroup$

Hint:

You are right on (a). The proof involves key results for Kleene star as follows. $$ \Sigma^{*}=\bigcup_{n\geqslant1}\Sigma^{n}\quad\text{and}\quad L\Sigma^{*}=\bigcup_{n\geqslant1}L\Sigma^{n}\quad\text{and}\quad \Sigma^{*}L=\bigcup_{n\geqslant1}\Sigma^{n}L $$ Where $\Sigma^{n}$ can be considered as the set of the concatenation of i strings in $\Sigma$, and $L\subset \Sigma^{*}$.

For (a), $L_1\Sigma^{*}\subset\Sigma^{*}$ since for all $n,L_1\Sigma^{n}\subset\Sigma^{n}$. If $\Lambda\in L_1$, then $n,L_1\Sigma^{n}=\Sigma^{n}$ for all $n$. Thus $L_1\Sigma^{*}=\Sigma^{*}$.

For (b), notice that if $\Lambda\in L_1$ and $L_2$, then $L_1\Sigma^{*}=\Sigma^{*}$ and $\Sigma^{*}L_2=\Sigma^{*}$. Thus $L_1\Sigma^{*}L_2=\Sigma^{*}L_2=\Sigma^{*}$.

$\endgroup$
0
$\begingroup$

You already have part of the answer for (a), but there's a bit more. For example, if $L_1 = \{a\}$ (and $\Sigma$ isn't just $a$) we certainly don't have $L_1\Sigma^* = \Sigma^*$. Can you come up with an extension? I knew you could.

$\endgroup$

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.