Alfabeto (ciência da computação)

Em ciência da computação e em lógica matemática, um alfabeto é um conjunto de símbolos, como letras ou dígitos. O alfabeto mais comum é ${0,1}$, o alfabeto binário. Uma cadeia finita é uma sequência finita de letras de símbolos de um determinado alfabeto; por exemplo, uma cadeia binária é uma cadeia formada pelo alfabeto binário.

Dado um alfabeto $\Sigma$, escreve-se $\Sigma^*$ para definir o conjunto de todas as cadeias formadas a partir do alfabeto $\Sigma$. Neste caso, ${}^*$ define o operador fecho de Kleene. Escreve-se $\Sigma^\infty$ (ou, ocasionalmente, $\Sigma^\N$ ou $\Sigma^\omega$) para definir o conjunto de todas as sequências infinitas formadas a partir do alfabeto $\Sigma$.

Por exemplo, usando o alfabeto binário ${0,1}$, as cadeias ${\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots}$ estariam no fechamento do alfabeto; $\varepsilon$ representa a cadeia vazia.

Alfabetos são importantes em linguagens formais, autômatos e semiautômatos.

Ver também

• Linguagem formal