⟸ pàgina anterior ⟸

Exercici 4 (Tasca 3).

(pumping lemma, hard exercise)

Palíndroms i palíndroms parcials

1. Demostreu que el llenguatge \{w\in \{a,b\}^* \mid w=w^R\} no és regular.

2. Demostreu que el llenguatge \{ww^R\mid w\in \{a,b\}^*\} no és regular.

3. Demostreu que el llenguatge \{ww\mid w\in \{a,b\}^*\} no és regular.

4. (difícil) Demostreu que el llenguatge \{ww^Rx\mid w,x\in \{a,b\}^+\} no és regular.

   Precaució

   En aquest últim punt, el lema de bombament no permet demostrar la no regularitat. Per què?

   Ajut

   Suposeu, per arribar a contradicció, que el llenguatge és regular i existeix un DFA de N estats que el reconeix. Comproveu el comportament de l’autòmat amb tots els mots w_i=aba^2b^2\cdots a^ib^i, per a i=1,2,\dots, N+1.