2DAD5d01

TEORIA DE AUTOMATAS Y LENGUAJES
FORMALES

Docente: Bianka Barrios S

OTOÑO 2011

www.inacap.cl

CADENAS, ALFABETOS Y LENGUAJE
•

Una cadena (o palabra)
es una secuencia finita de símbolos
yuxtapuestos. Por ejemplo, si a, b y c son símbolos entonces: abc,
bac,cab,…, es una cadena.

•

La longitud de una cadena w, que se denota como |w|, es el número
de símbolos que componen la cadena.

•

Lacadena vacía denotada por ε, es la cadena que consiste en cero
símbolos. Por tanto, | ε | = Ø (no tiene símbolos)

•

Los prefijos de una cadena están formados por los primeros símbolos
de ésta; y los sufijos por los últimos.

•

Un alfabeto es un conjunto finito de símbolos.

•

Un lenguaje (formal) es un conjunto de cadenas (o strings) formados
por símbolos de algún alfabeto.
www.inacap.clCADENAS, ALFABETOS Y LENGUAJE
•

La concatenación de dos cadenas es la cadena que se forma al
escribir la primera seguida de la segunda, sin que haya espacio entre
ellas. La yuxtaposición se utiliza como el operador de concatenación.
Dado dos lenguajes L1 y L2 se define la concatenación de ambos como
sigue:

L1L2 = { uv / u ∊ L1, v ∊ L2}
Ejemplo: Si L1={a, ab} y L2 = {c, cd} entonces:

•

L1L2= {ac, acd,abc, abcd}

Se verifica que
LØ = ØL = Ø
L { ε } ={ε L} = L

www.inacap.cl

CADENAS, ALFABETOS Y LENGUAJE

Dado un lenguaje L se define la concatenación de L
mismo n–veces como sigue:
Ln = L · Ln-1 (n 1)
L1 = L
L0 = {ε}

www.inacap.cl

consigo

CADENAS, ALFABETOS Y LENGUAJE
• Clausura de un lenguaje: Si L es un lenguaje, entonces su
clausura L* se define:
L* = U Ln = L0 U L1 U L2 U ……
Ejemplo:L = {0,1}
L* = { ε } U (L · L0) U (L · L ) U (L · L2 ) …..
L* = { ε } U (L) U (L · L ) U (L · L · L )
L* = {ε, 0,1,00,01,….}

L*, es el conjunto formado por la concatenación de los miembros de
L cualquier número de veces, incluyendo cero

www.inacap.cl

CADENAS, ALFABETOS Y LENGUAJE
• Así p, ej., dado un lenguaje L = {a, bb} , construido sobre el
alfabeto {a, b}, L* o {a, bb}*, es {, a, bb, abb,bba, aa, bbbb, ...}.

www.inacap.cl

CADENAS, ALFABETOS Y LENGUAJE
•

Si w es una cadena, se llama wR al reverso de esta cadena. Por
ejemplo,
Si w=0101  wR = 1010
El reverso de un lenguaje L se escribe:
LR = {wR / w ∊ L2}

•

Ejemplo: Si L = {01, 110, 001}, entonces LR = {10, 001,100}

www.inacap.cl

CADENAS, ALFABETOS Y LENGUAJE
• El conjunto vacío, Ø, y el conjunto formado por la cadenavacía
{ε} son lenguajes. Nótese que son diferentes : el último tiene un
elemento , mientras que el primero no.
• El conjunto de palíndromos sobre el alfabeto {0,1} es un lenguaje
infinito. P = {w /wR = w ∊L}

• Otro lenguaje es el conjunto de cadenas sobre el alfabeto fijo Σ.
Denotamos a este lenguaje como Σ*.
• Por ejemplo, si Σ = {a}, entonces Σ* = {ε, a, aa, aaa, …}.
Si Σ={0,1}, entonces Σ* = {ε, 0,1, 00, 01, 10, 11, 000,….}

www.inacap.cl

GRAMATICAS FORMALES
• Una gramática formal es un objeto o modelo matemático que
permite especificar un lenguaje o lengua, es decir, es el conjunto de
reglas capaces de generar todas las posibilidades combinatorias de
ese lenguaje
• Hay distintos tipos de gramáticas formales que generan lenguajes
formales. Imaginemos una gramática con estas dos reglas:
A→ bAc
A → de
La idea es sustituir el símbolo inicial de la izquierda por otros
símbolos aplicando las reglas. El lenguaje al cual representa esta
gramática es el conjunto de cadenas de símbolos que pueden ser
generados de esta manera.

www.inacap.cl

GRAMATICAS FORMALES
• Una gramática
componentes:

formal

está

formada

principalmente

de

3

a) El alfabeto cuyos símbolos son “Terminales” dela gramática.
b) El conjunto de símbolos no terminales de la gramática (llamadas
derrotadores de frases).
c) Un conjunto de reglas gramaticales llamadas producciones. Se
define además un símbolo Σ llamado símbolo de partida o raíz de
las producciones.

www.inacap.cl

DEFINICIÓN
• Una gramática formal es una 4-tupla G = ( N, T, P, Σ ), tal que:
T = alfabeto (símbolos terminales)
N = alfabeto de...