1
Se puede realizar aún si los lenguajes no están construidos sobre el mismo alfabeto, en tal caso la concatenación nos lleva a que, si y, son lenguajes sobre y , entonces el lenguaje resultante será un lenguaje sobre .
2
son caracteres secuenciales dentro de una cadena.
3
Un alfabeto es un conjunto finito no vacío, cuyos elementos se denominan letras o símbolos. Denotamos un alfabeto arbitrario con la letra Σ.
4
Es la unión de una o más potencias de A en ∑, resultando en un lenguaje que contiene, todas las cadenas excepto la cadena vacía ϵ, y se denota.
5
Es el número de posiciones ocupada por símbolos dentro de la cadena.
6
Inversa: es una palabra sobre ∑, la palabra inversa de x, x-1 es la palabra que tiene los símbolos de x puestos en sentido inverso. Sin embargo esta no es la definición más formal, esta sí: Dada x palabra sobre ∑, definimos la palabra inversa según el tamaño de las palabras 1. Si |x|=0 si x= λ x-1= λ 2.
7
: Un prefijo de una cadena x es una subcadena inicial de x, es decir una cadena y es un prefijo si existe una cadena z tal que x = yz y de manera similar z es un sufijo de x. 3.2.2.
8
Es una secuencia ordenada (de longitud arbitraria, aunque finita) de elementos que pertenecen a un cierto lenguaje formal o alfabeto análogas a una fórmula o a una oración.
9
que hacen que una palabra pertenezca a un lenguaje. Sea Σ, L ∈Σ * y . x . una palabra cualquiera que no tiene por qué pertenecer a . L: z. Se dice que el par de palabras . u, v ∈Σ * es un contexto válido de . x. en L si se cumple: u . x . v ∈ L. z
10
: Es una operación unaria que se aplica sobre un conjunto de cadenas de caracteres o un conjunto de símbolos o caracteres (alfabeto), y representa el conjunto de las cadenas que se pueden formar tomando cualquier número de cadenas del conjunto inicial, posiblemente con repeticiones, y concatenándolas entre sí.
