Алфавіт (інформатика)

В інформатики алфавіт - це безліч (як правило кінцеве) символів або літер, наприклад латинських букв і цифр. Прикладом поширеного алфавіту є двійковий алфавіт {0,1}. Кінцева рядок - це кінцева послідовність букв алфавіту. Наприклад, двійкова рядок - це рядок із символів алфавіту {0,1}. Також можлива побудова нескінченних послідовностей з букв алфавіту.

Нехай дано алфавіт \ Sigma . Тоді \ Sigma ^ * позначає безліч всіляких рядків із символів алфавіту \ Sigma . Тут {} ^ * позначений оператор зірка Кліні. Запис \ Sigma ^ \ infty (Або іноді \ Sigma ^ \ N або \ Sigma ^ \ omega ) Позначає безліч всіх нескінченних послідовностей символів з алфавіту \ Sigma .

Наприклад, для алфавіту {0,1} рядки {ε, 0, 1, 00, 01, 10, 11, 000, і так далі} складають його замикання Кліні (де ε позначає порожній рядок).

Алфавіти відіграють важливу роль в теорії формальних мов, автоматів і напівавтоматів. У більшості випадків для визначення сутності автоматів, таких як детермінований кінцевий автомат (ДКА), потрібно задати алфавіт, з якого складаються вхідні рядки для автомата.