Alfabeto
ALFABETO Se llama alfabeto a un conjunto finito, no vacío, cuyos elementos se denominan “letras” o “símbolos”. Se denomina palabra a toda secuencia finita de letras formada con los símbolos de un alfabeto. Se definen los alfabetos por la enumeración de los símbolos que contiene. Un "símbolo" es una entidad abstracta. Las letras y los dígitos son ejemplos de símbolos usados con frecuencia. Se utilizan meta–símbolos (tal como {, }, =, y la coma) para escribir sobre lo que hablamos. Desde el contexto siempre será claro, si se trata de un símbolo del alfabeto o si se trata de un meta–símbolo. Usamos subíndices para distinguir diferentes alfabetos. …ver más…
Es decir,
|u| = 0, si u = λ, n, si u = a1a2 • • • an
Ejemplo |aba| = 3, |baaa| = 4.
Ejemplo Si w ∈ Σ∗, n, m ∈ N, demostrar que
|wn+m| = |wn| + |wm|
Una cadena v es una subcadena o una subpalabra de u si existen cadenas x, y tales que u = xvy. Nótese que x o y pueden ser λ y, por lo tanto, la cadena vacía es una subcadena de cualquier cadena.
Un prefijo de u es una cadena v tal que u = vw para alguna cadena w ∈ Σ ∗Se dice que v es un prefijo propio si v ≠ u.
Similarmente, un sufijo de u es una cadena v tal que u = wv para alguna cadena w ∈ Σ∗
Se dice que v es un sufijo propio si v ≠ u.
Obsérvese que λ es un prefijo y un sufijo de toda cadena u ya que uλ = λu = u.
Por la misma razón, toda cadena u es prefijo y sufijo de sí misma.
Ejemplo Sea Σ = {a, b, c, d}, u = bcbaadb.
Prefijos de u: Sufijos de u: λ b bc bcb bcba bcbaa bcbaad bcbaadb
Lenguaje. Escriba tres ejemplos. Indique tres operaciones entre lenguajes y de ejemplos para cada operación.
Un lenguaje L sobre un alfabeto Σ es un subconjunto de Σ∗, es decir L ⊆ Σ∗.
Casos extremos:
L = ∅, lenguaje vacío.
L = Σ∗, lenguaje de todas las cadenas sobre Σ.
Todo lenguaje L satisface ∅ ⊆ L ⊆ Σ∗, y puede ser finito o infinito. Los lenguajes se denotan con letras mayúsculas A, B, C, . . . , L, M, N, . . .. En la siguiente gràfica se visualizan dos lenguajes A y B sobre Σ.
Ejemplo de