Регулярные выражения. Разрешимость и неразрешимость языков

Определение №37

Разрешимость и неразрешимость языков.

Язык, для которого машина Тьюринга может однозначно решить задачу принадлежности (т.е. определить принадлежит ли данная строка языку или нет) называется разрешимым (или рекурсивным)

Если задачу принадлежности можно решить лишь для строк входящих в язык, то язык называется частично разрешимым (или рекурсивно перечислимым)

Мозговой(стр. 280)

Определение №38

Регулярные выражения

Регуля́рные выраже́ния (англ. regular expressions) — формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов-джокеров, англ. wildcard characters). Для поиска используется строка-образец (англ. pattern, по-русски её часто называют «шаблоном», «маской»), состоящая из символов и метасимволов и задающая правило поиска. Для манипуляций с текстом дополнительно задаётся строка замены, которая также может содержать в себе специальные символы.

Регулярное выражение является шаблоном, описывающим целое семейство (нередко бесконечное) строк.(Мозговой стр.15)

Определение №39

Рекурсивный язык

Рекурсивный язык — тип формального языка, также называемый разрешимым или разрешимым по Тьюрингу. (см. определение №37)

Используется два эквивалентных определения рекурсивного языка:

Формальный рекурсивный язык - рекурсивное подмножество множества всех возможных слов в алфавите формального языка.

Рекурсивный язык - формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает её тогда и только тогда, когда она принадлежит языку. Говорят, что такая машина является решателем и разрешает данный рекурсивный язык.

Все рекурсивные языки также являются рекурсивно перечислимыми. Все регулярные, контекстно-свободные и контекстно-зависимые языки рекурсивны.

Определение №40

Сведение задач

Сведе́ние — преобразование одной задачи к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры задачи в экземпляры задачи , которые имеют тот же ответ (да/нет), то говорят, что сводится к . Таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или её принадлежность тому или иному классу сложности.

Самым общим типом сведения является Сведение по Тьюрингу, оно же - Сведение по Куку. В данном случае некоторый алгоритм (вычислимый на машине Тьюринга) может быть вызван любое количество раз, при этом каждый вызов будет считаться за один шаг алгоритма. Для формального определения сводимости по Тьюрингу используется понятие Тьюринг-машины с оракулом.

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

Если такой алгоритм существует, говорят, что сводима по Куку к и пишут

Неформально в таком случае говорят, что «как минимум так же сложна» как .

Если задача сводится по Куку к задаче , то решение задачи может быть использовано для решения задачи следующим образом: при запросе алгоритма, вычисляющего , к оракулу используется соответствующее решение . Так как машина Тьюринга может делать запросы к оракулу большое количество раз, итоговый алгоритм решения задачи может потребовать асимптотически больше времени, чем алгоритм, решающий задачу .

Определение №41

Семантика.

Сема́нтика в программировании — дисциплина, изучающая формализации значений конструкций языков программирования посредством построения их формальных математических моделей. В качестве инструментов построения таких моделей могут использоваться различные средства, например, математическая логика, λ-исчисление, теория множеств, теория категорий, теория моделей, универсальная алгебра. Формализация семантики языка программирования может использоваться как для описания языка, определения свойств языка, так и для целей формальной верификации программ на этом языке программирования.

Семантика языка — это смысловое значение слов. В программировании — начальное смысловое значение операторов, основных конструкций языка и т. п.

Определение №42

Синтаксис.

Синтаксис языка программирования — набор правил, описывающий комбинации символов алфавита, считающиеся правильно структурированной программой(документом) или её фрагментом. Синтаксису языка противопоставляется его семантика. Синтаксис языка описывает «чистый» язык, в то же время семантика приписывает значения (действия) различным синтаксическим конструкциям.

Каждый язык программирования имеет синтаксическое описание. Синтаксис языка можно описать, например, с помощью правил Бэкуса — Наура.

Синтаксис проверяется на ранних стадиях трансляции. В интерпретируемых языках программирования проверка синтаксиса производится или в процессе интерпретации (выполнения), или в процессе предварительной компиляции в промежуточный код. Кроме того, синтаксис может проверяться непосредственно при редактировании исходных текстов программ при использовании IDE.

Синтаксис записи функции — жёсткое правило, которому должна удовлетворять запись кода функции; форма записи функции. Если синтаксис функции будет неверен, компилятор вернет ошибку и программа не будет собрана, пока ошибка не будет исправлена.

К синтаксическим ошибкам записи функции относятся (неправильная сигнатура):

неверное написание названия функции при её вызове (неверный регистр символов для регистрострогих языков, неверное пространство имен);

неверное количество аргументов;

неверный тип переданных аргументов (например, нужно передать строковое значение, а передано числовое);

неверный тип возвращаемого значения (в частности, неуказанный тип).