Алфавит – это конечное множество I элементов, называемых символами.
Цепочка или слово в алфавите I – это конечная последовательность элементов (символов) из алфавита I. Например, если алфавит языка состоит только из заглавных и строчных букв латинского алфавита, то любые последовательности этих букв являются цепочками (словами), в том числе цепочка может состоять из одного символа.
С цепочками (словами) могут быть проделаны действия, которые имеют следующие обозначения:
хn. Цепочка символов х повторяется (пишется без пробелов одна за другой) n раз. Например, abba2 – это abbaabba.
хk. Цепочка символов х записывается в обратной последовательности. Например, portR - это trop.
xy. За цепочкой символов x без пробела помещается цепочка символов y.
х*. Цепочка символов х в цикле может повторяться нуль и более раз.
Обычно в алгоритмических языкахaэто действие реализуется циклом с предварительной проверкой условия.
Например: intl iden (‘,’ iden)* ‘;’
Это означает, что за символом intl должно следовать iden. Затем через запятую может еще повторяться iden нуль и более раз. В конце должна быть точка с запятой.
х+. Цепочка символов х должна повторяться один и больше раз. В алгоритмическом языке Pascal это реализуется оператором repeat, а в языке Си – оператором цикла do while.
|х|. Определение длины цепочки символов х (количество символов в цепочке).
{} или l, илиe- обозначение пустой цепочки символов.
[х]. Так обозначается необязательная цепочка символов. Например, такая запись нужна для того, чтобы обозначить, что перед числом знак может быть, а может и отсутствовать.
Кроме алфавита и цепочки символов (слов), важным понятием является язык.
Язык в алфавите I – это произвольное множество цепочек (слов).