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

Question

Как узнать, являются ли языки контекстно-свободными или нет?

Answer 1

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

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

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

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

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

Answer 2

Редактировать

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

Старый ответ

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

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

Answer 3

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