Alfabeto (lenguajes formales)

En la teoría del lenguaje formal , un alfabeto , a menudo llamado vocabulario en el contexto de símbolos terminales y no terminales , es un conjunto no vacío de símbolos / caracteres / glifos indivisibles , ^{[ 1 ]} que normalmente se considera que representan letras, caracteres, dígitos, fonemas o incluso palabras. ^{[ 2 ]}^{[ 3 ]} La definición se utiliza en una amplia gama de campos que incluyen lógica, matemáticas, informática y lingüística. Un alfabeto puede tener cualquier cardinalidad ("tamaño") y, dependiendo de su propósito, puede ser finito (por ejemplo, el alfabeto de las letras "a" a "z"), contable (por ejemplo, $\{v_{1},v_{2},\ldots \}$ ), o incluso incontables (por ejemplo, $\{v_{x}:x\in \mathbb {R} \}$ ).

Las cadenas , también conocidas como "palabras" u "frases", sobre un alfabeto se definen como una secuencia de los símbolos del conjunto del alfabeto. ^{[ 4 ]} Por ejemplo, el alfabeto de letras minúsculas "a" a "z" se puede usar para formar palabras en inglés como "iceberg", mientras que el alfabeto de letras mayúsculas y minúsculas también se puede usar para formar nombres propios como "Wikipedia". Un alfabeto común es {0,1}, el alfabeto binario , y "00101111" es un ejemplo de una cadena binaria . También se pueden considerar secuencias infinitas de símbolos (véase el lenguaje Omega ).

Las cadenas de caracteres suelen escribirse como la concatenación de sus símbolos, y al usar esta convención de notación, resulta práctico restringir los símbolos de un alfabeto para que esta notación sea inequívoca. Por ejemplo, si el alfabeto de dos elementos es {00,0}, una cadena escrita en forma concatenada como "000" es ambigua porque no queda claro si se trata de una secuencia de tres símbolos "0", un "00" seguido de un "0", o un "0" seguido de un "00". Sin embargo, esta es una limitación de la notación para escribir cadenas, no de sus definiciones subyacentes. Como cualquier conjunto finito, {00,0} puede usarse como alfabeto, cuyas cadenas pueden escribirse inequívocamente con una convención de notación diferente, separando sus elementos con comas: 0,00 ≠ 0,0,0 ≠ 00,0.

Notación

Por definición , el alfabeto de un lenguaje formal $L$ encima $\Sigma$ es el conjunto $\Sigma$ , que puede ser cualquier conjunto no vacío de símbolos del cual cada cadena en $L$ está construido. Por ejemplo, el conjunto $\Sigma =\{\_,\mathrm {a} ,\dots ,\mathrm {z} ,\mathrm {A} ,\dots ,\mathrm {Z} ,0,\mathrm {1} ,\dots ,\mathrm {9} \}$ puede ser el alfabeto del lenguaje formal $L$ eso significa "todos los identificadores de variables en el lenguaje de programación C ". No es necesario utilizar todos los símbolos del alfabeto de $L$ por sus cuerdas.

Dado un alfabeto $\Sigma$ , el conjunto de todas las cadenas de longitud $n$ sobre el alfabeto $\Sigma$ está indicado por $\Sigma ^{n}$ . El conjunto ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ de todas las cadenas finitas (independientemente de su longitud) se indica mediante el operador estrella de Kleene como $\Sigma ^{*}$ y también se denomina cierre de Kleene de $\Sigma$ . La notación $\Sigma ^{\omega }$ indica el conjunto de todas las secuencias infinitas sobre el alfabeto. $\Sigma$ , y $\Sigma ^{\infty }$ indica el conjunto $\Sigma ^{\ast }\cup \Sigma ^{\omega }$ de todas las secuencias finitas o infinitas.

Por ejemplo, utilizando el alfabeto binario {0,1}, las cadenas ε, 0, 1, 00, 01, 10, 11, 000, etc. están todas en el cierre de Kleene del alfabeto (donde ε representa la cadena vacía ).

