Diferencia entre revisiones de «Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)»
Sin resumen de edición |
|||
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== |
Revisión del 14:47 7 may 2008
Propiedades
- Lema de pumping: Si L es regular -> Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists}
n tq Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall}
w Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in}
L, |w|>=n, w se puede separar en w=xyz tq:
- y≠λ, |xy|<=n, y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall} k>=0, x.y^k.z Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in} L.
Ejercicio 01
Ejercicio 02
Ejercicio 03
Ejercicio 04
Ejercicio 05
c) {0^n/n es un numero primo }
Sup. L regular -> Sea a=0. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists}
α, β,γ Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in}
a*,β≠λ | Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall}
n, α.β^n.γError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in}
L. Sean: α=a^p, β=a^q, γ=a^r. Como β≠λ -> q≥1. Se debe cumplir que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall}
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
e) {x{0, 1}*/x tiene igual cantidad de ceros que de unos}
Sup. L regular -> Sea s = 0^p.1^p L y |s| > p. Por el lema de bombeo x,y,z | x.y^i.z L i ≥ 0. Sea x = λ y z = λ, en este caso, xyz L, pero se requiere |xy| ≤ p (ABS) -> L NO es regular.
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 ωError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in}
L -> (2.5) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists}
α, β, ρ | αβρ=ω y |αβ|≤k y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall}
n, αβ^nρError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in}
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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall}
n, α.β^n.ρError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in}
L equivale a decir que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall}
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.