Diferencia entre revisiones de «Práctica 4: Lenguajes regulares y lema de pumping (Teoría de Lenguajes)»
De Cuba-Wiki
Sin resumen de edición |
|||
| (No se muestran 2 ediciones intermedias del mismo usuario) | |||
| Línea 1: | Línea 1: | ||
{{Back|Teoría de Lenguajes}} | |||
==Ejercicio 01== | ==Ejercicio 01== | ||
==Ejercicio 02== | ==Ejercicio 02== | ||
| Línea 4: | Línea 6: | ||
==Ejercicio 04== | ==Ejercicio 04== | ||
==Ejercicio 05== | ==Ejercicio 05== | ||
<br>c) 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 para todo n, p+nq+r es primo. Sea n=(p+2q+r+2) -> p+nq+r debe ser primo. | |||
<br>p+nq+r = p+(p+2q+r+2)q+r = p+pq+2q^2+rq+2q+r = (q+1)(p+2q+r) es primo. Pero q≥1 -> q+1 ≥ 2 y (p+2*1+r) ≥ 2〉 = FALSO -> L NO es regular | |||
[[Category:Prácticas]] | |||
Revisión del 03:33 7 may 2008
Ejercicio 01
Ejercicio 02
Ejercicio 03
Ejercicio 04
Ejercicio 05
c) Sup. L regular -> Sea a=0. αa*, β a*,γa*,β≠λ tq n, αβ^nγL. Sean: α=a^p, β=a^q, γ=a^r. Como β≠λ -> q≥1. Se debe cumplir que para todo 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. Pero q≥1 -> q+1 ≥ 2 y (p+2*1+r) ≥ 2〉 = FALSO -> L NO es regular
