Lenguajes formales

CIENCIAS DE LA COMPUTACION I

2009

Lenguajes

Alfabeto

Un alfabeto o vocabulario A es un conjunto finito no vacío de símbolos (objetos atómicos o indivisibles).

Ejemplos de alfabetos:

Alfabeto de dígitos decimales D={0,1,2,3,4,5,6,7,8,9};

Alfabeto de dígitos binarios B={0,1}

Alfabeto de las caracteres C={a,b,…z,A,…Z, ?,!…,*,$}

Cadena

Una cadena ω es una sucesión finita de símbolos, sobre un alfabeto A.

Una cadena es simplemente representada como ω =s1s2…sn        donde s1,s2,.. sn   ∈ A

El símbolo si     1≤ i ≤ n, ocurre en la posición i de la cadena.

Por convención, ε denota la cadena vacía (la cadena que no tiene símbolos).

Ejemplo1

Las cadenas α1,   α2   ,α3   ,α4   sobre B={0,1}  se definen como:

α1  = 0101

α2  = 1111

α3  = 0111000

α4  = ε

Clausura sobre el alfabeto A*

El conjunto de todas las posibles cadenas sobre un alfabeto A, se describe como A* también llamado Clausura de Kleene.

i=∞

A*= ∪ Ai

i=0

donde Ai es el conjunto de todas las cadenas de longitud i sobre A

En el ejemplo para el alfabeto B={0,1} calcular B* ={0,1}*

B0 ={ε} B1={0,1}

B2={ 00,01,10,11}

B3={ 000,001,010,011,100,101,110,111}

…

Luego

B*=B0∪ B1∪ B2∪ B3∪….= { ε  0,1,00,01,10,11,000,001,010,011,100,101,110,111,…}

Nota: Las cadenas α1   ,α2   ,α3 ,α4     ∈ B*

Operaciones sobre cadenas

Sean dos cadenas sobre el alfabeto A

ω1=a1a2…an        y        ω2  =b1b2…bm        ω1  , ω2   ∈ A*

• Longitud de la cadena ω1

|ω1| denota la longitud de la cadena ω1.

|ω1| = n

• Igualdad de cadenas ω1   y ω2

ω1   =ω2    si se cumple que  |ω1| = |ω2|  y        (∀i: 1≤ i≤ n: ai= bi )

• Reversa de la cadena ω1

ω R denota la reversa de la cadena ω

1        1

1        n        2 1

ω R=a ….a a

• Concatenación de las cadenas ω1  y ω2

ω1.ω2   denota la concatenación que consiste de todos los símbolos de ω1 seguidos por los símbolos de ω2. (el punto puede omitirse)

ω1.ω2 = a1a2…anb1b2…bm

Propiedades de la concatenación:

1) ω1.ω2     es una cadena sobre A

2) ω1.ε = ε .ω1 = ω1

3) |ω1.ω2| = |ω1| + |ω2|

1        1        1        1

4) No es conmutativa. (puede suceder que para ciertas instancias lo sea) 5) ω .ω = ω 2 (Potencia cuadrada de la cadena ω )

• Potencia k-ésima de la cadena ω1

1

1        1        1        1

1

ω k denota la concatenación de ω con sí misma k-1 veces (o la repetición de ω1

 k veces).

así

1

ω 0 = ε1        1

ω 1 = ω1        1        1

ω 2 = ω . ω…

 ω k  = ω k-1. ω        y ω 0 = ε (por convención)

...