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