Я знаю, что этот вопрос задавался ранее, но, честно говоря, я не совсем понимаю его.
В настоящее время я изучаю теорию вычислений и подхожу к термину «Докажите, что язык разрешимый, узнаваемый или регулярный».
Проще говоря, что они на самом деле означают и как мы можем это доказать?
Речь идет о языке 
над алфавитом 
, что означает, что 
( состоит из слов, состоящих из букв из ).
означает, что существует машина Тьюринга 
, так что 
будет останавливать и принимать для любого входного слова 
и останавливать и отклонять для любого входного слова 
.
означает, что существует машина Тьюринга , так что будет останавливать и принимать для любого входного слова и останавливать или не останавливать (но не останавливать и принимать!) для любого ввода 
.
см. также разницу в Распознаваемые и решаемые на MathExchange.
означает, что 
можно создать с помощью регулярных выражений. Важно отметить, что эти регулярные выражения в теоретической информатике отличаются от функций RegEx, известных в таких языках программирования, как PERL или Java. На самом деле, эти регулярные выражения действительно более мощные (неизвестно, правильный ли это английский термин), чем регулярные выражения.
Хорошее определение регулярных выражений дается здесь:
Для алфавита
и 
(пустой набор и пустое слово) - регулярное выражение.
для любых 
(любая буква из алфавита) - регулярное выражение
and 
are regular expressions, these are regular expressions, too:
(meaning or )
(что означает объединение и 
)
(имеется в виду , любое количество повторений 
или пустое слово 
)и ничто другое не является регулярным выражением.
Чтобы доказать разрешимость или узнаваемость, часто проще всего снабдить машину Тьюринга желаемыми атрибутами. Благодаря тезису Черча-Тьюринга любой язык программирования столь же мощный как машину Тьюринга. Поэтому в моих курсах было вполне приемлемо предоставить алгоритм на языке программирования или псевдокоде.
Обратите внимание, что любой распознаваемый язык также разрешим (но не наоборот).
Чтобы доказать регулярность, в большинстве случаев проще всего просто предоставить регулярное выражение, которое создает язык. Иногда требуется доказать, что регулярное выражение действительно создает в точности , что обычно не слишком сложно (часто это просто очевидно).
Во многих лекциях существует соглашение о регулярных выражениях, позволяющее использовать более интуитивно понятный и короткий (но не более мощный) синтаксис.
Может быть интересно узнать, что обычные языки - это именно те языки, которые могут распознаваться конечными автоматами . Обратите внимание, что любой регулярный язык также разрешим (и, следовательно, узнаваем).
Чтобы опровергнуть регулярность, я просто упомяну лемму о перекачке для обычных языков.
