Ingeniería en Sistemas

Lenguajes
 

Informá0ca
 III
 –
 2014
 
Ing.
 Andrea
 Quan
 

Lenguajes
 
 
Todos
 los
 lenguajes
 formales
 poseen
 dos
 
dimensiones fundamentales:
 
① 
 Sintáxis
 
 

 ¿Cómo
 se
 escriben
 o
 formulan
 correctamente
 las
 
operaciones
 dentro
 del
 lenguaje?
 

② 
 Semán0ca
  ¿Qué
 significado
 0ene
 la
 oración?
 

Alfabeto
 
Conjunto
 finito
 y
 no
 vacío
 de
 símbolos.
 
 
Lo
 denotaremos
 con
 el
 símbolo Σ
 (sigma).
 

 
Ejemplos:
 
 


 
 Σ
 =
 {0,1}
 

 

 


 Σ
 =
 {a,b,c}
 

 nuestro
 abecedario
 

Strings
 
Dado
 un alfabeto
 Σ,
 una
 cuerda
 es
 una
 
secuencia
 finita
 de
 símbolos
 sobre
 Σ.
 
 
Generalmente
 denotamos
 con
 u,v,w,
 etc..
 

 Ejemplo:
 
 Sea
 Σ
 =
 {a,b}
 

 
 u
 =
 aabba
 
Cuerdas
 

 
 v
 =
 a
 
sobre
 Σ
 

 
 w
 =
 ba
 
 


 Propiedades
 de
 los
 Strings
 
LONGITUD:
 
Sea
 w
 una
 cuerda
 sobre
 Σ,
 la
 longitud
 de
 w,
 
denotada
 por
 |w|
 es
 la
 can0dad
 de símbolos
 
que
 forman
 la
 cuerda.
 

 
La
 cuerda
 cuya
 longitud
 es
 igual
 a
 0
 es
 llamada
 
cuerda
 nula
 o
 string
 vacio
 y la
 denotaremos
 con
 
el
 símbolo
 λ
 
 

Propiedades
 de
 los
 Strings
 
CERRADURAS:
 
Dado
 un
 alfabeto
 Σ:
 
 
-­‐  La
 cerradura de
 Kleene
 Σ*
 (star
 closure)
 :
 Es
 el
 
conjunto
 de
 todas
 las
 cuerdas
 obtenidas
 a
 
par0r
 de
 Σ,
 incluyendo
 λ.
 ...