Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Propiedades[editar]

  • 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[editar]

Ejercicio 02[editar]

Ejercicio 03[editar]

Ejercicio 04[editar]


b) Como L es LR existe una GR lineal a derecha G = (N, T, P, S) tal que L = L(G). A partir de G es posible definir una gramática GR =(N, T, PR, S) tal que L(GR) = LR. donde PR = P con cada regla de producción de P de la forma A -> aB reemplazada por A -> Ba para A, B en N y a en T. Como L(GR) = LR -> LR es un lenguaje regular

Ejercicio 05[editar]

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, w=a^k.b^k L. Por lema de bombeo -> x,y,z | xyz=w y |xy|≤k y n, x.y^n.zL. Como w=a^k.b^k y |xy|≤k -> x e 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 n, α.β^n.ρL equivale a 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

EDIT: El problema, es que estas tomando a "r" como un nro, cuando se trata de la reversa, por eso la demostracion no sirve para el ejercicio, y por eso es que 01 = (01)^r = 10.

i) {x{0, 1}*/x tiene cantidad par de ceros}
ER: (1*|01*0)* -> L es regular

j) {x{0, 1}*/x tiene cantidad par de ceros o impar de unos}
Sea L1 = {x{0, 1}*/x tiene cantidad par de ceros}, L2 = {x{0, 1}*/x tiene cantidad impar de unos}. ER de L1: (1*|01*0)*, ER de L2: 0*1(0*|10*1)*. L1 y L2 son regulares, y como L=L1 L2 -> L es regular.

k) {x{0, 1}*/x tiene cantidad par de ceros e impar de unos}
L = L1 L2 (del ej. anterior) -> L es regular

l) {x{0, 1}*/x tiene cantidad de ceros divisible por k} Es regular