Automatas

Propiedades de LR

1

0.1.

Propiedades de los lenguajes regulares Lema del bombeo

0.1.1.

Para todo lenguaje regular L (sobre un alfabeto Σ) existe una constante n ∈ N, llamada la constante del bombeo para L, tal que toda palabra w ∈ L, con | w |≥ n, satisface las siguiente propiedad: w se puede descomponer como w = uvx, con | uv |≤ n, v = y para todo i ≥ 0 se tiene uv ix ∈ L.

1.Tanto u como x pueden ser la cadena vac´ pero ıa, v= . 2. La palabra v ( o la parte central) se puede bombear cero o mas veces en el sentido de que uv ix es aceptada por L, ∀i ≥ 0.

2

Ra´l Ernesto Gutierrez de Pi˜erez u n

Ejemplo 1 Podemos usar el lema del bombeo para demostrar que el lenguaje L = {aibi : i ≥ 0} no es un lenguaje regular. Demostraci´n: Sea L es un lenguaje regular, enotonces existe una constante de bombeo n ∈ N. Sea w = anbn ∈ L, | w = anbn |≥ n. Descomponemos w = uvx, | v |≥ 1, | uv |≤ n u y v constan s´lo de as. o u = ar , r ≥ 0, v = as, s ≥ 1 w = anbn = uvx

Propiedades de LR

3

Entonces, anbn = ar asx x = an−r−sbn Ahora bombeamos v y se supone que uv ix ∈ L para i ≥ 0 sea i = 0 ux = ar an−r−sbn = an−sbn Por el lema del bombeo uv ix ∈ L para i ≥ 0. Enparticular si i = 0, ux ∈ L Pero ux = an−sbn ∈ L / y se concluye entonces que L no es regular. Ejemplo 2 El lenguaje de los pal´ ındromes sobre {a, b} no es un lenguaje regular. Demostraci´n. Por el lema del bombeo o 1. sea w = anban ∈ L donde n ∈ N es la constante del bombeo. 2. | v |≥ 1 y | uv |≤ n 3. ∀i ≥ 0, uv ix ∈ L

4

Ra´l Ernesto Gutierrez de Pi˜erez u n

u y v constan s´lo de as. ou = ar , r ≥ 0, v = as , s ≥ 1 w = anban = uvx Entonces, anban = ar asx x = an−r−sban Ahora bombeamos v y se supone que uv ix ∈ L para i ≥ 0 sea i = 2 uv 2x = ar asasan−r−sban = an+sban Por el lema del bombeo uv ix ∈ L para i ≥ 0. En particular si i = 2, uv 2x ∈ L. Pero uv 2x = an+sban ∈ L y se concluye entonces que L no es / regular.

Propiedades de LR

5

0.1.2.

Propiedades de clausurade los Lenguajes regulares

Teorema 1 Sean M, M1 y M2 aut´matas finitos (AF N − , o AF N, AF D) y L(M ) = L, L(M1) = L1 y L(M2) = L2 se pueden construir aut´matas finitos para los o siguientes lenguajes: 1. L1 ∪ L2 (uni´n finita de LR) o 2. L1L2 3. L∗ 4. L+ 5. L1 ∩ L2 6. L = Σ∗ − L 7. L1 − L2 8. L1 L2 Observaci´n 1 o La uni´n infinita de lenguajes regulares no neo cesariamente es regular. L = {anbn: n ≥ 1} = {aibi}
i≥1

Cada {aibi} es regular. Pero L no lo es.

6

Ra´l Ernesto Gutierrez de Pi˜erez u n

Todo lenguaje finito es regular. Teorema 2 Si L es un lenguaje regular sobre Σ, entonces L = Σ∗ − L es un lenguaje regular y se construye. 1. Sea L = L(M ) para un AFD M = (Q, Σ, q0, T, δ) 2. Entonces L = L(M ) donde M el AFD M = (Q, Σ, q0, Q − T, δ) 3. L(M ) = L(M ) donde losestados de aceptaci´n o de M se transforman en estados de no aceptaci´n en M y viceversa. o 4. w ∈ L(M ) sii δ(q0, w) ∈ Q − T , entonces w ∈ / L(M ) Ejemplo 3 Obtener el complemento del siguiente aut´mata. o

El AFN y AFD reconocen (1 + 0)∗01, ´ste es el e aut´mata complementario o

Propiedades de LR

7

Ejemplo 4 Demostrar que L = {aibj : i, j ≥ 0, i = j} No es regular. Suponemos que L esregular entonces a∗b∗ −L debe ser regular. a∗b∗ − L = {aibi : i ≥ 0} Teorema 3 Si L1 y L2 son lenguajes regulares, tambi´n lo es e L1 ∩ L2 . Demostraci´n. Sean L1 = L(M1) y L2 = L(M2) o donde M 1 = (Σ, Q1, q1, T1, δ1) y M 2 = (Σ, Q2, q2, T2, δ2). Entonces construimos: M = (Σ, Q1 × Q2, (q1, q2), T1 × T2, δ)

8

Ra´l Ernesto Gutierrez de Pi˜erez u n

donde δ : Q1 × Q2 × Σ → Q1 × Q2 δ((qi, qj ),a) = (δ1(qi, a), δ2(qj , a)) Satisface que L(M ) = L(M1) ∩ L(M2). Demostraci´n. Sea w ∈ Σ∗ o w ∈ L(M ) ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ δ((q1, q2), w) ∈ T1 × T2 (δ1(q1, w), δ2(q2, w)) ∈ T1 × T2 δ1(q1, w) ∈ T1 & δ2(q2, w) ∈ T2 w ∈ L(M1) & w ∈ L(M2) w ∈ L(M1) ∩ L(M2)

Ejemplo 5 Construir el AFD que acepte el lenjuaje L de todas las palabras sobre Σ = {a, b} que tienen un n´mero u par de a’s y un n´mero par de...