Edición de «Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 34: | Línea 34: | ||
''h) {x<math>\in</math>{0, 1}*/x = x^r}'' | ''h) {x<math>\in</math>{0, 1}*/x = x^r}'' | ||
<br>Sup. L regular -> Sea a=0,b=1, w=a^k.b^k <math>\in</math>L. Por lema de bombeo -> <math>\exists</math> x,y,z | xyz=w y |xy|≤k y <math>\forall</math> n, x.y^n.z<math>\in</math>L. Como w=a^k.b^k y |xy|≤k -> x | <br>Sup. L regular -> Sea a=0,b=1, w=a^k.b^k <math>\in</math>L. Por lema de bombeo -> <math>\exists</math> x,y,z | xyz=w y |xy|≤k y <math>\forall</math> n, x.y^n.z<math>\in</math>L. Como w=a^k.b^k y |xy|≤k -> x y y están compuestas sólo de a´s -> podemos decir que: α=a^t, β=a^s, ρ=a^[k-(s+t)].b^k, donde 1≤ s+t ≤ k y s ≥ 1. Entonces <math>\forall</math> n, α.β^n.ρ<math>\in</math>L equivale a <math>\forall</math> n, t+ns+k-(s+t)=k. Sin embargo tomando n=0, t+ns+k-(s+t) = t+k-(s+t) = k -> s = 0. Pero s >= 1 (ABS) -> L no es regular. | ||
------ No entiendo por que 01 = (01)^r = 10, me parece q hay un error en algun lado | ------ No entiendo por que 01 = (01)^r = 10, me parece q hay un error en algun lado |