Tema 2: Lenguajes regulares

Idea de autómata

Autómatas finitos y gramáticas regulares

b

• Autómatas finitos deterministas

a

p

• Autómatas finitos no deterministas

q

a

b

• Gramáticas regulares (y lineales) a la derecha a

Expresiones regulares • Expresiones regulares

a

b

a

b

a

a

b

p

1

a

b

a

b

p

a

b

p

3

• Autómatas finitos no deterministas con transiciones vacías

a

5

q

q

q

Propiedades de los lenguajes regulares • Minimización de autómatas

a

a

b

a

b

a

• Algunas propiedades de cierre 2

• Lenguajes no regulares

Tema 2: Lenguajes regulares

1

6 q

•

•

•

conjunto de estados

Fuente de entrada

Σ

alfabeto de entrada

a

b

p

q

M = (Q, Σ, δ, δ q0, F) con δ : Q × Σ  → Q

b p

a a

Ciclo-máquina: Consultas: estado actual y símbolo de entrada Acciones: avance en la entrada y cambio de estado

q

b

Este autómata es: M = ({p,q}, {a,b}, δ, p, {q}) con δ definida:

Elementos distinguidos para la inicialización y salida: q0 ∈ Q: estado inicial y F ⊆ Q: conjunto de estados finales

δ(p,a) = q δ(p,b) = p δ(q,a) = p δ(q,b) = q

Definición formal: M = (Q, Σ, δ, q0, F) con δ : Q × Σ  → Q (función parcial) Tema 2: Lenguajes regulares

b

2

Com ponentes lógicos Q

a

Tema 2: Lenguajes regulares

Formalmente: Unidad de Proceso

a

b

Ejemplo de AFD

Elementos: Com ponentes físicos

a

4

Autómata finito determinista (AFD) •

b

p

p

q

Aplicaciones

a

3

Tema 2: Lenguajes regulares

4

Lenguaje aceptado por un AFD

Ejemplo de AFD a

•

•

•

Configuración: (q, w) ∈ Q ×Σ* q es el estado actual y w la palabra que queda por leer Movimiento:

a

b

a

a

b

p

a

2

a

a

b

a

a

b

a

p

q

a

b

a

a

b

p

p

b

5 q

b

a

4

6 q

a

b

a

b

p

q

(p, aabab) | (q, abab) | (p, bab) | (p, ab) | (q, b) | (q,ε) δ(p,a) = q 5

Función de transición extendida

δ(q,a) = p

δ(p,b) = p

δ(p,a) = q

δ(q,b) = q

Tema 2: Lenguajes regulares

6

Ejemplo de lenguaje aceptado Dado un AFD M = (Q, Σ, δ, δ q0, F), el lenguaje que acepta es L(M) = { w∈Σ*: (q0,w) | * (p, ε) ∧ p∈F } = { w∈Σ*: δ*(q0, w)∈ F }

Función de transición extendida a palabras δ*: Q ×∑*  → Q ∀ w∈ Σ*, ∀s ∈ Σ, ∀ q ∈ Q δ*(q, w) = estado en que se encuentra M tras leer la palabra w desde q

Para el AFD M = ({p,q}, {a,b}, δ, p, {q})

b

- δ* (q, ε) = q - δ* (q, ws) = δ (δ δ* (q, w), s)

p

a a

Lenguaje aceptado por M:

q

b

L(M) = { a, bab, aaa, aaba, aabba, abbbabab,.... } = { w∈{a,b}*: el número de a’s en w es impar }

L(M) = { w∈Σ*: δ*(q0, w)∈ F }

Tema 2: Lenguajes regulares

b

p

q

( | * denota 0 ó más pasos de | )

•

a

3 q

Lenguaje aceptado por el autómata M: L(M) = { w∈Σ*: (q0,w) | * (p,εε) ∧ p∈F }

•

b

1

cambio de configuración en un paso (s∈Σ) (p, s.w) |  (q, w) si y solo si δ(p,s) = q

Tema 2: Lenguajes regulares

a

7

Tema 2: Lenguajes regulares

8

Autómata finito determinista totalmente especificado (AFDt) •

Ejemplo: AFD a AFDt

Autómata totalmente especificado AFDt

AFD M = (Q, Σ, δ, δ q0, F) con δ : Q × Σ  → Q f. parcial

Es un AFD cuya función de transición es total M = (Q, Σ, δ, δ q0, F) •

con δ : Q×Σ ×Σ

b

δ(p,c) = indefinido δ(q,b) = indefinido

Q

p

