Show that languages are regular

[evinda]

Show that languages are regular!

Homework Statement

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?

 

[Valkarie]

I don't think so,because the words that are written backwards are not taken in consideration.For the subquestion a,we can take the word 0^{p}10^{p}1,where p is the pumping length.Then,we get the following two words:a) 0^{p}10^{p}1b) 0^{p+1}10^{p-1}1Now,the first word is contained in L(A),but the second one is not,because it has an even number of b's.Therefore,the language is not regular.