Revisión actual |
Tu texto |
Línea 1: |
Línea 1: |
| {{Back|Teoría de Lenguajes}} | | {{Back|Teoría de Lenguajes}} |
|
| |
| ==Propiedades==
| |
| * Lema de pumping: Si L es regular -> <math>\exists</math> n tq <math>\forall</math> w <math>\in</math> L, |w|>=n, w se puede separar en w=xyz tq:
| |
| ** y≠λ, |xy|<=n, y <math>\forall</math> k>=0, x.y^k.z <math>\in</math> L.
| |
|
| |
|
| ==Ejercicio 01== | | ==Ejercicio 01== |
Línea 9: |
Línea 5: |
| ==Ejercicio 03== | | ==Ejercicio 03== |
| ==Ejercicio 04== | | ==Ejercicio 04== |
|
| |
| <br>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== | | ==Ejercicio 05== |
| ''a) {0^(2n)/n>=1}''
| |
| <br> 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}'' | | ''c) {0^n/n es un numero primo }'' |
| <br>Sup. L regular -> Sea a=0, w=1^p<math>\in</math>L. 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 <math>\in</math> 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. | | <br>Sup. L regular -> Sea a=0. <math>\exists</math> α<math>\in</math>a*, β <math>\in</math>a*,γ<math>\in</math>a*,β≠λ tq <math>\forall</math> n, α.β^n.γ<math>\in</math>L. Sean: α=a^p, β=a^q, γ=a^r. Como β≠λ -> q≥1. Se debe cumplir que <math>\forall</math>n, p+nq+r es primo. Sea n=(p+2q+r+2) -> p+nq+r debe ser primo -> p+nq+r = p+(p+2q+r+2)q+r = p+pq+2q^2+rq+2q+r = (q+1)(p+2q+r) es primo (ABS) -> L NO es regular |
| | |
| ''d) {x<math>\in</math>{0, 1}*/x no contiene 3 ceros consecutivos}''
| |
| <br> Sea L' = {x<math>\in</math>{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<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>Sea p la longitud de bombeo y sea s = 0^p.1^p <math>\in</math> L y |s| > p. Por el lema de bombeo <math>\exists</math>xyz = s tal que x.y^i.z <math>\in</math> L <math>\forall</math>i ≥ 0. Sea x = λ y z = λ, en este caso, xyz efectivamente pertenece a L, sin embargo, se requiere ademas que |xy| ≤ p (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}'' |
| <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 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 <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. | | <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 ρ tq αβρ=ω 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. |
| ------ 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<math>\in</math>{0, 1}*/x tiene cantidad par de ceros}''
| |
| <br>ER: (1*|01*0)* -> L es regular
| |
| | |
| ''j) {x<math>\in</math>{0, 1}*/x tiene cantidad par de ceros o impar de unos}''
| |
| <br>Sea L1 = {x<math>\in</math>{0, 1}*/x tiene cantidad par de ceros}, L2 = {x<math>\in</math>{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 <math>\cup</math> L2 -> L es regular.
| |
| | |
| ''k) {x<math>\in</math>{0, 1}*/x tiene cantidad par de ceros e impar de unos}''
| |
| <br> L = L1 <math>\cap</math> L2 (del ej. anterior) -> L es regular
| |
|
| |
|
| ''l) {x<math>\in</math>{0, 1}*/x tiene cantidad de ceros divisible por k}''
| |
| Es regular
| |
|
| |
|
| [[Category:Prácticas]] | | [[Category:Prácticas]] |