MATEMÁTICA
DISCRETA
Lenguajes
INTRODUCCIÓN
Ordenador
Dada una tarea
¿Puede realizarse con un ordenador?
¿Cómo puede realizarse esa tarea?
Un tipo de estructura usada en modelos de computación son las gramáticas, se
utilizan para generar las palabras de un lenguaje y decidir si una palabra cualquiera
pertenece o no a un lenguaje definido.
Los lenguajes formales definidos por gramáticas proporcionan modelos para
lenguajes naturales, como el español, y para lenguajes de programación, como
Pascal, Fortran, C o Java.
IDIOMA ESPAÑOL
Las palabras del idioma español pueden combinarse de varias formas.
La gramática española nos dice cuándo cierta combinación de palabras es una frase
válida. Por ejemplo:
sujeto predicado
El sapo escribe claramente Es una frase válida
artículo adverbio
nombre verbo
No nos preocupa si tiene sentido o no, lo que nos preocupa es solamente la sintaxis,
o forma de la frase, no el significado (semántica)
IDIOMA ESPAÑOL
Las palabras del idioma español pueden combinarse de varias formas.
La gramática española nos dice cuándo cierta combinación de palabras es una frase
válida. Por ejemplo:
Nada rápidamente matemáticas NO es una frase válida
No sigue las reglas de la gramática española
SINTAXIS
(GRAMÁTICA) Parte de la gramática que estudia el modo en que se combinan las
palabras y los grupos que estas forman para expresar significados, así como las
relaciones que se establecen entre todas esas unidades
(INFORMÁTICA) Conjunto de reglas que definen las secuencias correctas de los
elementos de un lenguaje de programación
La sintaxis de un lenguaje natural (inglés, español, alemán, francés) es
extremadamente complicada
Investigaciones
lenguaje formal
Lenguaje 1 Lenguaje 2 (Conjunto de reglas bien
definidas)
Traducción
automática
LENGUAJES
Un lenguaje natural es un conjunto de Un lenguaje formal se aplican para
palabras y métodos para combinar modelar un lenguaje natural y
palabras, que es usado y entendido «comunicarse» con la computadora.
por un extenso grupo de personas.
Ambos tienen cuestiones en común como por ejemplo un alfabeto
y reglas gramaticales.
Lenguajes naturales Lenguajes formales
Una semántica (un significado) Reglas gramaticales
Una sintaxis (un conjunto de reglas preestablecidas (lenguajes
gramaticales) de programación)
SINTAXIS
Aplicaciones de los lenguajes de programación
Problemas:
(1) ¿Cómo se puede determinar cuándo una combinación de palabras es una frase
válida en un lenguaje formal?
(2) ¿Cómo se pueden generar las frases válidas de un lenguaje formal?
Antes de ver la definición de gramática, describiremos un ejemplo de gramática que
genera un subconjunto del español.
Definiremos este subconjunto usando una lista de reglas que describe cómo construir
una frase válida.
SINTAXIS
Reglas
1. Una frase se compone de un sujeto seguido de un predicado
2. Un sujeto se compone de un artículo seguido de un nombre seguido de un adjetivo, o
3. Un sujeto se compone de un artículo seguido de un nombre;
4. Un predicado se compone de un verbo seguido de un adverbio, o
5. Un predicado se compone de un verbo;
6. Un artículo es un, o 7. Un artículo es el;
8. Un adjetivo es grande, o 9. Un adjetivo es hambriento,
10. Un nombre es conejo, o 11. Un nombre es matemático;
12. Un verbo es come, o 13. Un verbo es salta;
14. Un adverbio es rápidamente, o 15. Un adverbio es salvajemente.
SINTAXIS
A partir de estas reglas, podemos formar frases realizando una serie de
reemplazamientos hasta que no podamos aplicar ninguna regla más. Por ejemplo
frase
sujeto predicado
artículo nombre adjetivo predicado
artículo nombre adjetivo verbo adverbio
el nombre adjetivo verbo adverbio
el conejo adjetivo verbo adverbio el rápidamente come
el conejo grande verbo adverbio matemático
el conejo grande salta adverbio (no es válida la frase)
el conejo grande salta rápidamente
un matemático hambriento come salvajemente
un matemático salta
el conejo come rápidamente
SINTAXIS
frase
sujeto predicado
artículo nombre adjetivo verbo adverbio
artículo nombre verbo
un conejo grande come rápidamente
el matemático hambriento salta salvajemente
ALFABETO
Definición 1
Un alfabeto 𝑉 es un conjunto finito y no vacío, cuyos elementos se llaman símbolos.
Cada elemento que pertenece al conjunto alfabeto se denominan letras.
Ejemplo:
Para el alfabeto 𝑉 = {𝑎, 𝑏} tanto la 𝑎, como la 𝑏 son letras, simplemente por ser
elementos de ese conjunto.
PALABRA
Definición 2
Un palabra sobre 𝑉 es una cadena finita de elementos de 𝑉. La palabra vacía o cadena
vacía, denotada por 𝜆, es la cadena sin símbolos. El conjunto de todas las palabras
sobre 𝑉 se denota por 𝑉 ∗ .
Ejemplo:
Para el alfabeto 𝑉 = {0,1} 𝑉 ∗ : conjunto de todas las palabras que se pueden
que se denomina alfabeto construir con las letras 0 y 1
binario, se tienen las
palabras: 𝑉 ∗ = {𝜆, 1101, 001110, … }
1101 𝜆, es la palabra nula, aquella que no tiene
001110 letras y que siempre pertenece a 𝑉 ∗ .
PALABRA
Definición 2
Un palabra sobre 𝑉 es una cadena finita de elementos de 𝑉. La palabra vacía o cadena
vacía, denotada por 𝜆, es la cadena sin símbolos. El conjunto de todas las palabras
sobre 𝑉 se denota por 𝑉 ∗ .
Ejemplo:
Para el alfabeto 𝑉 = {𝑎, 𝑏}, 𝑉 ∗ : conjunto de todas las palabras que se pueden
se tienen las palabras: construir con las letras 𝑎 y 𝑏
ababbaaa 𝑉 ∗ = {𝜆, 𝑎𝑏𝑎𝑏𝑏𝑎𝑎𝑎, 𝑏𝑏𝑏𝑏, 𝑎𝑎𝑎𝑎𝑎, … }
bbbb
aaaaa Tengamos en cuenta que si bien el alfabeto
𝑉 es finito, 𝑉 ∗ no lo es.
LONGITUD DE UNA PALABRA
Definición 3
La longitud de una cadena 𝑤 se define como el número de símbolos que contiene. Se
denota por 𝑙𝑜𝑛𝑔 𝑤 = 𝑤 .
Ejemplo:
Para el alfabeto 𝑉 = {𝑎, 𝑏}, se tienen las palabras:
𝑤 =ababbaaa 𝑙𝑜𝑛𝑔 𝑤 = 𝑤 = 8
𝑣 =bbbb 𝑙𝑜𝑛𝑔 𝑣 = 𝑣 = 4
𝑡 =aaaaa 𝑙𝑜𝑛𝑔 𝑡 = 𝑡 = 5
La palabra vacía 𝜆 carece de símbolos, tiene longitud cero 𝑙𝑜𝑛𝑔 𝜆 = 𝜆 = 0
LENGUAJE
Definición 4
Un lenguaje 𝐿 sobre 𝑉 es un subconjunto de todas las palabras que se pueden formar
con las letras de un alfabeto 𝑉, es decir 𝐿(𝑉) ⊆ 𝑉 ∗ .
Ejemplo:
Para el alfabeto 𝑉 = {𝑎, 𝑙, 𝑛, 𝑝}, se tienen:
𝑉 ∗ : conjunto de todas las palabras que se pueden construir con las letras 𝑎, 𝑙, 𝑛 y 𝑝.
𝑉 ∗ = {𝜆, 𝑎𝑎, 𝑛𝑎𝑛𝑎𝑛𝑎, 𝑛𝑝𝑎𝑎𝑎, … , 𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑙𝑎𝑛𝑎, … }
Lenguaje sobre 𝑉: 𝐿(𝑉) = {𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑙𝑎𝑛𝑎} ⊆ 𝑉 ∗
OPERACIONES CON LENGUAJES
Las siguientes son operaciones que se pueden realizar con los lenguajes (tengamos en
cuenta que un lenguaje es un conjunto y por lo tanto son válidas las operaciones para
conjuntos)
Definición 5 - Concatenación
Dados dos lenguajes 𝐿1 y 𝐿2 , su concatenación 𝐿1 . 𝐿2 contendrá todas las palabras
que se pueden formar por la concatenación de una palabra de 𝐿1 y otra de 𝐿2 .
Ejemplo:
Dados 𝐿1 = {𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑙𝑎𝑛𝑎} y 𝐿2 = {𝜆, 𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑝𝑎𝑛𝑎, 𝑝𝑎𝑙𝑎𝑏𝑟𝑎, 𝑝𝑎𝑝𝑎, 𝑝𝑎𝑙𝑎}
𝐿1 . 𝐿2 = {𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑙𝑎𝑛𝑎, 𝑛𝑎𝑛𝑎𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎𝑛𝑎𝑛𝑎, 𝑙𝑎𝑛𝑎𝑛𝑎𝑛𝑎, … }
Concatenamos cada palabra del primer lenguaje con cada palabra del segundo
lenguaje
OPERACIONES CON LENGUAJES
Definición 6 - Potencia
La potencia 𝒊 − é𝒔𝒊𝒎𝒂 de un lenguaje corresponde a la concatenación 𝒊 veces del
lenguaje en el mismo; se denota por
𝐿𝑖 = 𝐿. 𝐿. 𝐿 … 𝐿
𝑖 − 𝑣𝑒𝑐𝑒𝑠
Tengamos en cuenta que si 𝑖 = 0 obtenemos el lenguaje nulo 𝐿0 = 𝜆 , si 𝑖 = 1
Se obtiene el mismo lenguaje.
Ejemplo:
Dado 𝐿 = {0,1} entonces 𝐿2 = 00, 01, 10, 11
OPERACIONES CON LENGUAJES
Definición 7 - Reflexión
La reflexión de un lenguaje 𝐿 está formada por la aplicación de la reflexión a cada una
de las palabras del lenguaje; se denota por
𝐿𝑅 = {𝑥 𝑅 ∶ 𝑥𝜖𝐿}
Ejemplo:
Dado 𝐿 = {0, 1, 00, 10} entonces 𝐿𝑅 = {0, 1, 00, 01}
OPERACIONES ENTRE CONJUNTOS CON LENGUAJES
Definición 8
Dados dos lenguajes 𝐿1 y 𝐿2 , se define:
Unión: 𝐿1 ∪ 𝐿2 = {𝑥 ∶ 𝑥 ∈ 𝐿1 ∨ 𝑥 ∈ 𝐿2 } contendrá todas las palabras que
pertenezcan a cualquiera de los dos lenguajes.
Intersección: 𝐿1 ∩ 𝐿2 = {𝑥 ∶ 𝑥 ∈ 𝐿1 ∧ 𝑥 ∈ 𝐿2 } contendrá todas las palabras que
pertenezcan a los dos lenguajes.
Diferencia: 𝐿1 − 𝐿2 = {𝑥 ∶ 𝑥 ∈ 𝐿1 ∧ 𝑥 ∉ 𝐿2 } contendrá todas las palabras que
pertenezcan a 𝐿1 y no pertenezcan a 𝐿2 .
OPERACIONES ENTRE CONJUNTOS CON LENGUAJES
Ejemplo
Dados
𝐿1 = {𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑙𝑎𝑛𝑎} y 𝐿2 = {𝜆, 𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑝𝑎𝑛𝑎, 𝑝𝑎𝑙𝑎𝑏𝑟𝑎, 𝑝𝑎𝑝𝑎, 𝑝𝑎𝑙𝑎}
Se tiene:
Unión: 𝐿1 ∪ 𝐿2 = {𝜆, 𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎, 𝑙𝑎𝑛𝑎, 𝑝𝑎𝑛𝑎, 𝑝𝑎𝑙𝑎𝑏𝑟𝑎, 𝑝𝑎𝑝𝑎, 𝑝𝑎𝑙𝑎}
Intersección: 𝐿1 ∩ 𝐿2 = {𝑛𝑎𝑛𝑎, 𝑛𝑎𝑝𝑎}
Diferencia: 𝐿1 − 𝐿2 = 𝑙𝑎𝑛𝑎
𝐿2 − 𝐿1 = {𝜆, 𝑝𝑎𝑛𝑎, 𝑝𝑎𝑙𝑎𝑏𝑟𝑎, 𝑝𝑎𝑝𝑎, 𝑝𝑎𝑙𝑎}
EJERCICIOS
EJERCICIOS
EJERCICIOS
