Алфавит (формальные языки) - Alphabet (formal languages)

В формальная теория языка, а нить определяется как конечная последовательность членов базовой базы набор; этот набор называется алфавит строки или набора строк.^[1][2] Члены набора называются символы, и обычно рассматриваются как представляющие буквы, символы или цифры.^[1][2] Например, общий алфавит - {0,1}, двоичный алфавит, а двоичная строка представляет собой строку, взятую из алфавита {0,1}. Бесконечный последовательность букв могут быть построены также из элементов алфавита.

Обозначение

Если L является формальным языком, т.е. (возможно, бесконечным) набором строк конечной длины, алфавит L это набор всех символов, которые могут встречаться в любой строке в L.Например, если L это набор всех идентификаторы переменных на языке программирования C, LАлфавит - это набор {a, b, c, ..., x, y, z, A, B, C, ..., X, Y, Z, 0, 1, 2, ..., 7 , 8, 9, _}.

Учитывая алфавит ${\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 }}$ всех конечных или бесконечных последовательностей.

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

Приложения

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

При использовании автоматов обычные выражения, или же формальные грамматики как часть обработки строк алгоритмы, алфавит можно считать набор символов текста, который будет обрабатываться этими алгоритмами, или подмножество допустимых символов из набора символов.

Смотрите также

• Комбинаторика слов

Рекомендации

1. Ахо, Альфред В.; Сетхи, Рави; Ульман, Джеффри Д. (1985). Компиляторы: принципы, методы и инструменты (Переиздание, март 1988 г.). Эддисон-Уэсли. п.92. ISBN  0-201-10088-6. Период, термин алфавит или же класс персонажа обозначает любой конечный набор символов.
2. Ebbinghaus, H.-D .; Flum, J .; Томас, В. (1994). Математическая логика (2-е изд.). Нью-Йорк: Springer. п. 11. ISBN  0-387-94258-0. Автор алфавит ${\displaystyle {\mathcal {A}}}$ мы имеем в виду непустой набор символы.

Литература

• Джон Э. Хопкрофт и Джеффри Д. Уллман, Введение в теорию автоматов, языки и вычисления, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN  0-201-02988-X.