SSyL-cap2_2015_Lenguajes

Vista previa del material en texto

19 
 
CAPITULO 2: LENGUAJES 
2.1. DEFINICIONES PREVIAS 
SIMBOLO: 
Es una entidad indivisible, que no se va a definir. Normalmente los símbolos son letras 
(a,b,c,………….., Z), dígitos (0, 1, ……….., 9) y otros caracteres (+, -, *, /, ¿, ………….). 
los símbolos también pueden estar formados por varias letras o caracteres, así por ejem-
plo las palabras reservadas de un lenguaje de programación son símbolos de dicho len-
guaje. 
a b c . . . . . . . . . . Z 
 0 1 2 . . . . . . . . . .9 Símbolos 
 + * ? > . . . . . . . . . 
 
2.2. ALFABETO O VOCABULARIO: 
Conjunto finito de “símbolos”. Los alfabetos se definen por enumeración de los símbolos 
que contienen. Utilizaremos la letra V para referenciar un alfabeto, para definir que un 
símbolo a pertenece a un alfabeto V se utiliza la notación a ϵ V. 
Ej: V 
V1 = {a, b, c, ……………., z} → alfabeto castellano 
V2 = {0, 1} → alfabeto binario 
V3 = {a, b} 
 
2.3. CADENA SOBRE UN ALFABETO: 
Toda secuencia finita de símbolos tomados de un determinado alfabeto. Puede haber re-
petición, es decir, un símbolo puede aparecer varias veces dentro de la cadena. También 
se llama a la cadena, palabra, tira o string. Utilizaremos la letra s minúscula para referen-
ciar una cadena. 
Secuencia: → tienen un orden lineal, sucesión finita. Todos los símbolos tienen un suce-
sor excepto el último y todos tienen un predecesor excepto el primero. 
Ej: 
s1 = abcbz es una cadena del alfabeto V1 
s2 = 001101 es una cadena del alfabeto V2 
s3 = aaabab es una cadena del alfabeto V3 
 s4 = sintaxis es una cadena del alfabeto V1 
2.4. LONGITUD DE UNA CADENA s: 
Esta dada por la cantidad de apariciones u ocurrencias de símbolos en la cadena, es de-
cir, cantidad de símbolos o letras que la componen. Se indica |s| 
a z 
b d 
20 
 
Ej 
 V = {a, b} s1 = abbba |s1| = 5 
 s2 = a |s2| = 1 
 
 V = {a, b, c, . . .. . . , z} s1 = sintaxis |s1| = 8 
 s2 = lenguajes |s2| = 9 
 s3 = for |s3| = 3 
 
2.5. CADENA VACIA: 
Es una cadena especial de longitud cero, es decir, no posee símbolos. Se indica o repre-
senta con la letra Ɛ (épsilon). | Ɛ | = 0. 
 
2.6. PARTES DE UNA CADENA: 
 PREFIJO DE UNA CADENA s: toda cadena que resulta de eliminar 0 o más ocu-
rrencias de símbolos de la cadena s desde el extremo derecho. Si no elimino nin-
guno me queda s, si elimino todos me queda Ɛ, por lo tanto, s y Ɛ son prefijos. 
Se define como prefijo propiamente dicho a aquel que no es ni s ni Ɛ. 
Ej: s = sintaxis → sin 
 
 SUFIJO: cadena que se obtiene eliminando 0 o más símbolos desde la izquierda. 
Sufijo propiamente dicho es aquel que no es ni s ni Ɛ. 
Ej: s = sintaxis → taxis 
 
 SUBCADENA DE UNA CADENA s: toda cadena que se obtiene al eliminar un pre-
fijo y un sufijo de s. 
Subcadena propiamente dicha es aquella que no es ni s ni Ɛ. 
Ej: s = sintaxis → inta 
 
 SUBSECUENCIA DE s: cualquier cadena que se forma eliminando 0 o más símbo-
