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

Question

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

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

спасибо.

Answer 1

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

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

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

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

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