Сначала давайте исправим распространенное заблуждение: (0+1)* не является бесконечной строкой.Это язык бесконечного числа конечных строк.Различие важно: любая заданная строка в языке конечна, но их бесконечное количество.
L=(0+1)* означает L={'', '0', '1', '00', '01', '10', '11', etc}.Это также показывает, как язык можно считать исчисляемым, если вы перечислите все слова длины 0, затем 1, затем 2 и т. Д. Каждое слово в языке имеет позицию в этом наборе и может быть сопоставлено с натуральными числами.
Все обычные языки являются исчисляемыми наборами слов.Конечные языки тривиально счетны.Бесконечные языки исчисляются, потому что соответствующий DFA можно обойти, перечислив весь язык упорядоченным образом, что позволяет сопоставить все строки с натуральными числами.наука.Это должно помочь: https://math.stackexchange.com/questions/1396896/number-of-non-decreasing-functions. По последнему вопросу это может помочь: https://en.wikipedia.org/wiki/Cantor%27s_theorem