Множество слов в произвольном алфавите, которое может быть получено из элементарных множеств путем конечного числа применений операций объединения, конкатенации, итерации, называется:
Множество, которое может быть порождено некоторой вычислимой функцией, называется:
Некоторая процедура, состоящая из конечного числа шагов, строго определенных на конкретном наборе данных, называется:
Множество называется перечислимым, если
Если А - это алфавит, то некоторое подмножество множества всех слов алфавита А называется
Пусть М1 и М2 - некоторые множества, с соответствующими мощностями. Тогда мощность множества М3, полученного путем конкатенации множеств М1 и М2 будет
Результатом конкатенации двух множеств М1 и М2 является множество М3, элементы которого получаются:
Если для любого произвольно взятого элемента можно определить, принадлежит он некоторому множеству или нет, то такое множество называется:
Множество распознаваемо конечным автоматом, если
Машина Тьюринга может быть задана:
