КПК, чтобы принять язык с больше а, чем б и с

Question

Мой вопрос похож на этот один.Мне было интересно, существует ли PDA, который принимает любые слова, содержащие a, b и c, в случайном порядке, где общее количество a больше, чем количество b, и больше, чем количество c, например, слово"abcacba" будет принято.

Answer 1

Это не контекстно-свободный язык.Доказательством является лемма накачки для контекстно-свободных языков.Предположим, что язык не зависит от контекста.Тогда каждая строка на языке, длина которой больше p, может быть переписана как uvxyz так, что | vxy |

0 и для каждого натурального числа k u (v ^ k) x (y ^ k) z также является строкой в ​​языке.Теперь рассмотрим строку [a ^ (p + 1)] [b ^ p] [c ^ p].Есть несколько способов написать это как uvxyz.Рассмотрим все возможные случаи для подстроки vxy:

1. , прокачиваемая часть vxy состоит только из a.Накачка работает, но k = 0 является допустимым выбором, а откачка не удалась, так как откачка уменьшит число a по крайней мере на один.
2. перекачиваемая часть vxy состоит из a и b: откачка будетуменьшайте a, не уменьшая c, нарушая требование.
3. прокачиваемая часть vxy состоит только из b: накачка увеличит число b выше фиксированного числа a, нарушая требование.
4. прокачиваемая часть vxy состоит из b и c: накачка увеличит количество b и c без изменения числа a, нарушая требование.
5. прокачиваемая часть vxy состоит только из c: накачка увеличит число с, не изменяя количество а, нарушая требование.

Следовательно, нет способа написать наше слово как uvxyz, удовлетворяя при этом требованиям леммы прокачки,противоречие.Поэтому наше предположение о том, что язык не зависит от контекста, опровергнуто.