Alfabet (informatică)

În teoria limbajelor formale și teoria informației un alfabet este o mulțime nevidă de simboluri / glife, considerate de obicei ca reprezentând litere, caractere sau cifre.^[1] Printre alte posibilități, „simbolurile” ar putea fi însă și o mulțime de foneme (unități de sunet). În acest sens tehnic ca totalitate de simboluri, alfabetele sunt folosite într-o gamă variată de sectoare științifice, inclusiv în logică, matematică, informatică, lingvistică, teoria informației, bioinformatică, genetică. Un alfabet poate avea orice număr cardinal („mărime”) și, în funcție de scopul său, poate fi finit (de exemplu, alfabetul literelor de la „a” la „z”), numărabil (de exemplu, $\{v_{1},v_{2},\ldots \}$ ), sau chiar nenumărabil (de exemplu, $\{v_{x}:x\in \mathbb {R} \}$ ).

Șirurile de caractere^⁠(d), cunoscute și sub denumirea de „cuvinte”, peste un alfabet sunt definite ca un șir de simboluri din mulțimea-alfabet.^[2] De exemplu, alfabetul literelor mici de la „a” la „z” poate fi folosit pentru a forma cuvinte în limba engleză precum „iceberg”, în timp ce alfabetul atât cu litere mari, cât și cu litere mici poate fi folosit și pentru a forma nume proprii precum „Wikipedia”. Un alfabet care apare frecvent este {0,1}, alfabetul binar și „00101111” este un exemplu de șir binar. Pot exista și șiruri infinite de simboluri.

Adesea, în scopuri practice, este nevoie să se restricționeze simbolurile dintr-un alfabet, astfel încât acestea să nu fie ambigue atunci când sunt interpretate. De exemplu, dacă alfabetul cu doi membri este {00,0}, un șir scris pe hârtie ca „000” este ambiguu, deoarece nu este clar dacă este un șir de trei simboluri „0”, un „00” urmat de un „0” sau un „0” urmat de un „00”.

Notație

Dacă L este un limbaj formal, adică o mulțime (posibil infinită) de șiruri de lungime finită, alfabetul lui L este mulțimea tuturor simbolurilor care pot apărea în orice șir din L. De exemplu, dacă L este mulțimea tuturor identificatorilor de variabile^⁠(d) în limbajul de programare C, alfabetul lui L este mulțimea { a, b, c, ..., x, y, z, A, B, C, . . ., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _ }.

Dat fiind un alfabet $\Sigma$ , mulțimea tuturor șirurilor de lungime $n$ peste alfabetul $\Sigma$ se notează cu $\Sigma ^{n}$ . Mulțimea ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ a tuturor șirurilor finite (indiferent de lungimea lor) se notează, cu ajutorul operatorului Kleene star, cu $\Sigma ^{*}$ , și se mai numește și închiderea Kleene a lui $\Sigma$ . Notația $\Sigma ^{\omega }$ indică mulțimea tuturor șirurilor infinite peste alfabetul $\Sigma$ , și $\Sigma ^{\infty }$ indică mulțimea $\Sigma ^{\ast }\cup \Sigma ^{\omega }$ a tuturor șirurilor finite sau infinite.

De exemplu, folosind alfabetul binar {0,1}, șirurile ε, 0, 1, 00, 01, 10, 11, 000 etc. sunt toate în închiderea Kleene a alfabetului (unde ε reprezintă șirul vid^⁠(d)).

Aplicații

Alfabetele sunt importante în utilizarea limbajelor formale, a automatelor și a semiautomatelor^⁠(d). În cele mai multe cazuri, pentru definirea instanțelor de automate, cum ar fi automatele finite deterministe^⁠(d) (DFA), este necesar să se specifice un alfabet din care sunt construite șirurile de intrare pentru automat. În aceste aplicații, un alfabet trebuie de regulă să fie o mulțime finită, dar nu este restricționat altfel.

Când se utilizează automate, expresii regulate sau gramatici formale^⁠(d) ca parte a algoritmilor de procesare a șirurilor de caractere, se poate presupune că alfabetul este mulțimea caracterelor^⁠(d) al textului care urmează să fie procesat de acești algoritmi sau o submulțime de caractere permise din setul de caractere.

Note

^ Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Mathematical Logic (ed. 2nd). New York: Springer. p. 11. ISBN 0-387-94258-0. By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols.
^ Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (PDF) (ed. Third). Springer. p. xx. ISBN 978-1-4419-1220-6. If 𝗔 is an alphabet, i.e., if the elements 𝐬 ∈ 𝗔 are symbols or at least named symbols, then the sequence (𝐬₁,...,𝐬_n)∈𝗔ⁿ is written as 𝐬₁···𝐬_n and called a string or a word over 𝗔.

Bibliografie

John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation (în engleză). Reading Massachusetts: Addison-Wesley Publishing. ISBN 0-201-02988-X.

[Ebbinghaus-1] Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Mathematical Logic (ed. 2nd). New York: Springer. p. 11. ISBN 0-387-94258-0. By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols.

[Rautenberg-2] Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (PDF) (ed. Third). Springer. p. xx. ISBN 978-1-4419-1220-6. If 𝗔 is an alphabet, i.e., if the elements 𝐬 ∈ 𝗔 are symbols or at least named symbols, then the sequence (𝐬₁,...,𝐬_n)∈𝗔ⁿ is written as 𝐬₁···𝐬_n and called a string or a word over 𝗔.

[1]

[2]