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

В теории формальных языков , A строка определяются как конечная последовательность членов лежащего в основе базового набора ; этот набор называется алфавитом строки или набором строк. ^[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 ^ {п}}$ ${\ textstyle \ bigcup _ {я \ in \ mathbb {N}} \ Sigma ^ {i}}$ ${\ displaystyle \ Sigma ^ {*}}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma ^ {\ omega}}$ ${\ displaystyle \ Sigma}$ ${\ Displaystyle \ Sigma ^ {\ infty}}$ ${\ Displaystyle \ Sigma ^ {\ ast} \ чашка \ Sigma ^ {\ omega}}$

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

Приложения [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Литература [ править ]

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

[aho-1] Ахо, Альфред В .; Сетхи, Рави ; Ульман, Джеффри Д. (1985). Компиляторы: принципы, методы и инструменты (переиздание в марте 1988 г.). Эддисон-Уэсли. п. 92 . ISBN 0-201-10088-6. Термин « алфавит» или « класс символов» обозначает любой конечный набор символов.

[ebbinghaus-2] Ebbinghaus, H.-D .; Flum, J .; Томас, В. (1994). Математическая логика (2-е изд.). Нью-Йорк : Спрингер . п. 11. ISBN 0-387-94258-0. Под алфавитом мы понимаем непустой набор символов . ${\ displaystyle {\ mathcal {A}}}$

[1]