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

Эту страницу предлагается объединить с Алфавит (математика). Пояснение причин и обсуждение — на странице Википедия:К объединению/14 сентября 2012. Обсуждение длится одну неделю (или дольше, если оно идёт медленно). Дата начала обсуждения — 2012-09-14. Если обсуждение не требуется (очевидный случай), используйте другие шаблоны. Не удаляйте шаблон до подведения итога обсуждения.

У этого термина существуют и другие значения, см. Алфавит (значения).

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

Пусть дан алфавит $\Sigma$. Тогда $\Sigma^*$ обозначает множество всевозможных строк из символов алфавита $\Sigma$. Здесь ${}^*$ обозначен оператор звезда Клини. Запись $\Sigma^\infty$ (или иногда $\Sigma^\N$ или $\Sigma^\omega$) обозначает множество всех бесконечных последовательностей символов из алфавита $\Sigma$.

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

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

См. также

• Алфавит (математика)

Для улучшения этой статьи желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.