Он L = { w ∈ ∑ * / w он заканчивается в в } регулярный язык?

Я пробую доказывать с девизом накачивания, - регулярный или нет язык ли выражение, описанное в титуле, это - то, что я попробовал:

∑={a,b}

∃(w)∈L y w = a^i b^j a  , siendo i,j>=0

|w| = 2n+1 >=n , cumple la condicion de |w| >= n

Мы знаем, что w = xyz с чем:

|xy| <= n   ^   1 <= |y| <= n

Будучи X=a^p , y=a^q и что p+q<=n я остался бы в конце концов z=a^(n-p-q) b^n a

Таким образом, он остался бы |w|= p+q+n-p-q+n+1

подтверждая свойство: x y^j z ∈ L для всего j> =0, у нас есть, что мы создаем новую цепь с j=2: w' = x y^2 zс чем он остался бы:

p + 2q + n - p - q + n + 1 =  2n + 1

В конце концов он упрощается оставаясь: q+2n+1 = 2n+1 что только верный если q=0 что не может быть, так как свойство самого девиза накачивания говорит 1<=|y|<=n

То, что я не понимаю, что, если, я это применяю с цепью, например:

w = aaaba

С n=2 мы можем делить w в:

x=a
y=a
z=aba

С чем для любой y^i что с нами случилось каждый раз, когда его было> =0, он должен бы быть принятым, так как он заканчивается в a нет??

13
задан 30.07.2019, 14:21
0 ответов