Существует ли не-RE язык, который состоит только из 1 элемента? - PullRequest
1 голос
/ 18 марта 2019

Я прочитал в книге (Хромкович, Сложность общения и параллельные вычисления), что существует бесконечное количество нерекурсивно-перечислимых (не-RE) языков, которые состоят только из одного элемента?Но возможно ли это?Я думаю, что для того, чтобы язык не был RE (или даже неразрешим), язык должен быть бесконечным.

1 Ответ

1 голос
/ 20 марта 2019

Нет, все конечные языки регулярны, потому что они могут быть приняты конечными автоматами.Существует по крайней мере три возможных объяснения того, что вы прочитали:

  1. автор (ы) написал что-то другое, а вы неправильно перефразировали;
  2. автор (ы) написал что-то другое, кромечто они намеревались, возможно, используя неаккуратную терминологию;
  3. автор (ы) написал что-то неправильное из-за неправильного понимания предмета, не принадлежащего их специальности.

Если вы цитируете соответствующуюпрохождение, можно было бы изучить, какой из этих вариантов наиболее вероятен.Обратите внимание, что все делают ошибки - люди, которые читают книги, и люди, которые пишут книги одинаково.Также обратите внимание, что я использую автора (ов), а не авторов, поскольку вполне возможно, что этот отрывок был написан отдельно одним автором и не был должным образом рассмотрен.

...