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 9: | Línea 9: | ||
==Ejercicio 03== | ==Ejercicio 03== | ||
==Ejercicio 04== | ==Ejercicio 04== | ||
==Ejercicio 05== | ==Ejercicio 05== | ||
''a) {0^(2n)/n>=1}'' | ''a) {0^(2n)/n>=1}'' | ||
Línea 19: | Línea 14: | ||
''b) {0^m.1^n.0^(m+n)/m,n>=1}'' | ''b) {0^m.1^n.0^(m+n)/m,n>=1}'' | ||
<br> Sea L1={0^m.1^n/m,n>=1} y L2={0^(m+n)/m,n>=1}. Las ER son 0+.1+ (para L1) y 0.0+ (para L2) -> L1 y L2 son regulares, y como L = L1.L2 -> L es regular. | |||
''c) {0^n/n es un numero primo}'' | ''c) {0^n/n es un numero primo}'' | ||
Línea 28: | Línea 24: | ||
''e) {x<math>\in</math>{0, 1}*/x tiene igual cantidad de ceros que de unos}'' | ''e) {x<math>\in</math>{0, 1}*/x tiene igual cantidad de ceros que de unos}'' | ||
<br>Sup. L regular -> Sea s = 0^n.1^n <math>\in</math> L. Usando el lema de bombeo, sea el s=xyz tq y≠λ, |xy|<=n, <math>\forall</math>k, x.y^kz <math>\in</math> L. Entonces xy solo tiene 0's, y ademas xz <math>\in</math> L, tiene <n 0's (porque y≠λ) y n 1's (ABS) -> L NO es regular. | <br>Sup. L regular -> Sea s = 0^n.1^n <math>\in</math> L. Usando el lema de bombeo, sea el s=xyz tq y≠λ, |xy|<=n, <math>\forall</math>k, x.y^kz <math>\in</math> L. Entonces xy solo tiene 0's, y ademas xz <math>\in</math> L, tiene <n 0's (porque y≠λ) y n 1's (ABS) -> L NO es regular. | ||
''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 | <br>Sup. L regular -> Sea a=0,b=1. Sup M es un autómata con k estados que lo reconoce. Sea ω=a^k.b^k. Es claro que ω<math>\in</math>L -> (2.5) <math>\exists</math> α, β, ρ | αβρ=ω y |αβ|≤k y <math>\forall</math> n, α.β^n.ρ<math>\in</math>L. Como ω=a^k.b^k y |αβ|≤k -> α y β están compuestas sólo de a´s. Por lo tanto, podemos decir que: α=a^t, β=a^s, ρ=a^[k-(s+t)].b^k, donde 1≤ s+t ≤ k y s ≥ 1. Es claro que: αβρ=ω | ||
<br>Como no se hicieron suposiciones adicionales con respecto a las cadenas, decir que <math>\forall</math> n, α.β^n.ρ<math>\in</math>L equivale a decir que <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. | |||
[[Category:Prácticas]] | [[Category:Prácticas]] |