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

Question

У меня проблема с домашней работой, которая требует от вас доказать, является ли язык одним из трех:

1. Обычный язык
2. Контекстно-свободный, но не обычный
3. Не без контекста

Как вы докажете каждому? Я знаю, что Pumping Lemma может проверить, не является ли язык обычным или не контекстным, но это все.

Пример, который поможет мне лучше понять, следующий:

{a ^ (2n + 1) b ^ (3n + 2) | n ∈ N}, алфавит {a, b}, где N - все натуральные числа.

Answer 1

Лемма прокачки для обычных языков может сказать вам, что язык не является регулярным; однако он не может сказать вам, что язык является регулярным. Чтобы сказать, что язык является регулярным, вы должны создать эквивалент конечного автомата, регулярной грамматики или регулярного выражения, а затем доказать, что он подходит для вашего языка.

Лемма прокачки для контекстно-свободных языков говорит вам, является ли язык контекстно-свободным или нет. То есть, если язык удовлетворяет лемме прокачки для языков без контекста, он не зависит от контекста; и если это не так, то это не так. Тем не менее, вы, безусловно, можете использовать его так же, как и лемму прокачки для обычных языков, и вместо этого вы найдете автомат с нажатием кнопки или грамматику без контекста.

В вашем случае мы можем сначала выбрать строку a ^ (2p + 1) b ^ (3p + 2), чтобы показать, что язык не является регулярным по лемме прокачки для обычных языков. Мы можем показать, что язык не зависит от контекста, доказав, что для любой строки вида a ^ (2k + 1) b ^ (3k + 2), где 2k + 1 и 3k + 2 достаточно велики, мы всегда можем выбрать v для содержат 2 a и y, чтобы содержать три b, так что откачка поддерживает требуемое свойство. В качестве альтернативы, мы можем просто дать ему CFG, основываясь на той же мысли:

S -> aaSbbb | abb

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