Alfabeto (lenguas formales)

Conjunto básico de símbolos con los que se forma una lengua

En la teoría del lenguaje formal , un alfabeto , a veces llamado vocabulario , 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]} Los alfabetos en este sentido técnico de un conjunto se utilizan en una amplia gama de campos, entre ellos la lógica, las matemáticas, la informática y la 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, ) o incluso incontable (por ejemplo, ). ${\displaystyle \{v_{1},v_{2},\ldots \}}$ ${\displaystyle \{v_{x}:x\in \mathbb {R} \}}$

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

A menudo, por razones prácticas, es necesario restringir los símbolos de un alfabeto para que no generen ambigüedades al interpretarlos. Por ejemplo, si el alfabeto de dos miembros es {00,0}, una cadena escrita en papel como "000" es ambigua porque no está 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".

Notación

Si L es un lenguaje formal, es decir, un conjunto (posiblemente infinito) de cadenas de longitud finita, el alfabeto de L es el conjunto de todos los símbolos que pueden aparecer en cualquier cadena en L. Por ejemplo, si L es el conjunto de todos los identificadores de variable en el lenguaje de programación C , el alfabeto de L es el conjunto {a, b, c, ..., x, y, z, A, B, C, ..., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _}.

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

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 (DFA), se requiere especificar un alfabeto a partir del cual se construyen las cadenas de entrada para el autómata. En estas aplicaciones, generalmente se requiere que un alfabeto sea un conjunto finito , pero no está restringido de otra manera.

Al utilizar autómatas, expresiones regulares o gramáticas formales como parte de algoritmos de procesamiento de cadenas , se puede suponer que el alfabeto es el conjunto de caracteres del texto que se procesará mediante estos algoritmos, o un subconjunto de caracteres permitidos del conjunto de caracteres.

Véase también

• Combinatoria sobre palabras
• Símbolos terminales y no terminales

Referencias

1. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Fundamentos de las 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 .
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 alfabeto entendemos un conjunto no vacío de símbolos . ${\displaystyle {\mathcal {A}}}$
3. Rosen, Kenneth H. (2012). Matemática discreta y sus aplicaciones (PDF) (7.ª ed.). Nueva York: McGraw Hill . pp. 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 (u oración) sobre V es una cadena de longitud finita de elementos de V.
4. Rautenberg, Wolfgang (2010). Una breve introducción a la lógica matemática (PDF) (tercera edición). 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 nombrados, entonces la secuencia (𝐬 ₁ ,...,𝐬 _n )∈𝗔 ⁿ se escribe como 𝐬 ₁ ···𝐬 _n y se llama cadena o 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 .