∪{s}, Σ, δ’, ∪{s} × Σ → Q∪ ∪{s} f. total AFDt N = (Q∪ δ q0, F) con δ’ : Q∪

M y N son equivalentes si L(M) = L(N)

Los AFDts y los AFDs son equivalentes: L(AFDt) = L(AFD)

[⊇ ⊇]

b

tal que

PROPOSICIÓN 1:

[⊆ ⊆]

q

a

Autómatas equivalentes

Dem:

c

a

L(M) = L(N)

a c

Todo AFDt es un AFD

s

Para cada AFD existe un AFDt (con un estado “trampa”) equivalente.

Tema 2: Lenguajes regulares

9

c

a

p

q b a,b,c

Tema 2: Lenguajes regulares

10

Autómata finito no determinista (AFND)

Ejemplo de AFND

• Definición formal: M = (Q, Σ, δ, q0, F) con δ : Q × Σ → ℘(Q ) • Función de transición extendida:

a q0

δ* : Q × Σ* → ℘(Q )

δ * ( q , ε ) = {q} y δ * ( q , ws ) =

a

U δ ( p, s ) p∈δ * ( q , w )

(q, w) ∈ Q × Σ *

•

Configuración:

•

Movimiento:

•

Lenguaje aceptado:

Tema 2: Lenguajes regulares

(p, s.w) |— (q, w) si y solo si q ∈δ(p, s) L(M) = { w∈Σ*: δ *(q0, w) ∩ F ≠∅ } 11

q1 q2

b c

δ(q0, a) = {q1, q2}

δ(q0, b) = ∅

δ(q0, c) = ∅

δ(q1, a) = ∅

δ(q1, b) = {q1}

δ(q1, c) = ∅

δ(q2, a) = ∅

δ(q2, b) = ∅

δ(q2, c) = {q2}

Tema 2: Lenguajes regulares

12

Gramáticas regulares a la derecha (GRD)

Relación entre AFND y AFD PROPOSICIÓN 2:

L(AFD) ⊆ L(AFND)

•

Elementos:

Los lenguajes reconocidos por los autómatas finitos deterministas son reconocidos por los autómatas finitos no deterministas. DEMOSTRACIÓN:
Dado un AFD M = (Q, Σ, δ, q0, F), construimos el AFND

C o m p o n en te s N

c o n ju n to d e n o te rm in a le s

F u en te d e en tra d a

Σ

a lfab e to d e te rm in ale s

•

Elementos distinguidos para la inicialización: S∈ ∈N símbolo inicial

•

Ciclo-generativo: Búsqueda de subpalabra: lado izquierdo de una regla

M’ = (Q, Σ, γ, q0, F) con γ (q,s) = { δ(q,s) } ∀q∈Q, ∀s∈Σ

Acciones: sustituir por lado derecho.


Los autómatas M y M’ son equivalentes: L(M) = L(M’)

•

Pasos de la demostración:

con N∩ ∩Σ=∅ y S∈ ∈N

Definición formal: G = (N, ∑, S, P)

con P (conjunto de reglas o producciones) de la forma:

1)

γ*(q,x) = { δ*(q,x) } ∀q∈Q, ∀x∈Σ*

2)

x∈L(M) ⇔ x∈L(M’)

A → aB con A,B∈ ∈N, a∈ ∈∑

A→ε

Tema 2: Lenguajes regulares

13

Tema 2: Lenguajes regulares

14

Gramáticas regulares a la derecha (GRD) •

C o m p o n en te s fo r m a le s

C a te g o ria s

Ejemplo de GRD G = (N, ∑, S, P), con N = {S,A,B}, ∑ = {a,b,c} y siendo P el conjunto

Derivación:

de reglas:

δ 1 ⇒ δ 2 si y sólo si δ 1 = σ 1 A σ 2 , δ 2 = σ 1 βσ •

y A → β ∈P

S → aA | aB

Forma sentencial: *

α ∈ ( Σ ∪ N ) * tal que S ⇒ α G

•

2

B → cB | ε

Ejemplos de derivaciones:

*

(donde ⇒ denota 0 ó más pasos de ⇒ ) S ⇒ aA ⇒ abA ⇒ abbA ⇒ abb

Lenguaje generado por G:

S ⇒ aB ⇒ acB ⇒ ac

*

L (G ) = { w ∈ Σ * : S ⇒ w}

¿Lenguaje generado por G?

G

Tema 2: Lenguajes regulares

A → bA | ε

15

Tema 2: Lenguajes regulares

16

Gramáticas lineales a la derecha (GLD) 

