Ask Your Question
1

Pumping lemma - rozklad

asked 2014-12-07 11:48:14 +0100

anonymous user

Anonymous

updated 2014-12-09 20:44:02 +0100

anonymous user

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.

edit retag flag offensive close delete

1 Answer

Sort by » oldest newest most voted
3

answered 2014-12-07 11:59:10 +0100

Viktor Chlumský gravatar image

Jestli si chcete přidat práci tak můžete, ale řek bych, že jedna skupina rozložení, které vám ukazovali na cvičení stačí, a to v tomhle případě 2. případ, protože:

  • případ 1 spadá do 2 s tím že l = 0
  • případ 3 spadá do 2 pokud j = 0
  • případ 4 spadá do 2 pokud j = l = 0

Nezapomeňte, že rozkládáte konkrétní slovo (které tu nějak nevidim), a pokud si tam vytváříte proměnný (j, k, l, m), chtělo by to taky napsat jaké mohou mít hodnoty.

edit flag offensive delete publish link more

Comments

Aha, jasne, cize pridam tam ake hodnoty to moze nadobudnut a tym to je vyriesene. To slovo som zabudol napisat. Fajn, dakujem velmi pekne :)

gandalf ( 2014-12-07 12:03:04 +0100 )edit

Mimochodom este k tym hodnotam premennych, napr pripad 1 prveho prikladu, je z = b^l , moze byt to l aj rovne 0, teda, ze tam nebudu ziadne becka? Alebo musi byt ostro vacsie? Dopisal som tam aj tie podmienky pre premenne. edit: Nie, mam to zle zrejme, to becko tam asi bude musiet byt, podla slova ktore rozkladam.

gandalf ( 2014-12-07 12:06:47 +0100 )edit

No hlavně by to chtělo podmínky pro vztahy těch proměnných s p. V tomhle případě musí vždy platit, že l = p+1.

Viktor Chlumský ( 2014-12-07 14:13:09 +0100 )edit

jo jasne, super dik este raz :)

gandalf ( 2014-12-07 14:18:33 +0100 )edit

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2014-12-07 11:48:14 +0100

Seen: 155 times

Last updated: Dec 07 '14