INTRODUCCIÓN A LA TEORIA DE LENJUAGES FORMALES

Una cadena es una secuencia finita de símbolos de un determinado alfabeto.

 

Ejemplo. Tomando en cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:

abcb es una cadena del alfabeto V2

a+2*b es una cadena del alfabeto V2

000111 es una cadena del alfabeto V3

If a>b then b=a; es una cadena del alfabeto V4

 

La cadena vacía, denotada por  E es aquella que presenta cero apariciones de símbolos, es una cadena que puede construirse en cualquier alfabeto.

 

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, Por ejemplo la concatenación de padre y madre es padremadre. La yuxtaposición se utiliza como el operador de concatenación. Esto es si w y x son cadenas, entonces wx es la concatenación de estas dos cadenas. La cadena vacía es la identidad para el operador de concatenación, es decir Ew=wE para cada cadena de w.