- #1

evinda

Gold Member

MHB

- 3,836

- 0

**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?