Pátá série sedmnáctého ročníku KSP

Vzorová řešení


17-5-1 Velkovezír (Zadání)


Došlá řešení se dala rozdělit na tři skupiny, a to na jednak na triviální kvadratická (k nim není co dodat, pomocí částečných součtů řady se zkusily všechny možné úseky a vybral se ten s nejlepším průměrem), na řešení se složitostí O(KN) (také se zkouší všechny možnosti, ale uvědomíme si, že mezi všemi posloupnostmi s maximálním průměrem existuje alespoň jedna, která má délku menší než 2K, viz druhé pozorování) a na lineární. Jak na to?

Začněme pozorováním: Pokud máme nějakou posloupnost s průměrem d a rozdělíme ji na dvě části, alespoň jedna z těchto částí musí mít stejný nebo větší průměr než původní posloupnost. Nechť má jedna část délku l1 a druhá l2. Kdyby toto tvrzení neplatilo (čili průměr první části d1<d a taktéž d2<d), byl by průměr celé posloupnosti:

l1·d1+l2·d2
l1+l2
<
l1·d+l2·d
l1+l2
=d

ostře menší než d, což není možné, protože d je její průměr. Navíc stejné pozorování se dá provést i pro opačnou nerovnost, že tedy průměr jedné z částí musí být menší nebo roven průměru celé posloupnosti.

Přimíchejme ještě toto pozorování: Označme φa… b průměr čísel s indexy ab a φmax největší průměr nějaké posloupnosti. Předpokládejme, že posloupnost s maximálním průměrem končí prvkem s indexem L>i+K a že průměr všech posloupností, které končí prvkem i, není maximální (matematik by řekl, že pro každé 1≤ j<i platí φj… imax). Potom posloupnost s maximálním průměrem začíná na čísle s indexem větším než i.

Danger!Rozepišme, jak dopadne průměr posloupnosti začínající prvkem j≤ i:

φj… L =
φj… i·(i-j+1) + φi+1… L·(L-i)
L-j+1
φj… i·(i-j+1) + φmax·(L-i)
L-j+1
<
<
φmax·(i-j+1) + φmax·(L-i)
L-j+1
= φmax.

Tedy žádné z čísel s indexem 1… i nemůže být obsaženo v posloupnosti s maximálním průměrem.

Dost už bylo přihazování pozorování, pojďme z nich nyní vařit algoritmus. Na začátku vezmeme prvních K prvků, které budou tvořit zpracovávanou podposloupnost. V každém kroku algoritmu posuneme pravý konec zpracovávané posloupnosti o jeden prvek doprava. Její levý konec už nemusíme posouvat zpátky doleva, můžeme ho nechat tam, kde je (a druhé pozorování nám říká, že nepřijdeme o žádnou posloupnost s maximálním průměrem). Levý konec tedy nemusíme posouvat doleva, ale může se nám stát, že ho budeme muset posouvat doprava, abychom zvětšili průměr zpracovávané posloupnosti. Jak, to vyřešíme za chvilku. Takto v tomto kroku najdeme posloupnost s největším průměrem, která má pevný pravý konec a vznikla zkracováním posloupnosti z minulého kroku. (Netvrdíme, že tato posloupnost má největší průměr ze všech, které končí tímto pravým okrajem, ale z druhého pozorování víme, že jsme nezapomněli na posloupnost s maximálním průměrem, a to nám stačí.) Když si z těchto posloupností (pro každý pravý okraj máme jednu) vybereme tu s největším průměrem, najdeme určitě posloupnost s maximálním průměrem.

Jak tedy přesně vypadá krok algoritmu? Na začátku L:=1 a P:=K, zpracovávaná posloupnost je prvních K prvků. V každém dalším kroku uděláme

  • P:=P+1
  • dokud existuje L'>L, že P-L'+1≥ K (nezkrátíme moc) a φL'...PL...P (zlepšíme průměr), pokládáme L:=L'. Navíc pokud použijeme naše první pozorování a trochu se zamyslíme, zjistíme, že podmínka φL'...PL...P (část posloupnosti má větší průměr) je stejná jako podmínka φL...L'-1L...P (druhá část posloupnosti má menší průměr). Pro nás bude druhá varianta lepší.

