Определение. ЗНАК – это элемент конечного множества различных элементов.
Пример. +,-,*
Определение. АЛФАВИТ – это упорядоченное множество знаков. Порядок элементов в алфавите задает лексикографический порядок.

Пример. Используется в словарях: алфавит от А до Я.

Определение. СИМВОЛ – это знак вместе с сопоставленным ему смыслом.

Пример. Код ASCII: 1 – 00110001.

Определение: СТРОКА (или ЦЕПОЧКА) – это последовательность знаков некоторого алфавита. Строка характеризуется длиной, то есть числом знаков, составляющих эту строку.

Пример. Если у нас есть некоторый алфавит , тогда — есть строка.

Определение. СЛОВО – это строка вместе с сопоставленным ей смыслом.

Определение. МНОЖЕСТВО УНИВЕРСУМ – это множество всех конечных строк в алфавите.
Если задан алфавит , то множество универсум — есть множество строк конечной длины.
Мощность множества счетная, те есть все строки данного множества можно пронумеровать, хотя их число и бесконечно.

Пример. Пусть задан алфавит . Определим множество универсум .
Таким образом, проблема перечисления неразрешима, но мы можем, рассматривая некоторую строку , сказать принадлежит она множеству универсум или нет. Следовательно, проблема распознавания алфавитов разрешима, причем за конечное число шагов.

Определение. МНОЖЕСТВО УНИВЕРСУМ БЕЗ ПУСТОЙ СТРОКИ. Будем обозначать .