los, no necesariamente consecutivos, de s. 
Ej: s = sintaxis → sinas 
 
 
 
∀ s, tanto s como Ɛ son: 
prefijo, sufijo y subcadena 
Con un alfabeto finito puedo 
hacer infinitas cadenas 
 
 
21 
 
2.6. OPERACIONES ENTRE CADENAS 
 CONCATENACION DE CADENAS: sean x e y dos cadenas cualesquiera sobre el 
alfabeto V, se denomina concatenación de x e y y se representa x.y a una nueva 
cadena que se obtiene agregando y a x. Es decir, es la palabra formada al escribir 
los símbolos de la primera seguidos inmediatamente por los símbolos de la se-
gunda. 
Ej: x = vice x . y = vicedirector por lo tanto 
 y = director y . x = directorvice x . y ≠ y . x 
 
 POTENCIA ENTERA n ≥ 0 DE UNA CADENA s sn: 
Estamos en presencia de una definición por recurrencia: 
 s0 = Ɛ cadena vacía 
 si = si-1 . s (con i > 0) = s.s.s. . . . . . s (i veces) 
Ej: 
 s3 = s2 . s = (s1 . s) . s = ((s0 .s) . s) . s = ((Ɛ . s) .s) .s = (s . s) . s = s . s . s 
 s = ja s3 = jajaja 
2.7. LENGUAJE: 
Conjunto (finito o infinito) de cadenas que se pueden formar con un alfabeto (finito). Se re-
presenta con la letra L 
Lenguaje sobre un alfabeto V es cualquier conjunto de cadenas sobre ese alfabeto. Len-
guaje sobre V es cualquier subconjunto de V*. 
V* conjunto de todas las palabras posibles obtenidas de V incluyendo la palabra va-
cía (es un conjunto infinito ∞). 
 V* cadenas 
 
 
 V 
 alfabeto 
 cadenas de longitud 
 1 = alfabeto 
V  es un lenguaje sobre V 
V*  es un lenguaje sobre V 
{Ɛ}  es un lenguaje – tiene una cadena que es vacía 
Ø o { }  es un lenguaje – conjunto vacío – no tiene cadenas 
L ⊆ V* (L está contenido en V* o es igual a V*) 
 V 
 
 
a 
Ɛ 
22 
 
Ej: V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
 L1(V) = {nº de 2 cifras} 
 L2(V) = {todos los nº} 
L3(V) = {nº binarios} 
 V = {n, s, o, i, 3, 9} 
 R = {no; si} 
 S = {33; 9a} 
 
2.8. LENGUAJE VACÍO: 
Existe un lenguaje denominado lenguaje vacío, que es un conjunto vacío y que se denota 
con Ø o { }. El lenguaje vacío no debe confundirse con un lenguaje que contenga una 
sola cadena y que esta sea la cadena vacía, es decir {Ɛ}, ya que el nº de elementos (car-
dinalidad) de estos dos conjuntos es diferente. 
 Cardinal ({ Ø }) = 0 Cardinal {( Ɛ }) = 1 
2.9. OPERACIONES SOBRE LENGUAJES 
 Union de L y M: L U M 
 L U M = { s / s está en L o s está en M } 
 Concatenacion de L con M: L . M 
 L . M = { s / s = r . t con r en L y t en M } 
 No es conmutativa 
 Puedo concatenar un lenguaje consigo mismo, o sea, L . L es válido 
 
Ej: R . S = {no; si} . {33; 9a} = {no33; no9a; si33; si9a} 
 S . R = {33; 9a} . {no; si} = {33no; 33si; 9ano; 9asi} 
 R . R = {no; si} . {no; si} = {nono; sisi; nosi; sino} 
 Potencia entera n ≥ 0 de un Lenguaje L Ln 
 L0 = { Ɛ } conjunto que contiene la cadena vacía 
 Li = Li-1 . L (con i > 0) 
 Cerradura o Clausura de Kleene de L L* 
 L0 = { Ɛ } 
 L1 = L0 . L = { Ɛ } . L = L 
 L2 = L1 . L = L . L 
