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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

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

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

Личные инструменты

Served in 0.051 secs.