Изменения

'''Алфавит''' (англ. ''alphabet'') {{---}} конечное непустое [[Множества|множество]] элментов, называемых '''символами''' (англ. ''symbols''). Условимся обозначать алфавит символом большой греческой буквой <tex>\Sigma</tex>.

'''Слово''' (англ. ''string'' {{---}} ''слово'', ''цепочка''') {{---}} конечная последовательность символов некоторого алфавита.

'''Язык''' (англ. ''language'') над алфавитом <tex>\Sigma</tex> {{---}} некоторое подмножество <tex>\Sigma^*</tex>. Иногда такие языки называют '''формальными'''(англ. ''formal''), чтобы подчеркнуть отличие от языков в привычном смысле.

Пусть <tex>x, y \in \Sigma^*</tex>. Тогда <tex>xy</tex> обозначает их '''конкатенацию'''(англ. ''concatenation''), т.е. цепочку, в которой последовательно записаны цепочки x и y.