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
    $\begingroup$ By the way, the culture here is one question per post. Expect a response saying that. $\endgroup$ – Rick Decker Feb 13 at 1:09
0
$\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^{*}$.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.