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

Question

Мой профессор ожидает, что мы быстро узнаем, является ли данный язык регулярным, контекстно-свободным, но не регулярным, или не контекстно-свободным (другими словами, без рисования КПК, написания контекстно-свободной грамматики и использования накачанной леммы для контекста языки).

Мне известны советы, которые помогают нам быстро понять, что такое обычный язык с первого взгляда, но не о том, является ли язык свободным от контекста.

Спасибо.

Answer 1

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

• считать одновременно в двух местах, как в ^ NB ^ N,
• также многократно, как в ^ нб ^ на ^ мб ^ м
• или вложенный как в ^ nb ^ ma ^ mb ^ n
• палиндромные паттерны, то есть w, за которым следует обратное w
• посчитать число одной буквы против другой, как в "словах с равным количеством a и b" или "слов на 5 больше, чем b"

Типичные вещи, которые CF не может сделать:

• считать одновременно в трех местах, как в ^ NB ^ NC ^ N
• считать одновременно дважды в двух пересечениях пары мест, как в ^ NB ^ ма ^ NB ^ м
• две заказанные копии как ww
• сравните числа трех букв, как в "словах с равным числом a, b и c".

Имея в виду эти шаблоны, вы должны быть в состоянии определить контекстную свободу наиболее распространенных примеров языков.