Для языка {a ^ 2 ^ n | п> = 0}
Я понимаю, что сначала выбирается какое-то k, а затем z = uvwxy такое, что vx! = Epsilon и # (vwx) ‹= k, но я не могу придумать ни одного i, которое доказывает, что этот язык не является контекстно-свободным.
Лемма о накачке на контекстно-свободном языке
comment
Это, вероятно, больше подходит для сайтов обмена стеками математики или компьютерных наук.
- person Preston Guillot schedule 17.01.2015
Ответы (1)
Вот подсказка: если вы рассматриваете любую степень двойки, превышающую k (скажем, 2 k), то 2 k + k не является степенью двойки, поскольку
2 k + k ‹2 k + 2 k = 2 k + 1
Посмотрите, может ли это помочь вам выбрать правильную струну и выбрать i.
Надеюсь это поможет!
person
templatetypedef
schedule
17.01.2015
