Gramaticas

1.1. LENGUAJE
Un lenguaje es un conjunto de palabras.
1.2. Potencia.
Sea A un lenguaje sobre el alfabeto £.
Definimos

Por tanto, si A = {ab} sobre el alfabeto inglés, se obtiene que1.3. Cadena
Una secuencia finita de símbolos de un determinado alfabeto
1.4. Cadena Vacia
se puede tener una cadena compuesta por ningún simbolo {£}
1.5. Longitud de cadena
longitudse denota mediante el símbolo | w | . La longitud de w es el número de símbolos que tiene la cadena.
1.6. Operaciones con cadenas
Si w y z son cadenas, la concatenación de w con z esla cadena que se obtiene al añadir a la cadena w la palabra z- Por ejemplo, si w = “banana” y Z = “rama”, la concatenación de w con z es la cadena “bananarama”. Laconcatenación de las palabras w y z se denota como wz o w - z . Obsérvese que se tiene que
|wz| = |w| + |z|
La concatenación de la palabra vacía e con cualquier otra palabra w, no modifica a lapalabra w. Por esta razón, £ se comporta como la identidad con respecto a la operación de concatenación.
1.7. Potencia de una cadena
Vamos a introducir la noción de potencia de una palabra sobre unalfabeto. Sea w una palabra; para n e N se define


1.8. Prefijo y sufijo
Las nociones de sufijo y prefijo de cadenas sobre un alfabeto son análogas a las que se usan habitualmente. S i w yj t son palabras, se dice que x es prefijo de w, si para alguna cadena y se obtiene que w = xy. Por ejemplo, si w es la cadena 121, entonces la cadena x = 12 es un prefijo de w e y - 1. Sise considera >• = £, entonces para w = xy se tiene que w = x, con lo que toda palabra puede considerarse prefijo de sí misma. Introduciremos el término prefijo propio para denotar aquellas cadenasque son prefijos de una palabra pero no iguales a la misma. Por éso x= 121 es un prefijo de la cadena w = 121, pero no es un prefijo propio de w. Finalmente hay que tener en cuenta que la...