23 
 
 L3 = L . L . L 
 Ln = Ln-1 . L 
 L* = L0 U L1 U L2 U . . . . . . U Ln (Unión de todas las potencias del lenguaje de 0 en adelante) 
 ∞ 
L* = { Ɛ } U L U L . L U (L .L) .L U . . . . . . = U Li 
 i = 0 
 
por lo tanto L* es un lenguaje infinito que contiene al propio lenguaje, y Ɛ siempre está en 
la cerradura. 
 
2.10. CERRADURA DE KLEENE DEL ALFABETO TOMADO COMO LENGUAJE 
V* = V0 U V1 U V2 U V3 U . . . . . . . . (unión de todas las potencias enteras de V de 0 en 
adelante) 
V* = {Ɛ} U V U V . V U V . V . V U . . (conjunto de todas las cadenas que se pueden cons-
truir con los símbolos del alfabeto) 
{Ɛ}  cadenas de longitud 0 
V  cadenas de longitud 1 
V . V  cadenas de longitud 2 
V . V . V  cadenas de longitud 3 
 
Cuando tomo el alfabeto como lenguaje y hago la cerradura de Kleene del alfabeto lo que 
obtengo es el universo de todas las cadenas sobre V. 
 
2.11. CERRADURA POSTIVA DE L L+ 
L+ = L1 U L2 U L3 U . . . . . . (unión de todas as potencias positivas de L de 1 en adelante) 
 ∞ 
L+ = L U L . L U (L .L) .L U . . . . . . = U Li 
 i = 1 
L+ U {Ɛ} = L* 
 
Ej: 
 L = { a, aab} 
 M = { b, bb } 
 
L U M = { a, aab, b, bb } 
LM = { ab, aabb, abb, aabbb } 
L* = L0 U L1 U L2 U .......... 
 = { Ɛ,a, aab, aa, aaab, aaba, aabaab, ......... } 
L+ = L* - { Ɛ } 
L2 = { aa, aaab, aaba, aabaab } 
 Ej: Imaginemos un alfabeto que contiene letras y dígitos 
 
24 
 
V = { a, b, c, . . . , Z, 0, 1, 2, . . .,9 } 
 y sobre este alfabeto los lenguajes: 
 
 L = { A, B, .........., Z, a, b, ...........z } 
 D = { 0, 1, ..........., 9 } 
 
L U D = { conjunto de letras y dígitos } 
L . D = { conjunto de cadenas consistentes en 1 letra seguida por 1 dígito } 
L4 = { conjunto de cadenas de 4 letras } 
L* = { conjunto de cadenas de 1 o más letras, incluída Ɛ } 
D+ = { conjunto de cadenas de 1 o más dígitos } 
L . (L U D) = { conjunto de cadenas de letras y dígitos que empiezan con una letra} 
(L U D)* = { conjunto de cadenas de letras y dígitos, incluída la cadena vacía} 
L . (L U D)* = { conjunto de cadenas de letras y dígitos que empiezan con una letra, no in-
cluye la cadena vacía } 
Los nombres de variables en Pascal son cadenas de este conjunto. Este es el lenguaje 
formal de los identificadores de Pascal. 
En Pascal: <identificador> 
 
L . (L U D)+ = {conjunto de cadenas de letras y dígitos de por lo menos longitud 2 y que 
empiezan con una letra, no incluye la cadena vacía} 
 
D+ = {conjunto de cadenas de 1 o más dígitos} = {conjunto de los enteros positivos} tam-
bién ϵ al Pascal: 
 
dígito 
letra 
letra 
D+ = D1 U D2 U D3 U . . . . . . . . . . 
dígito 
<entero sin signo> 
25