1. Not finding help here? Sign up for a free 30min 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!

Show that languages are regular

  1. Dec 14, 2013 #1
    Show that languages are regular!!!

    1. The problem statement, all variables and given/known data
    Use the lemma:
    <<If the language L(A) of an automaton A has an infinite number of words,then there are words a,m,t ε Σ*,so that |at|≤|Σ_{k}|,and each word a m^{i}t,i≥0 is contained in L(A) >>(version of Pumping Lemma)and show that the following languages are not regular:
    a) L={ww^{R}:w ε {a,b}*} (w^{R}=the word w is written backwards)
    b)L={ww:w ε {a,b}*}

    P.S: Σ_{k} is the set of states.

    2. The attempt at a solution

    For the subquestion b,if we would have the original version of Pumping Lemma,we could take the word 0^{p}10^{p}1,where p is the pumping length.Can we also do this in our case?
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?