[2020] [Parcial Integrador] [Ejercicio 4] Pumping lemma versión 1

[2020] [Parcial Integrador] [Ejercicio 4] Pumping lemma versión 1

de Ignacio Daniel Vigna López -
Número de respuestas: 2

Buenas, haciendo ejercicios de exámenes me surge la siguiente duda:

Por ejemplo, si yo quiero probar que el siguiente lenguaje no es regular:

{a^p.b^p / p > 0}, he visto que se considera la tira Z = a^N.b^N

Ahora bien, la duda va por el lado de que N es arbitrario, y en particular para un N=0 Z no pertenece a L.

¿Debería considerar entonces la tira a^(N+1).b^(N+1)?

La duda surge porque haciendo el ejercicio 4 del parcial integrador del curso 2020, el cual les dejo el enlace:

https://eva.fing.edu.uy/pluginfile.php/263012/mod_folder/content/0/2020/ST-Parcial_Integrador_2020.pdf?forcedownload=1

yo había decidido tomar la tira Z= 1.0^(2N).(01)^(2N-1) pero claro, cuando N vale 0, la tira no pertenece al lenguaje. En cambio en la solución ustedes toman la tira:

Z=1.0^(2N+2).(01)^(2N+1) que es casi lo mismo, pero ahora para N igual cero, vale.

Muchas gracias


En respuesta a Ignacio Daniel Vigna López

[2020] [Parcial Integrador] [Ejercicio 4] Pumping lemma versión 1

de Diego Garat -

hola:

sí, lo correcto es asegurarte que los índices sean mayores o iguales a cero, porque las potencias negativas no existen en el universo de las tiras. esto es, si el valor pudiese ser menor a cero, el resultado no estaría definido. 

esto se arregla, o bien sumando algún natural ---a^(N+1).b^(N+1), 1.0^(2N+2).(01)^(2N+1)---, o bien tomando otra constante que sí lo cumpla, por ejemplo,  a^M b^M donde "M=max(N,...)"

creo que la primera opción es la más clara, pero a veces no hay más remedio que ir por la segunda. por ejemplo sea L={0^p / p es primo}. 

dado N, yo no puedo tomar z=0^N (porque N no es necesariamente primo)... así que debo elegir z=0^M tal que M es primo, M>=N (que sé que existe pues los primos son infinitos).


saludos,

d.-