1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook