guia de sql

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES (UTN-FRR)

FACULTAD REGIONAL ROSARIO

INTRODUCCIÓN A LOS LENGUAJES FORMALES

GUÍA TEÓRICO-PRÁCTICA
PARA ALUMNOS DE LA CÁTEDRA

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
DE LA CARRERA DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN

ING. EDUARDO AMAR

PROF. ING. EDUARDO AMAR - INTRODUCCIÓN A LOS LENGUAJES FORMALES

1

SINTAXIS Y SEMÁNTICA DE LOSLENGUAJES (UTN-FRR)

2

UNIDAD DIDÁCTICA N° 1

INTRODUCCIÓN A LOS LENGUAJES FORMALES

1. Definiciones básicas
1.1. ALFABETO
o vocabulario o clase de carácter, es cualquier conjunto finito de símbolos.
Se lo denomina con:

V = { s1, s2, ........, sn }

Ej:
V = { a, b }

a y b son letras de V

V = { 0, 1 }

alfabeto binario

V = { a, b, ........, z }

alfabeto castellano

1.2.CADENA
sobre un alfabeto, es una secuencia finita de símbolos tomados de ese alfabeto.
También se llama a la cadena, palabra o tira.
Ej:
V = { a, b }

cadenas: a, aa, baab, bba

V = { 0, 1 }

cadenas: 01, 0010, 1001, 11

V = { a, b, ........, z }

cadenas: perro, loro, pato

1.3. LONGITUD DE UNA CADENA S
se escribe |s|, es la cantidad de símbolos o letras que la componen.

Ej:V = { a, b }
s1 = a
s2 = bab
s3 = aaaba

PROF. ING. EDUARDO AMAR - INTRODUCCIÓN A LOS LENGUAJES FORMALES

|s1| = 1
|s2| = 3
|s3| = 5

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES (UTN-FRR)

3

V = { a, b, ......, z}
s1 = oca
s2 = zapato
s3 = repollo

|s1| = 3
|s2| = 6
|s3| = 7

1.4. CADENA VACÍA
se representa con ε, es una cadena de longitud cero, no tiene ninguna letra.

1.5.CERRADURA DE UN ALFABETO V
o clausura de V, se representa con V* y es el conjunto de todas las palabras
posibles obtenidas de V, incluyendo la palabra vacía. Siempre es un conjunto ∞.
Ej:
V = { a, b }

V* = { ε, a, b, aa, ab, ba, bbb, .....}

V = { a, b, ......, z}

V* = { cualquier palabra del idioma castellano}

1.6. CERRADURA POSITIVA DE V
se representa con V+, no contiene lapalabra vacía.

V + = V* - { ε }

Ej:
V = { a, b }

V+ = { a, b, aa, ab, ba, bbb, .....}

1.7. PARTES DE UNA CADENA
Término
Prefijo de s

Sufijo de s

Subcadena de s
Prefijo, sufijo o
subcadena propios de s
Subsecuencia de s

Definición
Cadena que se obtiene eliminando 0 o más símbolos desde la
derecha.
(Ej: s = bandera → ban)
Cadena que se obtiene eliminando 0 o más símbolosdesde la
izquierda.
(Ej: s = bandera → dera)
Cadena que se obtiene eliminando un prefijo y un sufijo de s.
(Ej: s = bandera → ande)
Para toda s, tanto s como ε son: prefijo, sufijo y subcadena
Cualquier cadena no vacía x, que sea prefijo, sufijo o
subcadena, pero s ≠ x
Cualquier cadena formada eliminando 0 o más símbolos no
necesariamente contiguos de s
(Ej: s= bandera → bada)

PROF.ING. EDUARDO AMAR - INTRODUCCIÓN A LOS LENGUAJES FORMALES

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES (UTN-FRR)

4

Ej:
S = compiladores
•
•
•
•
•

compi, compila, com
dores, compiladores, ε
pila, ε, compila
pila, ε, compi
compis, compiladores, cmpr

2. Lenguajes
se denomina lenguaje sobre un alfabeto V a cualquier conjunto de cadenas de V y se
representa con L.
L ⊆ V*. L puedeser finito o infinito.
Tanto V como V* son lenguajes sobre V.
Ej:
V = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
L1 (V) = { n° de 3 cifras }
L2 (V) = { todos los n° }
L3 (V) = { n° binarios }

2.1. CONJUNTO VACÍO
φ o {} , es aquel conjunto que no tiene ninguna palabra.
2.2. CONJUNTO QUE CONTIENE LA CADENA VACÍA
{ ε }.

2.3. OPERACIONES APLICADAS A LENGUAJES
Dados dos lenguajes L y M se define:Unión de L y M:

LUM

L U M = { s / s está en L o s está en M }
Concatenación de L y M:

L.M

L . M = { s . t / s está en L y t está en M }

PROF. ING. EDUARDO AMAR - INTRODUCCIÓN A LOS LENGUAJES FORMALES

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES (UTN-FRR)

Cerradura de Kleene:

L*

∞
L* = U Li
i=0

L* = L0 U L1 U L2 U .................. Ln U ......
L0 = { ε }
L1 = L
L2 =...