Aplicaciones

Los alfabetos son importantes en el uso de lenguajes formales , autómatas y semiautómatas . En la mayoría de los casos, para definir instancias de autómatas, como los autómatas finitos deterministas (AFD), es necesario especificar un alfabeto a partir del cual se construyen las cadenas de entrada para el autómata. En estas aplicaciones, generalmente se requiere que el alfabeto sea un conjunto finito , pero no está sujeto a ninguna otra restricción.

Cuando se utilizan autómatas, expresiones regulares o gramáticas formales como parte de algoritmos de procesamiento de cadenas , se puede asumir que el alfabeto es el conjunto de caracteres del texto que van a procesar estos algoritmos, o un subconjunto de caracteres permitidos del conjunto de caracteres.

Véase también

Referencias

↑ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Fundamentos de matemáticas discretas . PWS-Kent. pág. 114. ISBN 0-53492-373-9Un alfabeto es un conjunto finito no vacío cuyos miembros se denominan símbolos o caracteres .
↑ Ebbinghaus, H.-D .; Flum, J.; Thomas, W. (1994). Lógica matemática (2.ª ed.). Nueva York : Springer . pág. 11. ISBN 0-387-94258-0Por un alfabeto ${\mathcal {A}}$ nos referimos a un conjunto no vacío de símbolos .
↑ Rosen, Kenneth H. (2012). Matemáticas discretas y sus aplicaciones (PDF) (7.ª ed.). Nueva York: McGraw Hill . págs. 847–851 . ISBN 978-0-07-338309-5Un vocabulario (o alfabeto) V es un conjunto finito y no vacío de elementos llamados símbolos. Una palabra (o frase) sobre V es una cadena de longitud finita formada por elementos de V.
↑ Rautenberg, Wolfgang (2010). Una introducción concisa a la lógica matemática (PDF) (Tercera ed.). Springer. p. xx. ISBN 978-1-4419-1220-6. Si 𝗔 es un alfabeto , es decir, si los elementos 𝐬 ∈ 𝗔 son símbolos o al menos símbolos con nombre, entonces la secuencia (𝐬 ₁ ,...,𝐬 _n )∈𝗔 ⁿ se escribe como 𝐬 ₁ ···𝐬 _n y se llama una cadena o una palabra sobre 𝗔.

Literatura

John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación , Addison-Wesley Publishing, Reading, Massachusetts, 1979. ISBN 0-201-02988-X.

[1] Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Fundamentos de matemáticas discretas . PWS-Kent. pág. 114. ISBN 0-53492-373-9Un alfabeto es un conjunto finito no vacío cuyos miembros se denominan símbolos o caracteres .

[Ebbinghaus1994-2] Ebbinghaus, H.-D .; Flum, J.; Thomas, W. (1994). Lógica matemática (2.ª ed.). Nueva York : Springer . pág. 11. ISBN 0-387-94258-0Por un alfabeto ${\mathcal {A}}$ nos referimos a un conjunto no vacío de símbolos .

[3] Rosen, Kenneth H. (2012). Matemáticas discretas y sus aplicaciones (PDF) (7.ª ed.). Nueva York: McGraw Hill . págs. 847–851 . ISBN 978-0-07-338309-5Un vocabulario (o alfabeto) V es un conjunto finito y no vacío de elementos llamados símbolos. Una palabra (o frase) sobre V es una cadena de longitud finita formada por elementos de V.

[Rautenberg-4] Rautenberg, Wolfgang (2010). Una introducción concisa a la lógica matemática (PDF) (Tercera ed.). Springer. p. xx. ISBN 978-1-4419-1220-6. Si 𝗔 es un alfabeto , es decir, si los elementos 𝐬 ∈ 𝗔 son símbolos o al menos símbolos con nombre, entonces la secuencia (𝐬 ₁ ,...,𝐬 _n )∈𝗔 ⁿ se escribe como 𝐬 ₁ ···𝐬 _n y se llama una cadena o una palabra sobre 𝗔.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]