Proving the Equivalence of Languages over \Sigma: A Mathematical Approach

[ayusuf]

Homework Statement

If L is a language over $$\Sigma$$ then lim n -> inf of Lⁿ = $$\Sigma$$* iff ($$\Sigma$$$$\cup$${$$\lambda$$})$$\subseteq$$ L

Also L^k = {x₁x₂...x_k | x₁, x₂, ...x_k $$\in$$ L}

Homework Equations

The Attempt at a Solution

I started by saying there is an w is an element of sigma then it is also an element of L so I might use induction but I really don't even know if I started right. Thanks.

 

[ystael]

What is the definition of limit you use in the expression $$\lim_{n\to\infty} L^n$$?

If $$L$$ does not contain the empty string $$\epsilon$$, then it is not true that $$L \subset L^2 \subset L^3 \subset \cdots$$, because the shortest string in $$L^n$$ has length $$n$$ times the length of the shortest string in $$L$$. In this case, you therefore cannot use $$\lim_{n\to\infty} L^n = \bigcup_{n=0}^\infty L^n$$ as a definition. You can even construct a case (say, $$L = \Sigma$$) where the $$L^n$$ are pairwise disjoint!