Diferencia entre revisiones de «Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)»
Línea 14: | 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}'' | ||
''c) {0^n/n es un numero primo}'' | ''c) {0^n/n es un numero primo}'' | ||
Línea 24: | Línea 23: | ||
''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. | ||
''f) {x<math>\in</math>{0, 1}*/x tiene dist. cantidad de ceros que de unos}'' | |||
''g) {x<math>\in</math>{0, 1}*/x tiene menor cantidad de ceros que de unos}'' | |||
''h) {x<math>\in</math>{0, 1}*/x = x^r}'' | ''h) {x<math>\in</math>{0, 1}*/x = x^r}'' | ||
Línea 29: | Línea 32: | ||
<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. | <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. | ||
''i) {x<math>\in</math>{0, 1}*/x tiene cantidad par de ceros}'' | |||
''j) {x<math>\in</math>{0, 1}*/x tiene cantidad par de ceros o impar de unos}'' | |||
''k) {x<math>\in</math>{0, 1}*/x tiene cantidad par de ceros e impar de unos}'' | |||
''l) {x<math>\in</math>{0, 1}*/x tiene cantidad de ceros divisible por k}'' | |||
[[Category:Prácticas]] | [[Category:Prácticas]] |
Revisión del 17:44 7 may 2008
Propiedades
- Lema de pumping: Si L es regular -> n tq w L, |w|>=n, w se puede separar en w=xyz tq:
- y≠λ, |xy|<=n, y k>=0, x.y^k.z L.
Ejercicio 01
Ejercicio 02
Ejercicio 03
Ejercicio 04
Ejercicio 05
a) {0^(2n)/n>=1}
L = { (00)^n/n>=1 }. La ER para este lenguaje es (00)+ -> L es regular.
b) {0^m.1^n.0^(m+n)/m,n>=1}
c) {0^n/n es un numero primo}
Sup. L regular -> Sea a=0, w=1^pL. Por lema de bombeo, se puede separar w=xyz tq y≠λ, |xy|<=n. Elijamos p>=n+2, y sea |y|=m<=n -> |xz|=p-m. Como y≠λ -> m≥1. Entonces xy^(p-m)z L,pero |xy^(p-m)z| = |xz|+(p-m)|y| = p-m+(p-m)m = (p-m)(m+1), el cual NO es primo, ya que m+1>1 y p-m>=p-n>=n+2-n>=2>1 (ABS) -> L NO es regular.
d) {x{0, 1}*/x no contiene 3 ceros consecutivos}
Sea L' = {x{0, 1}*/x contiene 3 ceros consecutivos}. La ER para este lenguaje es (0|1)*(000)(0|1)* -> L' es regular, y como L es el complemento de L' -> L tambien es regular.
e) {x{0, 1}*/x tiene igual cantidad de ceros que de unos}
Sup. L regular -> Sea s = 0^n.1^n L. Usando el lema de bombeo, sea el s=xyz tq y≠λ, |xy|<=n, k, x.y^kz L. Entonces xy solo tiene 0's, y ademas xz L, tiene <n 0's (porque y≠λ) y n 1's (ABS) -> L NO es regular.
f) {x{0, 1}*/x tiene dist. cantidad de ceros que de unos}
g) {x{0, 1}*/x tiene menor cantidad de ceros que de unos}
h) {x{0, 1}*/x = x^r}
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 ωL -> (2.5) α, β, ρ | αβρ=ω y |αβ|≤k y n, α.β^n.ρ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: αβρ=ω
Como no se hicieron suposiciones adicionales con respecto a las cadenas, decir que n, α.β^n.ρL equivale a decir que 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.
i) {x{0, 1}*/x tiene cantidad par de ceros}
j) {x{0, 1}*/x tiene cantidad par de ceros o impar de unos}
k) {x{0, 1}*/x tiene cantidad par de ceros e impar de unos}
l) {x{0, 1}*/x tiene cantidad de ceros divisible por k}