Как определить, свободен ли язык в контексте или нет?

Ответ 1

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

Эквивалентная конструкция будет pushdown automaton. Это то же самое, что и DFA, но со стеком. Это может быть проще, чем грамматика.

Однако, если вам не удалось создать грамматику или автомат, это не означает, что язык не является контекстным; возможно, именно вам, кто не может построить грамматику достаточно сложно (например, я однажды потратил около 7 часов на создание грамматики для сложного языка).

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

Эта лемма является следствием леммы Огдена. Таким образом, Огден более мощный, и если вам не удалось применить лемму о перекачке, вы можете попробовать Огден (он использовал тот же путь).

Ответ 2

Edit

Как было предложено в комментариях, чтобы доказать, что язык не является CFG, я считаю, что он использует лемму Огденса. Собственное неверное истолкование, содержащееся в моем предыдущем ответе, должно быть оправдано:) Сохранение более раннего ответа для lurkers.

Старый ответ

Изучая грамматику и используемые правила! Как видно из изображения (любезность википедии хомской иерархии). Только обычные языки не являются контекстно-зависимыми. Подразумевая, что все, что используется в формах A- > aB или A- > Ba, не является свободным от контекста.

Edit Определения A- > aB и A- > Ba предназначены для выражения левых и правых рекурсивных грамматик и не должны восприниматься буквально.

Ответ 3

Вам нужна грамматика для языка, чтобы определить, свободен ли он. Грамматика свободна от контекста, если все ее производные имеют форму "(не терминал) → последовательность терминалов и нетерминалов".