Gramaticas formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Las Gramáticas Formales
Como definir un Lenguaje Formal

Universidad de Cantabria

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Esquema

1

Motivación

2

Definición de Gramáticas Formales

3

Tipos de Notación

Gramáticas Formales

Motivación
Definición deGramáticas Formales
Tipos de Notación

Problema

Dado un lenguaje L, se nos presenta el problema de
describirlo. Para resolverlo se pueden tomar dos caminos:
Dar una forma de generar todas las palabras del lenguaje.
Dar un algoritmo para demostrar que una palabra esta en
el lenguaje.

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

ProblemaDado un lenguaje L, se nos presenta el problema de
describirlo. Para resolverlo se pueden tomar dos caminos:
Dar una forma de generar todas las palabras del lenguaje.
Dar un algoritmo para demostrar que una palabra esta en
el lenguaje.

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Diferencias entre los Métodos

A simple vista, los dos métodos noson equivalentes. Podemos
pensar por ejemplo en el lenguaje formado por los programas
escritos en java que devuelven para cualquier entrada “Hola
Mundo”.

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Diferencias entre los Métodos

También tenemos la otra cara de la moneda, saber reconocer
no implica saber generar elementos del conjunto. Unejemplo
lo darían el lenguaje definido por los libros en español.

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

La Idea detrás de una Gramática

Los lenguajes que vamos a tratar no son simples conjuntos de
palabras. Las palabras están porque tienen una estructura, han
sido generadas por unas reglas.

Gramáticas Formales

MotivaciónDefinición de Gramáticas Formales
Tipos de Notación

Las Gramáticas Formales
Definición (Gramáticas Formales)
Una gramática formal es una cuaterna G = (V , Σ, Q0 , P),
donde:
V es un conjunto finito llamado alfabeto de símbolos no
terminales o, simplemente, alfabeto de variables.
Σ es otro conjunto finito, que verifica V ∩ Σ = ∅ y se suele
denominar alfabeto de símbolos terminales.
Q0 ∈ V es una“variable” distinguida que se denomina
símbolo inicial.
P ⊆ (V ∪ Σ)∗ × (V ∪ Σ)∗ es un conjunto finito llamado
conjunto de producciones (o, simplemente, sistema de
reescritura).
Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Como Operar: Sistema de Transición

Para poder definir la dinámica asociada a una gramática,
necesitamos asociarle unsistema de transición.

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Como Operar: Sistema de Transición
Definición
Sea G = (V , Σ, Q0 , P) una gramática, definiremos el sistema
de transición asociado (SG , →G ) dado por las propiedades
siguientes:
El espacio de configuraciones será dado por:
SG := (V ∪ Σ)∗ .
Dadas dos configuraciones s1 , s2 ∈ SG, decimos que
s1 →G s2 si se verifica la siguiente propiedad:
∃x, y , α, β ∈ SG = (V ∪ Σ)∗ , tales que
s1 := x · α · y , s2 := x · β · y , (α, β) ∈ P.
Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Lenguaje generado por una Gramática

Definición
Dada una gramática G = (V , Σ, Q0 , P) y su espacio de
configuraciones SG se define el lenguajegenerado por una
gramática al conjunto de configuraciones s1 tales que:
Q0 →G s1 ,
además s1 ∈ Σ∗ .

Gramáticas Formales

Motivación
Definición de Gramáticas Formales
Tipos de Notación

Ejemplos
Ejemplo
Consideremos la gramática: G = (V , Σ, Q0 , P), donde
V := {Q0 }, Σ := {a, b}, , P := {(Q0 , aQ0 ), (Q0 , λ)}.
El sistema de transición tiene por configuraciones
S := {Q0 , a, b}∗ y...