Я читал в книге (Hromkovic, Communication Complexity and Parallel Computing), что существует бесконечное количество нерекурсивно-перечислимых (не-RE) языков, которые состоят только из 1 элемента? Но возможно ли это? Я думал, что для того, чтобы язык не был RE (или даже неразрешимым), он должен быть бесконечным.
Существует ли язык без RE, состоящий только из 1 элемента?
Ответы (1)
Нет, все конечные языки регулярны, потому что они могут быть восприняты конечными автоматами. Есть как минимум три возможных объяснения тому, что вы читаете:
- автор(ы) написал(а) что-то другое, а вы неправильно перефразируете;
- автор(ы) написал(и) не то, что намеревался, возможно, использовал небрежную терминологию;
- автор(ы) написали что-то неправильное из-за непонимания предмета, не относящегося к их специальности.
Если вы процитируете соответствующий отрывок, возможно, удастся выяснить, какой из этих вариантов наиболее вероятен. Обратите внимание, что ошибаются все — и те, кто читает книги, и те, кто пишет книги. Обратите также внимание, что я использую автора (авторов), а не авторов, потому что возможно, что этот отрывок был написан изолированно одним автором и не был должным образом рецензирован.
person
Patrick87
schedule
20.03.2019
Перечитав текст, я думаю, что случай (1) более вероятен: вот более точные слова из доказательства теоремы 2.3.5.5, стр. 81 книги: Существует бесконечно много языков L в LRE со свойством L( n)=1 для каждого n из набора натуральных чисел. (LRE - рекурсивно перечисляемые языки)
- person Link L; 23.03.2019
и L(n) относится к строке, принадлежащей языку L, с длиной 1
- person Link L; 23.03.2019
@LinkL Может быть, они говорят, что существует бесконечно много языков RE, которые содержат строки всех длин натуральных чисел. Это верно. Верно также и то, что существует бесконечно много языков RE, содержащих строки длины 1. Так что да, вероятно, что-то подобное имеется в виду.
- person Patrick87; 24.03.2019
