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

Править

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

Старый ответ

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

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

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

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

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

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

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

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