Zbývá tedy vyřešit, jak zjistit, když máme L a P, jestli existuje prvek L', aby průměr posloupnosti prvků L… L'-1 byl menší než průměr prvků L… P (φL...L'-1L...P). Použijeme k tomu datovou strukturu, která bude kombinací fronty a zásobníku (bude umět data přidávat na jeden konec a odebírat je z konců obou), říkejme jí frobník. Ve frobníku budeme mít uloženou informaci o tom, jak vypadají průměry posloupností mezi prvky L a P-K. Přesněji řečeno v něm budou uloženy průměry posloupností X0X1-1, X_1… X_2-1,… ,X_S-1… X_S-1 s tím, že X0=L (začínáme vždy v L) a XS=P-K+1 (končíme vždy v P-K). Navíc bude vždy platit, že průměr jedné posloupnosti je menší než průměry všech posloupností, které se nacházejí ve frobníku (a tedy i v původní posloupnosti) za ní, matematicky řečeno φXi-1… Xi-1Xi… Xi+1-1.

Data budeme ve frobníku udržovat následujícím způsobem. Na začátku v něm není nic, protože P-K=0. Pak vždy, když zvětšujeme P, přidáme na konec frobníku průměr jednoprvkové posloupnosti s prvkem na indexu P-K (když přidáváme prvek do zkoumané posloupnosti, přidáme do frobníku prvek, který ještě může být v posloupnosti končící prvkem P). To nám ale mohlo pokazit vlastnost zvětšujících se průměrů. Pokud se tak stalo (φXS-1… XS-1≥ φP-K… P-K=P-K), budeme slučovat dvě poslední posloupnosti ve frobníku do jedné, dokud nebude platit, že průměr poslední posloupnosti ve frobníku je větší než průměr posloupnosti předposlední, případně dokud nesloučíme všechny posloupnosti do jedné.

Když jsme tedy takto upravili frobník, můžeme zkusit najít hledané L', aby průměr prvků L… L'-1 byl menší než průměr prvků L… P = φL… P. Vezmeme první posloupnost z frobníku (je to posloupnost L… L'-1) a pokud má průměr menší než φL… P, je to naše hledaná posloupnost s menším průměrem, tedy položíme L=L', a tuto posloupnost z frobníku odebereme. Takto pokračujeme, dokud je průměr první posloupnost ve frobníku menší než φL… P nebo dokud frobník nevyprázdníme.

Nyní už víme, jak algoritmus pracuje, zbývá zjistit složitost. Program se skládá z N kroků, v každém zvětšujeme P, upravujeme L (frobník) a testujeme, zda je nalezená posloupnost lepší než dosud nalezená. Kromě úprav frobníku jsou všechny tyto operace konstantní, tedy časová složitost algoritmu bez úprav frobníku je lineární. Do frobníku vložíme nanejvýš N posloupností, každá se může nanejvýš jednou sloučit a jednou vyndat, takže všechny operace s frobníkem trvají dohromady také jenom lineárně dlouho. (V jednom kroku algoritmu sice můžeme ve frobníku najednou sloučit až O(N) posloupností, ale uvědomte si, že sloučit mohu jenom to, co jsem do frobníku dal, takže slučování je celkem nanejvýš N-K.) Tedy časová složitost celého algoritmu je lineární, paměťová taktéž.

Program

Pavel Čížek a Milan Straka


17-5-2 Ranní hroše (Zadání)


Při řešení každé úlohy je nejprve nutno pochopit zadání. To se mnohým řešitelům této úložky nepovedlo i přesto, že úloha byla zadána poměrně srozumitelně. Úkolem bylo zjistit, zda existuje nějaký interval h z množiny H a vV, že h začíná i končí dříve než v. Tedy jedná se o úlohu zjišťovací, na kterou stačilo odpovědět ano nebo ne. Vypsání hledané dvojice intervalů navíc samozřejmě není nijak na škodu, ale nebylo potřeba. Co však již vadí, je situace, ve které řešitel vypisuje všechny vyhovující dvojice intervalů, to vede na triviální kvadratický algoritmus. Takováto řešení nechť do budoucna odradí ne víc než dva body za funkčnost.

Tato úloha se dá optimálně pořešit rozličnými přístupy. Zkusme nejprve setřídit obě množiny dohromady podle počátků intervalů. Nyní procházejme po setříděné posloupnosti. Budeme si přitom pamatovat jeden interval z množiny H, říkejme mu kandidát, který má takovou vlastnost, že pokud existuje nějaká dvojice vyhovujících intervalů, pak existuje i vyhovující dvojice, ve které se nachází náš kandidát. Na počátku si poznačme, že kandidáta ještě nemáme. Pokud tedy při průchodu narazíme na interval z množiny H, pak ho porovnáme s kandidátem. V případě, že nově nalezený interval je „lepší“, označíme ho za nového kandidáta. Nově nalezený interval A je „lepší“ než interval B právě, když jeho konec je menší.

Nyní rozeberme případ, kdy narazíme na interval z množiny V. Pokud ještě nemáme kandidáta, znamená to, že neexistuje žádný interval z množiny H takový, který má menší začátek, tehdy jdeme v posloupnosti dále. Pokud však již máme nějakého kandidáta, pak jeho začátek je díky setříděnosti menší než začátek nově nalezeného intervalu. Stačí tedy porovnat konec kandidáta s koncem nového intervalu a v případě, že kandidát má konec intervalu menší, skončíme, protože jsme právě nalezli vyhovující dvojici.

Linearita průchodu po setřídění i jeho konečnost je zřejmá. Celková časová složitost algoritmu je tedy ovlivněna tříděním, které pro neceločíselné intervaly umíme při nejlepším v čase O(N log N), kde N budiž součet velikostí množin HV. Paměťová složitost je vůči stejnému N lineární.

Zbývá ukázat, že pokud řešení existuje, náš algoritmus ho najde. Ať tedy dvojice intervalů splňující zadání existuje, označme ji h a v, kde h je z H, vV, pak při průchodu posloupností narazíme na h dříve než na v. Tedy jistě dojde k porovnání h s kandidátem, v případě, že je kandidát „lepší“, pak dvojice kandidát a v také splňuje zadané podmínky. V případě, že kandidát není „lepší“, pak dojde k nahrazení kandidáta intervalem h. Tedy po průchodu přes h splňuje kandidát podmínky pro hledané intervaly. Zřejmě pokud v budoucnu se kandidát zlepší, stále bude kandidát splňovat podmínky. A konečně až narazíme při průchodu na v, porovnáme jej s kandidátem a program skončí.

Na závěr zmíním, že řešení, která měla po setřídění již jen lineární průchody, tedy taková, která by se v případě celočíselných intervalů dala napsat i se setříděním v lineárním čase, byla o maličko lépe ohodnocena než ostatní řešení.

Program

David Matoušek


17-5-3 Nouze V-Dáli-hrocha (Zadání)


Poslyšte příběh kratochvilný o tom, jak hrošík v nouzi poprosil o pomoc kmotřičku Rekurzi (ťuky ťuk!) a jak to dopadlo.

Maličký hrošík to asi ještě neví, ale to, co potřebuje, je vypsat všechny permutace množiny {1,… ,N} (čili všechna možná uspořádání těchto čísel) tak, aby se sousední permutace lišily prohozením právě jedné dvojice prvků (máte-li rádi cizí slovíčka, tak jednou transpozicí). A my vyřešíme rovnou těžší variantu úlohy, která po nás žádá, aby se jedinou transpozicí lišila i první a poslední permutace.

Jak na to? Všimněme si, že všechny permutace N prvků získáme z permutací N-1 prvků tak, že do každé původní permutace vložíme prvek N postupně na všechna možná místa. Čili pokud už víme, že pro N=2 existují permutace 12 a 21, pak pro N=3 můžeme z 12 získat 312, 132 a 123, zatímco z 21 získáme 321, 231 a 213. Když si uvědomíme, že míst, kam vložit nový prvek, je vždy N, dostaneme ihned vzoreček, který nám řekne, že permutací N prvků je p(N)=N·p(N-1), čili p(N)=N·(N-1)·(N-2)·… ·2 ·1 (obvykle značíme N!, tedy faktoriál z N).

Vyzbrojeni tímto pozorováním získáme ihned jednoduchý algoritmus, který nám všechny permutace vygeneruje. Pokud je N=1, vrátíme ihned jedinou permutaci, a to jedničku samu. Pokud je N>1, rekurzivním zavoláním našeho algoritmu vyřešíme úlohu pro N-1, čímž získáme nějaké permutace p1p(N-1)!. Nyní do nich budeme vkládat N-tý prvek, přičemž do p1 ho vložíme nejdříve na poslední pozici, pak na předposlední, atd. až na první, zatímco u p2 budeme postupovat popředu, u p3 opět pozpátku atd.

Nejlépe to asi bude vidět na příkladu:

Pro N=1: 1
Pro N=2: 12 21
Pro N=3: 123 132 312 321 231 213

Tak dosáhneme, že se sousední permutace liší jen jednou transpozicí: mezi dvěma sousedními permutacemi vzniklými z jedné pi se přesunulo pouze N na sousední pozici, zatímco mezi poslední vzniklou z pi a první z pi+1 zůstalo N na místě a změnily se pouze ostatní prvky, ovšem podle stejného algoritmu, takže také s jedinou transpozicí [ejhle, důkaz indukcí].

První vygenerovaná permutace bude určitě 12… N (každý prvek startuje vpravo). Jak ale bude vypadat ta poslední? Jelikož pro N>2 je (N-1)! sudé číslo, budeme v p(N-1)! posouvat N-kem zleva doprava, takže N skončí na poslední pozici. Indukcí nahlédneme, že tak dopadnou i všechny ostatní prvky až na jedničku a dvojku, které zůstanou prohozené. Proto poslední permutace bude 2134… N, přesně, jak potřebujeme.

Náš algoritmus má ale jeden velký háček: potřebuje z rekurze vracet celý vygenerovaný seznam permutací, takže má paměťovou složitost O(N·N!). To věru není dobré, ovšem můžeme to snadno napravit: připravíme si už na začátku celou počáteční permutaci 12… N a použijeme rekurzivní proceduru, která pro dané i proskáče aktuální permutaci prvkem i a mezi každými dvěma skoky zavolá sama sebe pro i+1. Jen si pro každý prvek potřebujeme pamatovat, jestli jsme jím naposledy skákali doleva nebo doprava, abychom správně střídali směry, a také se nám bude hodit udržovat si inverzi permutace, čili pole, které nám pro každý prvek řekne, kde se zrovna v permutaci nachází.

Všimněte si, že při proskakování i-čkem nás prvky větší než i nebudou rušit, protože jsou bezpečně uklizeny na jednom či druhém kraji permutace, takže opravdu stačí i-čkem posouvat na sousední pozici ve správném směru. Tím jsme vlastně mimoděk splnili mnohem víc, než po nás zadání chtělo: používáme jen transpozice sousedních prvků.

Zbývá rozebrat složitost: Naše rekurzivní procedura potřebuje jen konstantní čas na vymyšlení jedné permutace, leč na její vypsání je potřeba čas lineární. Proto pokud chceme vypisovat celé permutace, časová složitost nutně dosáhne O(N·N!) a lépe to ani nejde, protože je to čas lineární ve velikosti výstupu; kdyby nám stačilo vypsat posloupnost prohazování, zvládli bychom to v čase O(N!) a opět to lépe nemůže jít. Paměti spotřebováváme lineární množství (lineárně velká globální pole a konstantně na každou z N úrovní rekurze).

Danger!Pozorný čtenář si asi povšimne, že argument s velikostí výstupu na jednu nohu pokulhává, protože výstupem je přeci desítkový zápis permutace, ve kterém na každý prvek spotřebujeme řádově log N číslic, takže celý zápis musí měřit O(N log N) namísto O(N). To je i není pravda, tato potíž je totiž důsledkem toho, že jsme si nikdy paměťovou složitost (ani velikost vstupu a výstupu) nezavedli precizně. Dá se zavést dvěma způsoby: buďto můžeme počítat složitosti na chlup přesně a měřit velikost vstupu a výstupu i zabranou paměť v bitech (což „opravdová“ teorie složitosti skutečně dělá a zde ji vyjde log N), nebo si zvolíme jako základní jednotku jeden integer (rozumné velikosti, řekněme polynomiální v N, abychom předešli trikům a la naskládání celého vstupu do jediného integeru) a vše měříme v integerech. V KSP obvykle používáme ten druhý, výrazně jednodušší (i když někdy zbytečně hrubozrnný) přístup, a ten nám v tomto případě říká, že výstup je velký jenom O(N). Podobně je to s časovou složitostí: v druhém případě považujeme každou aritmetickou operaci za konstantně rychlou, v prvním její složitost závisí na počtu bitů čísel, se kterými operace počítá. Toto téma ještě nakousneme v úvodu k dalšímu ročníku KSP.

Program

Martin Mareš


17-5-4 Kudy tudy cestička (Zadání)


Začneme tím, že si určíme, v jakém pořadí po sobě následují zadané body na obvodu mnohoúhelníka (řekněme proti směru hodinových ručiček). Jeden ze způsobů jak to udělat je vybrat si nejlevější bod bod A a ostatní body setřídit sestupně podle úhlu, který svírá jejich spojnice s bodem A s osou x. Možná o něco jednodušší než si pro každý takový vektor počítat tento úhel, je pouze umět pro libovolné dva takové vektory rozhodnout, který z nich je má tento úhel větší. To poznáme podle znaménka jejich vektorového součinu: Pokud je tento součin kladný, leží druhý vektor v levé polorovině určené prvním vektorem, a tedy je úhel druhého vektoru větší. Povšimněte si, že pokud vektory porovnáváme tímto způsobem, můžeme si bod A vybrat libovolně, tj. nemusíme ani hledat nejlevější zadaný bod.

Nyní uvažme počáteční úsek P' libovolné nekřížící se cesty P, která projde všechny vrcholy. Vrcholy navštívené P' tvoří souvislý interval I na obvodu mnohoúhelníka (bráno cyklicky, tedy za N-tým vrcholem následuje první). Kdyby tomu tak nebylo a P' by nějaký vrchol w přeskočil, cesta P by se bez křížení nemohla dostat zároveň do w a do ostatních vrcholů. Z toho plyne, že poslední vrchol u úseku P' musí být jeden z krajních bodů intervalu I, a následující vrchol v cesty P je jeden z maximálně dvou vrcholů, které sousedí s krajními body I na obvodu mnohoúhelníka (samozřejmě u a v musí být také spojeny pěšinkou).

Nabízí se řešení zvolit si nějaký vrchol a poté procházet všechny cesty, které v něm začínají. Nicméně podle pozorování z předchozího odstavce může být možné každý počáteční úsek rozšířit dvěma způsoby, tedy všech takových cest může být řádově až 2N. To je příliš mnoho a přímočarý program založený na této myšlence by byl neúnosně pomalý.

Označme si ℓ(y,z) délku pěšinky mezi dvěma vrcholy y a z (tato hodnota je , pokud mezi vrcholy y a z pěšinka není). Procházet všechny cesty je beznadějné, ale všimli jsme si, že počáteční úsek libovolné nekřížící se cesty odpovídá nějakému intervalu. Intervalů není mnoho (jen řádově N2), zkusme toho využít. Je pro nás celkem nepodstatné, jak přesně cesta vypadá uvnitř intervalu, zajímá nás pouze její délka. Budeme si tedy pro každý interval mezi vrcholy s čísly u a v počítat délku nejkratší cesty, která pokryje interval u a v a navíc skončí v předepsaném vrcholu x (kde x je buď u nebo v). Označme si délku nejkratší takové cesty L(u,v,x). Nechť bez újmy na obecnosti x=v. Předposlední vrchol této cesty potom je buď u nebo v-1, a z těchto možností si chceme vybrat tu lepší. Takto dostáváme, že

L(u,v,v)=min(L(u,v - 1,u) + ℓ(u,v),
L(u,v-1,v-1) + ℓ(v-1,v)).

Z tohoto vztahu již snadno všechny hodnoty L(u,v,x) spočítáme – k jejich výpočtu potřebujeme znát hodnoty L pro kratší intervaly, uděláme si tedy tabulku, do níž budeme počítat tyto hodnoty postupně podle rostoucí délky intervalu. Ještě zmiňme, že pro intervaly délky 0 (tj. jednotlivé vrcholy) si nastavíme L(v,v,v)=0. Tato tabulka bude mít velikost 2N2 a každé její políčko spočítáme z předchozích hodnot v konstantním čase. Délku nejkratší cesty, která projde všechny vrcholy, pak dostaneme jako minimum z hodnot L(v,v-1,v) pro všechny vrcholy v.

Zbývá přijít na to, jak najít tuto cestu, ne jen její délku. Při výpočtu hodnoty L(u,v,x) si můžeme zapamatovat, který vrchol má být předposlední. Pak snadno cestu zkonstruujeme odzadu – začneme posledním vrcholem vN, k němu si najdeme předposlední vN-1, k tomu pak vN-2, atd., až dokud nedojdeme k prvnímu vrcholu.

Třídění vrcholů na obvodu mnohoúhelníka nám zabere čas O(N log N), délku cesty si určíme vyplněním tabulky v čase O(N2) a cestu samotnou nalezneme v čase O(N), výsledná časová složitost je tedy O(N2). Paměťová složitost je dána velikostí tabulek L a a je tedy O(N2). Povšimněte si, že pokud bychom chtěli znát pouze délku nejkratší cesty P a nepotřebovali bychom P vypsat, stačilo by nám pole L velikosti O(N) – počítali bychom si hodnoty L(u,v,x) podle vzrůstající délky k intervalu mezi vrcholy u a v a pamatovali bychom si pouze dva řádky tabulky – (k-1)-ní a k-tý.

Program

Zdeněk Dvořák


17-5-5 Jazykozpytec se loučí (Zadání)


Nebude zřejmě na škodu, když si ještě jednou pořádně rozmyslíme, co jsou to vlastně gramatiky. Gramatika je nástroj, který se používá pro přesný formální popis jistého jazyka. Abychom mohli o určité gramatice diskutovat, jaký jazyk vlastně popisuje, hodí se na chvíli na ni pohlížet jako na stroj, který postupně generuje slova podle přepisovacích pravidel. Takový výpočet je v principu nedeterministický, typicky totiž bývá na výběr několik pravidel, které se v daném okamžiku mohou použít. Některé větve výpočtu jsou slepé – pokud se v nich expandované slovo ocitne, nikdy z něj již nevymizí neterminální symboly a výpočet se nezastaví. Všechny možné větve výpočtu, které naopak úspěšně skončí odstraněním všech neterminálů, potom svým výsledným slovem tvoří jazyk gramatiky. Chceme-li sestrojit gramatiku popisující nějaký jazyk L, musíme jednak zajistit, aby se sadou přepisovacích pravidel bylo možno vytvořit všechna slova jazyka L, ale hlavně ukázat, že všechny ostatní větve výpočtu jsou slepé a gramatika tak netvoří slova nepatřící do L.

Úloha 1

První úloha je snadná, gramatiku pro jazyk {ai bj ck;  1≤ i≤ j≤ k} vytvoříme úpravou příkladu ze zadání. Nosná myšlenka bude následující: kromě původních pravidel z příkladu, které zajišťovaly namnožení stejného počtu symbolů a, b a c, dodáme ještě pravidlo na přimnožení libovolného množství symbolů b a c, od obou ovšem stejný počet, a konečně ještě jedno pravidlo pro přimnožení libovolného počtu samotných symbolů c. Zjevně tak bude v každém okamžiku platit 1≤ i≤ j≤ k, a každá platná kombinace počtů i,j,k bude naší gramatikou pokryta.

Tedy přesně, sestrojíme gramatiku G=(VN, VT, S, P), kde množina neterminálů bude VT={a,b,c}, množina neterminálů VN={S, B, C, X}, startovní symbol S a sada přepisovacích pravidel tato:

S→aSBC  |  abC
CB→BC      (CB→XB, XB→XC, XC→BC)
bB→bb
bC→bc  |  bbCC  |  bCC     …množíme bc a c
cC→cc

Abychom byli poctiví, bylo by ještě třeba si přesně zdůvodnit, že gramatika nevydá nepatřičná slova a nechtěné větve výpočtu tedy skončí jako slepé. Věříme však, že máte již dostatek zkušeností a znalostí, abyste si to po chvíli dívání na sadu pravidel bez problémů uvědomili sami.

Úloha 2

Druhá úloha se ukázala být pro některé řešitele oříškem, a občas tvrdili, že gramatiku popisující jazyk {a2n;  n∈N} nelze sestrojit, kupodivu i s „důkazem“. To samozřejmě není pravda, příslušná gramatika existuje a my si jednu takovou ukážeme.

V první fázi nejdříve vytvoříme jeden symbol A. V každé další fázi potom rozmnožíme všechny symboly a na dvojnásobný počet. Problém ovšem je, jak toho v rámci jedné fáze dosáhnout. Jediné pravidlo typu A→AA by zjevně násobným použitím produkovalo i jiné počty, než 2n.

Pomůžeme si speciálním neterminálním symbolem K, „kurzorem“, který bude běhat po slovu, vždy zleva doprava, přeskočí každé A a zdvojí ho při tom. Budeme při tom potřebovat poznačit si, kde aktuální slovo začíná a končí, obalíme si ho tedy na začátku symboly L a R, které se mohou změnit na A. Zbývá chytře navrhnout sadu přepisovacích pravidel P tak, aby gramatika nevydávala špatná slova.

S→a     …ošetři jednopísmenné slovo
S→LR     …obal slovo mezemi
L→A     …meze jsou v podstatě skryté A
R→A
L→LAK     …vytvoř vlevo nový kurzor
KA→AAK     …přeskoč A a zdvoj ho; podvádíme
KR→AR     …kurzor dorazil na konec, zruš ho
A→a     …a nahraď neterminály terminály

Všimněme si, že kurzorů může být v jednom okamžiku ve slově i více, ale protože zanikají až na konci slova, ničemu to nepřekáží a správně zdvojnásobí všechna A. Zdvojovací pravidlo není kontextové, ve skutečnosti tedy použijeme známý trik:

KA→XA
XA→XK
XK→AAK

Formálně bude naše gramatika G čtveřice (VN, VT, S, P), kde VN={S, A, L, R, K, X} a VT={a}.

Protože kurzor může zaniknout pouze až když dorazí úplně napravo, dojde tak ke správnému počtu zdvojnásobení všech symbolů A, gramatika tedy negeneruje nežádoucí slova. Naopak, pro slovo délky 2n stačí gramatice vytvořit n-1 kurzorů, které už se postarají o umocnění.

Tomáš Valla