Automatas

Lección 3: Lenguajes independientes del contexto
Gramáticas independientes de contexto (GIC) Conceptos básicos Ambigüedad Autómatas con pila (AP) Definición de autómata con pila Determinismo y no determinismo Formas normales Simplificación Forma normal de Greibach Equivalencia entre APs y GICs Propiedades y aplicaciones
1

Gramáticas independientes del contexto
•

Elementos:

C omponentes C ategorias Fu ente de entrada N Σ

C om ponentes form ales conju nto de no term inales alfabeto de term inales

•

Elementos distinguidos S ∈ N símbolo inicial Definición formal: G = (N, Σ, S, P) con α → β ∈ P, α ∈ N , β ∈ (N ∪ Σ )* Derivación: δ1, δ2, σ1, σ2, β ∈ (N ∪ Σ )* Α∈N δ1 ⇒ δ2 si y solo si δ1 = σ1Ασ2, δ2 = σ1βσ2 y Α → β ∈ P
* Lenguaje generado: L(G) = { w∈Σ*: S ⇒ w }
Lección3: GIC 2

•

•

•

Derivaciones y Árboles
•

•

Derivación a la izquierda: δ1, δ2, σ, β ∈ (N ∪ Σ )* Α ∈ N, w ∈ Σ* δ1 ⇒ δ2 si y solo si δ1 = wΑσ, δ2 = wβσ y Α → β ∈ P Árbol de derivación o árbol de análisis de G: Es un árbol etiquetado y ordenado tal que - Todo nodo está etiquetado con un símbolo de N ∪ Σ ∪ {ε} - La raíz es el símbolo inicial. - Los nodos internos están etiquetadoscon símbolos no terminales - Si un nodo está etiquetado con A y sus k hijos están etiquetados X1X2…Xk leídos de izquierda a derecha entonces la regla A → X1X2…Xk es una regla de la gramática. - Si un nodo está etiquetado con ε entonces es el único hijo de un nodo. - Si todas las hojas son símbolos terminales ó ε el árbol es completo y la frontera es una palabra de L(G).
Lección 3: GIC 3Ambigüedad

•

G es ambigua si existe x ∈L(G) con al menos dos árboles de derivación diferentes.

G es inherentemente ambigua si no existe una gramática no ambigua equivalente a G.
•

Lección 3: GIC

4

Autómatas con pila (AP)
- Elementos:
Componentes físicos Unidad de Proceso Fuente de entrada Pila Q Σ Γ Componentes lógicos conjunto de estados alfabeto de entrada alfabeto de pila

-Elementos distinguidos para la inicialización y aceptación:
q0 ∈Q: estado inicial F ⊆ Q: conjunto de estados finales pila vacía

- Ciclo-máquina

Consultas: • estado actual • símbolo de entrada • cima de la pila

Acciones: • avance en la entrada • cambio de estado • modificación de la pila:desempilar un elemento ó desempilar un elemento y empilar uno o más
5

Lección 3: Autómatas con pilaAutómatas con pila (AP)
- Definición formal:
M = (Q, Σ, Γ, δ, q0, F) con δ : Q × Σ × Γ ∪ {⊥} - → ℘(Q × Γ*)

-Configuración:
(q, w, α) ∈ Q × Σ* × Γ*

-Movimiento:
(p, sw, Aα) ├── (q, w, βα) si y solo si (q, β) ∈ δ(p, s, A) (p, sw, ε) ├── (q, w, β) si y solo si (q, β) ∈ δ(p, s, ⊥)

- Lenguaje aceptado:
* L(M) = { w∈Σ*: ∃ p∈F (q0, w, ε) ├── (p, ε, ε) }
Lección 3: Autómatas con pila 6Determinismo y no determinismo
- Diseñar un autómata con pila que reconozca el siguiente lenguaje: L = { wcwR: w ∈ {a,b}* } - Diseñar un autómata con pila que reconozca el siguiente lenguaje: L = { wwR: w ∈ {a,b}* } En general, a diferencia de lo que pasa entre L(AFD) y L(AFND), los lenguajes reconocidos por autómatas con pila deterministas (APD) no coinciden con los lenguajes reconocidos porautómatas con pila NO deterministas (AP). Es decir, L(AFD) = L(AFND) pero L(APD) ≠L(AP)
Lección 3: Autómatas con pila 7

Formas Normales
Definiciones:
•

Símbolo útil, X: Símbolo accesible, X: Símbolo fecundo, X:

S S X

⇒ ⇒
* *

*

αXβ αXβ w

⇒

*

w

•

•

⇒

Lección 3: Formas normales

8

Eliminar símbolos inútiles (I)
entrada: G = (N, ∑, P, S) gramáticaindependiente de contexto salida: G2 = (N2, ∑, P2, S) equivalente a G sin símbolos inútiles
-- Objetivo: eliminar de G los no terminales estériles -- Método: buscar inductivamente,los símbolos fecundos N1 -- Resultado: G1 = (N1, ∑, P1, S)

proceso: primer paso:

• Si A → w ∈ P con w∈Σ* entonces A∈N1 • Si A → α ∈ P con α ∈(N1 ∪Σ)*, entonces A∈N1 P1 = { A → α ∈ P: α∈(Σ ∪ N1)*}
Lección 3:...