Pumping Лемма с контекстно-свободными языками

У меня есть язык {a ^ ib ^ jc ^ k | i, j, k> = 0 & i> j & j> k} Я начал с предположения, что для меня выбрано какое-то m , так что строка

   z = a^m b^(m-1) c^(m-2)

Затем строка разбивается на (z =) uvwxy , так что vx не пустые и # (vwx) <= m Затем, когда я выбираю « i », я путаюсь. Скажем, я выбираю i = 1 , тогда у меня есть: uv ^ 1wx ^ 1y , и я не совсем уверен, что с этим делать, потому что мне это кажется например, я мог бы выбрать vwx, который ЕСТЬ на языке.

Есть предложения?

6
задан Alex 10 November 2010 в 21:41
поделиться