Изменения

'''Докажем, что он неконтестноне контестно-свободный'''. Для этого воспользуемся [[Лемма_Огдена|Леммой Огдена]]. Для фиксированного <tex>n</tex> рассмотрим слово <tex>\omega=a^n b^n c^{n!+n}</tex>. Пометим все символы <tex>a</tex> и <tex>b</tex>. Пусть <tex>\omega</tex> разбили на <tex>u, v, x, y, z</tex>, так что <tex>x</tex> содержит выделенную позицию; <tex>u</tex> и <tex>v</tex> содержат выделенные позиции и <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций. Тогда очевидно, что <tex>vy</tex> должно содержать одинаковое число символов <tex>a</tex> и <tex>b</tex>, иначе выбираем <tex>k=0</tex> и тогда количество символов <tex>a</tex> и <tex>b</tex> станет разным. Пусть символов <tex>a</tex> в <tex>vy</tex> будет <tex>t</tex>. Так же очевидно, что <tex>vy</tex> не содержит символов <tex>c</tex>, так как <tex>vxy</tex> содержат не более <tex>n</tex> выделенных позиций, но <tex>v</tex> точно содержит символ <tex>a</tex>. Тогда выберем <tex dpi=120>k=\frac{n!}{t}+1</tex> и получим слово <tex>a^{n!+n}b^{n!+n}c^{n!+n}</tex>, которое не принадлежит рассмотренному языку. Значит <tex>a^{n}b^{n}c^{i}</tex> не является контекстно-свободным.