Pumping lemma - rozklad
asked 2014-12-07 11:48:14 +0100
Anonymous
Ahojte, chcel by som sa uistit v jednej veci. Vsade citam, ze pri pumping lemme potrebujem preverit vsetky mozne rozklady. Na cviceni sme robili priklad, no zda sa mi, ze tam mame nejak malo rozkladov. Je vsak mozne, ze som na cviceni nieco prehliadol, kedze som tomu najprv velmi nerozumel. Priklad je takyto
{a^m b^n | m<n }
Rozkladam slovo
w = a^p b^(p+1)
Ja by som to rozlozil nasledovne
1.) x = a^j ; y = a^k; z = b^l => j >= 0; k > 0; l >= 0
2.) x = a^j; y = a^k; z=a^l b^m => j >= 0; k > 0; l >= 0; m >= 0
3.) x = ε; y = a^j; z = a^k b^l => j >= 0; k >= 0; l >= 0
4.) x = ε; y = a^k; z = b^l => k > 0; l >= 0
Alebo
{a^m b^n | m>n}
Rozkladam slovo
w = a^(p+1) b^p
1.) x = a^j; y = a^k; z= a^l b^m => j >= 0; k > 1; l > 0; m >= 0
2.) x = ε; y = a^j; z = a^k b^m => j > 0; k > 0; m >= 0
Pochopil som to spravne? Dakujem pekne.
