Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Languages math problem

  1. Jan 27, 2010 #1
    1. The problem statement, all variables and given/known data
    If L is a language over [tex]\Sigma[/tex] then lim n -> inf of Ln = [tex]\Sigma[/tex]* iff ([tex]\Sigma[/tex][tex]\cup[/tex]{[tex]\lambda[/tex]})[tex]\subseteq[/tex] L

    Also Lk = {x1x2...xk | x1, x2, ...xk [tex]\in[/tex] L}

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Jan 28, 2010 #2
    Re: Languages

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

    If [tex]L[/tex] does not contain the empty string [tex]\epsilon[/tex], then it is not true that [tex]L \subset L^2 \subset L^3 \subset \cdots[/tex], because the shortest string in [tex]L^n[/tex] has length [tex]n[/tex] times the length of the shortest string in [tex]L[/tex]. In this case, you therefore cannot use [tex]\lim_{n\to\infty} L^n = \bigcup_{n=0}^\infty L^n[/tex] as a definition. You can even construct a case (say, [tex]L = \Sigma[/tex]) where the [tex]L^n[/tex] are pairwise disjoint!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook