Alfabeto (linguagens formais) - Alphabet (formal languages)

Na teoria da linguagem formal , um alfabeto é um conjunto não vazio de símbolos / glifos , normalmente considerado como uma representação de letras, caracteres ou dígitos, mas, entre outras possibilidades, os "símbolos" também podem ser um conjunto de fonemas (unidades de som). Os alfabetos, neste sentido técnico de conjunto, são usados ​​em diversos campos, incluindo lógica, matemática, ciência da computação e linguística. Um alfabeto pode ter qualquer cardinalidade ("tamanho") e dependendo de sua finalidade pode ser finito (por exemplo, o alfabeto das letras de "a" a "z"), contável (por exemplo, ) ou mesmo incontável (por exemplo, ). ${\ displaystyle \ {v_ {1}, v_ {2}, \ ldots \}}$${\ displaystyle \ {v_ {x}: x \ in \ mathbb {R} \}}$

Strings , também conhecidas como "palavras", sobre um alfabeto são definidas como uma sequência de símbolos do conjunto. Por exemplo, o alfabeto de letras minúsculas de "a" a "z" pode ser usado para formar palavras em inglês como "iceberg", enquanto o alfabeto de letras maiúsculas e minúsculas também pode ser usado para formar nomes próprios como "Wikipedia". Um alfabeto comum é {0,1}, o alfabeto binário , e "00101111" é um exemplo de string binária . Seqüência infinita de símbolos também pode ser considerada.

Freqüentemente, é necessário, para fins práticos, restringir os símbolos em um alfabeto para que não sejam ambíguos quando interpretados. Por exemplo, se o alfabeto de dois membros for {00,0}, uma string escrita no papel como "000" é ambígua porque não está claro se é uma sequência de três símbolos "0", um "00" seguido por um "0" ou "0" seguido de "00".

Notação

Se L é uma linguagem formal, ou seja, um (possivelmente infinito) conjunto de strings de comprimento finito, o alfabeto de L é o conjunto de todos os símbolos que podem ocorrer em qualquer cadeia em L . Por exemplo, se L é o conjunto de todos os identificadores de variáveis na linguagem de programação C , o alfabeto de L é o conjunto {a, b, c, ..., x, y, z, A, B, C, .. ., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _}.

Dado um alfabeto , o conjunto de todas as sequências de comprimento sobre o alfabeto é indicado por . O conjunto de todas as strings finitas (independentemente de seu comprimento) é indicado pelo operador estrela de Kleene como e também é chamado de fechamento de Kleene de . A notação indica o conjunto de todas as sequências infinitas sobre o alfabeto e indica o conjunto de todas as sequências finitas ou 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 exemplo, usando o alfabeto binário {0,1}, as strings ε, 0, 1, 00, 01, 10, 11, 000, etc. estão todas no fechamento Kleene do alfabeto (onde ε representa a string vazia ) .

Formulários

Os alfabetos são importantes no uso de linguagens formais , autômatos e semiautomáticos . Na maioria dos casos, para definir instâncias de autômatos, como autômatos finitos determinísticos (DFAs), é necessário especificar um alfabeto a partir do qual as strings de entrada para o autômato são construídas. Nessas aplicações, geralmente exige-se que um alfabeto seja um conjunto finito , mas não é restrito de outra forma.

Ao usar autômatos, expressões regulares ou gramáticas formais como parte de algoritmos de processamento de strings , o alfabeto pode ser considerado o conjunto de caracteres do texto a ser processado por esses algoritmos ou um subconjunto de caracteres permitidos do conjunto de caracteres.

Veja também

• Combinatória de palavras

Referências

Literatura

• John E. Hopcroft e Jeffrey D. Ullman, Introdução à Teoria dos Autômatos, Linguagens e Computação , Publicação Addison-Wesley, Reading Massachusetts, 1979. ISBN   0-201-02988-X .