MATERIA:
LENGUAJES AUTOMATAS I
UNIDAD 1:
Introducción a la Teoría de Lenguajes Formales.
HORARIO:
16:00 - 17:00
AULA:704
GRUPO:IS2
ALUMNA:
MEMIJE PERALTA ISIS ASTRID
22320964
NOMBRE DEL PROFESOR:
GRACIELA GARCIA MORALES
FECHA:
26/02/2025
INTRODUCCIÓN
Un lenguaje formal es un conjunto (finito o infinito) de cadenas finitas de símbolos primitivos Ej: El
lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadas con los dígitos
0, 1, 2, 3, 4, 5, 6, 7, 8 y 9 Dichas cadenas están formadas gracias a un alfabeto y a una gramática
que están formalmente especificados El alfabeto es un conjunto finito no vacío de símbolos La
gramática es un conjunto finito de reglas para formar cadenas finitas juntando símbolos del
alfabeto A cada cadena de símbolos de un lenguaje formal se le llama fórmula bien formada (o
palabra) del lenguaje
Tipo 3: Gramáticas regulares que generan lenguajes regulares Tipo 2: Gramáticas incontextuales
que generan lenguajes incontextuales Tipo 1: Gramáticas contextuales que generan lenguajes
contextuales Tipo 0: Gramáticas libres que generan lenguajes sin ningún tipo de restricción Cuanto
menor es el tipo, mayor es el poder expresivo del lenguaje generado y más complejidad tiene su
tratamiento por parte de una máquina
NOMBRE DE FUNCIÓN O SINTAXIS EJEMPLO
LENGUAJE PROPÓSITO
Lenguaje Puede ser El conjunto de
Regular descrito expresiones
mediante una regulares sobre un
expresión alfabeto A se
regular denomina ER(A) y Descripción del lenguaje de las
(expresar de sólo contiene cadenas que empiezan por una “a”
forma compacta expresiones y continúan con “a’s” y “b’s” a(a|
cómo son todas formadas mediante b)* Descripción del lenguaje de las
∅∈ER(A) y denota
las cadenas de estas reglas: cadenas que empiezan por “a”,
símbolos que le continúan con “b’s” y “c’s” y
siendo ∅ el vacío λ
pertenecen) el lenguaje {}, terminan en “d” a(b|c)*d
∈ER(A) y denota el
Puede ser Descripción del lenguaje de las
generado cadenas formadas por trozos de
mediante una lenguaje {λ}, siendo cadena que pueden empezar (o
x ∈ A, x ∈ER(A) y
gramática λ la cadena vacía Si no) por una “a” y continúan con un
regular (obtener número que tenga al menos un
todas las denota el lenguaje dígito; además terminan siempre
∈ ER(A), con
cadenas de {x} Si H∈ ER(A) y K en asterisco * (a?[0-9]+)*\*
símbolos que le
pertenecen) lenguajes
(H | K) ∈ ER(A) y
Puede ser denotados LH y LK
reconocido
LH ∪ LK (Conjunto
mediante un denota el lenguaje
autómata finito
(saber si una de todas las
K) (HK) ∈ ER(A) y
cadena de cadenas de H o de
símbolos
pertenece a él o denota el lenguaje
{hk tal que h ∈ LH y
no) LHK siendo LHK =
k ∈ LK} (Conjunto
de todas las
concatenaciones
posibles de una
de K) H* ∈ER(A) y
cadena de H y otra
denota el lenguaje
∪ {aα tal que a ∈
LH* siendo LH* = {λ}
LH y α ∈ LH*}
(Conjunto de todas
las concatenaciones
sucesivas posibles
de cadenas de H)
Los paréntesis ()
asocian operadores
a cadenas de
símbolos. Si no
aparecen, repetir *
es más prioritario
que concatenar y
concatenar más
prioritario que
alternar
Las cadenas ∈ (T ∪ Gbin Ejemplo de derivación bits ⇒
bits bit ⇒ bits bit bit ⇒ bit bit bit
Lenguaje Puede ser
⇒ 1 bit bit ⇒ 1 0 bit ⇒ 1 0 1
incontextual generado N)* se llaman
Las cadenas ∈ T* se
mediante una formas sentenciales
gramática
incontextual llaman sentencias o
(obtener todas frases Una
las cadenas de gramática
genera en (T ∪ N)*
símbolos que le incontextual G
pertenecen)
Puede ser relaciones de
inmediata ⇒ ⇒⇒
reconocido derivación
⇒G α αα α ⇒ ⇒ ⇒
mediante un
⇒Gβ ββ β (β es
autómata con
pila (saber si una
cadena de derivable
símbolos inmediatamente de
pertenece a él o α) si y sólo si dan
no) Aunque son estas tres
más complejos condiciones: α
que los ≡αonα1 β ≡ αoβ0α1
αo, α1 y β0 ∈ (T ∪
regulares, estas n → β0∈P siendo
características
facilitan su N)* y n ∈ N Las
derivación ⇒ ⇒⇒
tratamiento relaciones de
se ⇒G* son el
computacional,
por eso también
nos interesan los resultado de hacer
transitivo de ⇒
lenguajes el cierre reflexivo-
⇒⇒ ⇒G α ⇒G*
incontextuales
β(β es derivable de
α) si y sólo si existe
una secuencia de
derivaciones
inmediatas que nos
permita llegar a β
Si α α α α ⇒ ⇒
partiendo de α
⇒ ⇒G* β ββ β
Lenguaje Los autómatas a pila
generado se definen con una
puede haber tupla <A, P, E, po,
sólo una eo, t, F> siendo: A el
secuencia de alfabeto de entrada
derivación que acepta el
inmediata autómata P el
(derivación de β alfabeto de la pila E
ββ β desde α αα el conjunto finito y
posibles po ∈ P, el
α) o varias no vacío de estados
posibles Cada
pila eo ∈ E, el
una se símbolo inicial de la
⇒G αo,
representa así: α
estado inicial del
⇒G β O en
αo⇒Gα1, …, αn autómata t, la
función de
estados t ∈ E ×(A
forma transición de
αo ⇒G α1 ⇒G ∪{λ}) × P →℘(E
compacta: α⇒G
…. ⇒G β ×P*) (Con algún
Derivación por símbolo de entrada,
la izquierda: o con la cadena
aquella en la vacía, y teniendo en
que cada cuenta la cima de la
derivación pila, se pasa de uno
⇒G αy usa la
inmediata αx de los estados del
autómata a otro
β0 ∈ P para el n
producción n → conjunto no vacío
de estados,
situado lo más a sustituyendo el
la izquierda símbolo de la cima
posible en αx de la pila por otros
Derivación por símbolos del
la derecha: alfabeto de la pila el
aquella en la símbolo más a la
que cada derecha de ellos es
⊆E, el conjunto de
derivación la cima de la pila) F
⇒G αy usa la
inmediata αx
estados finales
β0 ∈ P para el n
producción n →
situado lo más a
la derecha
posible en αx
Lenguaje TERMINAL <no Sintaxis de los
incontextual terminal> números enteros
Símbolo (ej. una positivos en
palabra) del notación BNF Sintaxis de los números enteros
lenguaje a <numero positivos en notación EBNF
definir (se entero> ::= <signo Numero-entero ::= [Signo]
escribe en letras opcional> Secuencia-dígitos Signo ::= “+”
mayúsculas) <secuencia dígitos> Secuencia-dígitos ::= Dígito {Dígito}
Símbolo que se <signo opcional> ::= Dígito ::= “0” | “1” | “2” | “3” | “4”
define en + | <nada> | “5” | “6” | “7” | “8” | “9”
términos de <secuencia
otros símbolos dígitos> ::= <dígito>
(tanto | <dígito>
terminales como <secuencia dígitos>
no terminales) <dígito> ::= 0 | 1 | 2
(se escribe en |3|4|5|6|7|8
letras | 9 <nada> ::=
minúsculas y Añade
entre <>) Regla metasímbolos
de producción nuevos y cambia la
Descripción de forma de presentar
un símbolo no las cosas BNF
terminal como TERMINAL <no
equivalente a 1) terminal>
una Metasímbolo ::=
combinación de Equivalencia |
terminales y no Alternativa
terminales, o 2) Recursividad
Metasímbolo permitida
Procesadores de Procesadores de
Lenguaje Lenguaje Ingeniería
Ingeniería en en Informática EBNF
Informática “terminal” No-
Símbolo propio terminal
de la notación Metasímbolo ::= |
BNF, está (...) [...] {...}
reservado y no Equivalencia
puede utilizarse Alternativa
en ningún otro Agrupación
símbolo ::= Aparición opcional
Equivalencia (lo Aparición 0, 1 o más
de la izquierda veces (son ERs a la
equivale a lo de derecha de cada
la derecha; es producción)
una regla de Recursividad NO
producción) | permitida
Alternativa
CONCLUSIÓN
Conjunto de reglas que especifican y permiten verificar la corrección de las sentencias del lenguaje
y que están orientadas a los programadores que quieren conocer con exactitud su sintaxis
(principalmente) La notación gramatical es útil desde el punto de vista del desarrollador de
procesadores de lenguaje, pero no desde el punto de vista de sus usuarios Formalismos más
utilizados por ser compactos o visuales: Notación BNF (Backus-Naur Form) Notación EBNF
(Extended Backus-Naur Form) Diagramas sintácticos Todos ellos pueden expresar cualquier
lenguaje incontextual (la base de la sintaxis de cualquier lenguaje de programación) así que
podemos usar el que queramos
Maneras más organizadas de expresar una gramática incontextual (¡recomendables para no
cometer errores en la definición del lenguaje!) Forma normal de Chomsky Gramática incontextual
∈ T y n, no, n1 ∈N Forma normal de Greibach Gramática incontextual G con todas sus
G con todas sus producciones expresadas según una de estas dos fórmulas: n →non1 n →t siendo t
producciones expresadas
Bibliografía
(S/f). Recuperado el 27 de febrero de 2025, de
http://chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.fdi.ucm.es/profesor/
fpeinado/courses/compiling/repaso-lenguajesformales.pdf
