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!