Язык, L = {a^n b^n a^n; п=1,2,3,.. }
Я хочу проверить, является ли данный язык L контекстно-свободным или нет.
CFG использует PDA, который использует стеки. Итак, сначала сохраните каждую букву «а» в стеке. Затем нажмите дважды для каждого вхождения «b». Верна ли эта логика?
Можно показать, что этот язык не является контекстно-свободным, используя лемму о накачке для контекстно-свободных языков. Доказательство от противного. Предположим, что язык является контекстно-свободным. Тогда слова длины не менее p в языке можно записать как uvxyz с |vxy| ‹= р, |вы| › 0 и где u(v^n)x(y^n)z находится в языке для всех целых чисел n. Выберите строку a^p b^p a^p на языке. Следует рассмотреть пять случаев:
vxy состоит только из a из первой части. Накачка вверх или вниз нарушает требование, чтобы количество букв a в первой части равнялось количеству букв b во второй части.
vxy состоит только из a и b из первых двух частей. Накачка может сохранить требование, чтобы количество а в первой части равнялось количеству Ь во второй, но она, безусловно, нарушит требование, чтобы количество а в первой и третьей частях было одинаковым.
vxy состоит только из b из второго раздела. Насос не работает по той же причине, что и в случае 1.
vxy состоит из a и b из второй и третьей частей. Накачка не удалась по причине, аналогичной указанной во втором случае.
vxy состоит только из a из третьего раздела. Насос не работает по той же причине, что и в первом случае.
Итак, нет никакого способа переписать нашу строку a^n b^n a^n так, чтобы она могла быть записана как uvxyz и удовлетворяла требованиям леммы о накачке. Это противоречие, поэтому язык не мог быть регулярным.