Relación entre GRD y GLD

Definición formal: G = (N, ∑, S, P) con N∩ ∩Σ=∅ y S∈ ∈N donde el conjunto P de reglas o producciones es de la forma: A → wB con A,B∈ ∈N, w∈ ∈∑+, u∈ ∈∑* A→u

Algoritmo que transforma una GLD en una GRD equivalente: ENTRADA: GLD G = (N, Σ, A0, P) GRD G’ = (N∪N’, Σ, A0, P’)

SALIDA:

→ awB (ó equiv. A→ → aw) con w ≠ ε se crea un
Para cada A→ símbolo no terminal Z∈N’ y cambiamos la regla por 2 reglas:

PROPOSICIÓN 3:

A→ → aZ y Z→ → wB (ó equiv. Z→ → w)

Las GRDs y las GLDs son equivalentes: L(GRD) = L(GLD) Dem:

[⊆ ⊆]

Toda GRD es una GLD

[⊇]

Para cada GLD se construye una GRD equivalente,


Para cada A→ → a con a∈Σ ∈Σ se crea un símbolo no terminal Z∈N’ y cambiamos la regla por 2 reglas: A→ → aZ y Z→ →ε

mediante el siguiente algoritmo:


Continuar el proceso mientras haya reglas que reemplazar. Tema 2: Lenguajes regulares

17

Tema 2: Lenguajes regulares

Ejemplo: GLD a GRD

Relación entre GRD y AFD PROPOSICIÓN 4:

Ejemplo de transformación de una GLD en una GRD equivalente: ENTRADA:

SALIDA:

B→d|ε

Tema 2: Lenguajes regulares

DEMOSTRACIÓN: 1) Crear un algoritmo que produzca una GRD equivalente a un AFD M:

GRD G’ = ({A,B,C,D,E}, {a,b,c,d}, A, P’) siendo P’: A → aC

C → bcB C → bD

D → cB

B → dE | ε

E→ ε

L(AFD) ⊆ L(GRD)

Los lenguajes reconocidos por los autómatas finitos deterministas son generados por las gramáticas regulares a la derecha.

GLD G = ({A,B}, {a,b,c,d}, A, P) siendo P: A → abcB

18

•

ENTRADA: AFD M = (Q, Σ, δ, q0, F) con Q = {q0, q1, ..., qm}.

•

SALIDA:

GRD G = (N, Σ, A0, P)

2) Probar que M y G son equivalentes: L(M)=L(G). 19

Tema 2: Lenguajes regulares

20

2) Demostración formal de la equivalencia

1) Construcción del algoritmo •

Sea N = { A0, A1, ..., Am } donde Ai se corresponde con el estado qi

•

Sea P = { Ai → sAj : δ(qi, s) = qj } ∪ { Ai →ε : qi∈F }

•

La salida es G = (N, Σ, A0, P)

a) Demostramos por inducción sobre k≥0 la siguiente propiedad: (qi, x) |—k— (qj, ε) ⇔

a

Gramática obtenida:

a

b q1

b

x∈L(M) ⇔ (q0, x) |—k— (qf, ε) con qf ∈F ⇔

A0 → aA0 | bA1 | ε

A0⇒k xAf y Af ε ∈P ⇔ A0⇒k xAf ⇒x ⇔

A1 → aA1 | bA2

b q2

A0⇒k+1 x

A2 → aA2 | bA0

a Tema 2: Lenguajes regulares

21

⇔

x∈L(G)

Tema 2: Lenguajes regulares

Relación entre GRD y AFND PROPOSICIÓN 5:

( x∈∑* )

b) A partir de la propiedad anterior podemos demostrar la equivalencia:

Ejemplo: q0

Ai ⇒k xAj

22

Relaciones estudiadas

L(AFND) = L(GRD)

Los lenguajes reconocidos por los autómatas finitos no deterministas son generados por gramáticas regulares a la derecha. Y viceversa.

Repaso de las proposiciones vistas hasta ahora:

DEMOSTRACIÓN: L(AFND) ⊆ L(GRD) Similar a la demostración de la Proposición 2. L(GRD) ⊆ L(AFND) Dar la vuelta a la demostración anterior.

EJEMPLO:

a

q0 a Tema 2: Lenguajes regulares

q1 q2

b c

L(AFDt) =(1) L(AFD) ⊆ (2) L(AFND) =(5) L(GRD) =(3) L(GLD) ⊆ (4)

S → aA | aB A → bA | ε B → cB | ε 23

Tema 2: Lenguajes regulares

24