Postupovať budeme analogicky ako v prípade dôkazu neregularity jazyka, teda dôkazom sporom

1. Prvým krokom dôkazu je predpoklad, že tento jazyk je bezkontextvý a platí preň pumpovacia lema.

2. Predpokladáme, že existuje také číslo $p$ (pumpovacia konštanta), že slová s dĺžkou aspoň $p$ možno rozdeliť na základe vyššie prezentovaného princípu na peť časti $u,v,x,y,z$.

3. Určime slovo $w$, pre ktoré platí $|w|\geq p.$ Takýmto slovom je napíklad slovo $a^pb^pc^p$, keďže $$|w|=|a^pb^pc^p|=|a^p|+|b^p|+|c^p|=p+p+p=\underline{\underline{3p\geq p}}.$$

4. Teraz vykonáme tzv. analýzu prípadov, v rámci ktorej preskúmame všetky možné dekompozície tohto slova. Zameriame sa pritom na časti, ktoré možno napumpovať. Keďže $|vxy|\leq p$ je zrejmé, že pri dekompozícii môžu nastať len nasledujúce štyri prípady:

• $vxy$ je tvorené len symbolmi $a$
  Z 2. bodu PL je zrejmé, že $vy$ obsahuje aspoň jeden symbol $a$. Pri napumnovaní týchto častí sa preto počet symbolov $a$ v slove navýši, zatiaľ čo počet symbolov $b$ a $c$ zostane nezmení, keďže sú súčasťou $z$. Takéto slovo však nepatrí jazyku $L$, čo predstavuje SPOR s tretím bodom PL.
• $vxy$ je tvorené len symbolmi $b$; $vxy$ je tvorené len symbolmi $c$
  Tieto prípady dekompozície vedu takiež k SPORU s tretím bodom PL, a to analogicky, ako predchádzajúci prípad.
• $vxy$ je tvorené len symbolmi $a$, $b$
  V tomto prípade možno napumpovaním častí $v$, $y$ dosiahnuť zvýšenie počtu symbolov $a$ alebo symbolov $b$ alebo oboch symbolov $a$ aj $b$, zatiaľ čo počet symbolov $c$ zostane nezmení. Takéto slovo však nepatrí jazyku $L$, čo predstavuje SPOR s tretím bodom PL.
• $vxy$ je tvorené len symbolmi $b$. $c$
  Tento prípad dekompozície vedie takiež k SPORU s tretím bodom PL, a to analogicky, ako predchádzajúci prípad.

Záver: Kedže v každom prípade sme dospeli k sporu, možno konštatovať, že jazyk $L$ nie je bezkontextový Q.E.D.

1. Zavedenie pravidla pre prázdny reťazec: V prvom kroku vytvoríme pravidlo pre generovanie prázdneho reťazca, keďže to sa podľa definície kontextovej gramatiky, môže udiať len priamou deriváciou z jej začiatočného symbolu S. Neterminálny symbol S' následne slúži na generovanie neprázdnych reťazcov tohto jazyka.

2. Generovanie vetných foriem tvaru aB(AB)${}^i$c${}^i$c, kde $i\in\mathbb{N}_0$: Keďže všetky ostatné reťazce musia začínať (aspoň jedným) terminálnym symbolom a a končiť (aspoň jedným) terminálnym symbolom c do gramatiky zavedieme pravidlo:

Je zrejmé, že ak následne prepíšeme neterminálny symbol B na terminálny symbol b získame najkratšie neprázdne slovo jazyka abc. Teraz však potrebujeme špecifikovať spôsob, ako rovnomerne navyšovať počet výskytov symbolov a, b a c, aby sme dokázali generovať všetky slová jazyka $L$. To dosiahneme zavedením ďalších pravidiel, ktoré opakovane vkladajú nové inštancie neterminálnych symbolov A, B medzi existujúce a a c, čím vytvárajú základ pre ich neskorší prepis na terminálne symboly.

3. Zoskupenie terminálnych symbolov A a B: Vyššie uvedený systém pravidiel je schopny generovať vetné formy tvaru: aBc, aBABcc, aBABABccc$\ldots$ Ako je pritom možné pozorovať tieto vetné formy zachovávajú rovnakú početnosť symbolov c, B, z ktorých neskôr vzniknú symboly b a taktiež početnosť symbolov a a A, z ktorých neskôr vzniknú symboly a. Problém však predstavuje striedanie neterminálnych symbolov A a B, ktorý však možno jednoducho vyriešiť skôr spomínaným pravidlom zámeny, tvaru:

4. Finálny prepis neterminálnych symbolov A,B na terminálne symboly a,b: Posledným krokom je už zoskupené, teda správne usporiadané neterminálne symboly A a B prepísať na terminálne symboly a a b. Nemožno to však vykonať jednoducho prostredníctvom pravidiel A$\to$a, B$\to$b, keďže tie by sa mohli alipkovať ešte pred usporiadaním týchto neterminálnych symbolov, čo by viedlo k možnosti generovať taktiež slová, ktoré nepatria jazyku $L$. (Majú rovnaké počty terminálnych symbolov a,b,c a však symboly a nie sú zoskupené na začiatku a sú prekladané symbolmi b.)

Otázkou je tak za akých okolností (v akom kontexte) vieme prepísať neterminálne symboly A, B na terminálne symboly a,b. Odpoveďou je, keď sú už správne usporiadané, čo v prípade neterminálnych symbolov B predstavuje dva možné prípady, ak tento symbol stojí bezprostredne pred terminálnym symbolom c alebo b a v prípade neterminálnych symbolov A, ak tento symbol stojí bezprostredne za terminálnym symbolom a. Všetky tieto prípady sú vyjadrené prostredníctvom nasledujúcich pravidiel gramatiky:

Výsledkom je teda kontextová gramatika $G=(\{$S, S', X, A, B$\},\{$a, b, c$\},P,$S$)$, kde $P$ je množina pozostávajúca z nasledujúcich pravidiel:

Jazyk všetkých reťazcov, ktoré pozostávajú z dvoch za sebou idúcich identických podreťazcov, nie je kontextový. Dôvodom je, že nie je možné pomocou kontextovej gramatiky (ani zásobníkového automatu) zabezpečiť rovnosť dvoch ľubovoľne dlhých reťazcov bez toho, aby sme mali možnosť uchovávať arbitrárne veľké množstvo informácie o prvom z nich. Formálne sa dá dokázať, že tento jazyk nie je bezkontextový (ani kontextový), no v tomto príklade ukážeme, ako ho možno generovať pomocou frázovej gramatiky.

Základnou myšlienkou je najprv vygenerovať vetnú formu tvaru $w$T$w^R$# a následne preklopiť časť $w^R$ cez # späť do pôvodného poradia, čím vznikne reťazec $ww$. V rámci tohto mechanizmu využijeme pomocný neterminálny symbol C ("prenášač"), ktorý zabezpečuje postupný presun terminálnych symbolov (z časti $w^R$) za špeciálny oddeľovací symbol # predstavujúci hranicu medzi novými časťami reťazca.

1. Generovanie reťazca $w$T$w^R$#: touto časťou gramtiky možno dovodiť vetné formy tvaru: T#, aTa#, bTb#, abTba#$\ldots$

2. Preklopenie $w^R$ za oddeľovací symbol # pomocou "prenášača" C: po tom, čo máme vygenerovanú vetnú formu $w$T$w^R$#, potrebujeme pomocou pravidiel postupne presunúť jednotlivé symboly zo začiatku $w^R$ doprava za pomocný oddeľovací symbol #, čím sa obrátený reťazec $w^R$ preklopí do správneho poradia. Prenos symbolov realizujeme pomocou "prenášača" C, ktorý symbol "uchopí" a pomocou výmen s nasledujúcimi symbolmi sa spolu s týmto symbolom posúva doprava. Keď sa nosič dostane pred symbol #, výmenou ho dostane za pomocný oddeľovací symbol #. Celý tento proces je vyjadrený prostredníctvom nasledujúcich pravidiel gramatiky:

3. Odstánenie pomocných neterminálnych symbolov T a #: Opakovaním predchádzajúceho kroku sa všetky symboly zo segmentu $w^R$ presunú za oddeľovací symbol # v správnom poradí, čím vznikne vetná forma tvaru $w$T#$w$. Následne je už len potrebné odstrániť pomocné neterminálne symboly T a # stojace vedľa seba prostredníctvom nasledujúceho pravidla:

Výsledkom je teda frázová gramatika $G=(\{$S, S', T, C, #$\},\{$a, b$\},P,$S$)$, kde $P$ je množina pozostávajúca z nasledujúcich pravidiel:

V prvom kroku tohto cvičenia sme dokázali, že jazyk $L$ nie je bezkontextový, preto neexistuje ZA, ktorý by ho akceptoval. Keďže v druhom kroku sme konštruovali jeho kontextovú gramatiku je zrejmé, že preň musí existovať akceptor v podobe lineárne ohraničeného TS, ktorého cieľom je overiť, či vstupný reťazec obsahuje rovnaký počet symbolov $a$, $b$ a $c$, ktoré sú navyše zoradené striktne v tomto poradí. Uveďme teda princíp fungovania TS akceptujúceho jazyk $L$.

TS bude opakovane vyhľadávať prvý neoznačený symbol $a$, ktorý následne označí ako $X$. Potom preskočí všetky už označené symboly $b$, aby našiel prvý neoznačený symbol $b$, ktorý označí ako $X$. Následne analogickým spôsobom vyhľadá zodpovedajúci symbol $c$, pričom preskočí všetky predchádzajúce značky $X$, a označí ho ako $X$. Každý úspešne vykonaný trojstupňový krok (označenie $a\to X$, $b\to X$, $c\to X$) zodpovedá jednej trojici symbolov $a_{i}$, $b_{i}$, $c_{i}$.

Výsledný automat má tak tvar $M=(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\{a,b,X,\Box\},\delta,q_0,\Box,\{q_4\})$, kde prechodová funkcia $\delta$ je určená nasledujúcim diagramom.

Keďže princíp fungovania tohto TS je pomerne zložitý rozdelíme ho do štyroch fáz:

1. Prepis vstupu na označené symboly: Turingov stroj najprv postupne prepisuje vstupné slovo na ekvivalentné slovo tvorené označenými symbolmi: každý symbol $a$ nahradí symbolom $X$ a každý symbol $b$ symbolom $Y$. Symboly $X$ a $Y$ teda predstavujú označené varianty pôvodných znakov. Tento prepis sa vykonáva striedavo – najprv z ľavého a potom z pravého konca neoznačenej časti vstupného slova, čím sa zabezpečí, že stroj skončí v strede slova. (Zodpovedajúce stavy: $q_0$ až $q_3$)

2. Obnovenie ľavej polovice slova: Po označení všetkých symbolov vstupného slova stroj prepíše ľavú polovicu slova naspäť na pôvodné symboly ($X$ na $a$ a $Y$ na $b$). Tým sa obnoví prvá polovica pôvodného slova. Tento krok končí na vstupného slova. (Zodpovedajúci stav: $q_4$)

3. Porovnávanie prvej a druhej polovoce slova: V ďalšej fáze stroj iteratívne označuje symboly prvej polovice, pričom ich porovnáva s príslušnými symbolmi druhej polovice:

• najprv označí symbol z prvej polovice,
• potom preskočí všetky neoznačené symboly a symboly $\Box$ až kým nenarazí na zodpovedajúci označený symbol,
• ak sa symboly zhodujú, prepíše symbol z druhej polovice na $\Box$ a vráti sa späť k ďalšiemu neoznačenému symbolu prvej polovice.

(Zodpovedajúce stavy: $q_5$ až $q_8$)

4. Akceptácia slova: Po ukončení predchádzajúcej fázy je druhá polovica slova prepísaná na symboly $\Box$. Stroj následne prejde na začiatok prvej polovice slova (ktorá je v označenej forme) a zmení svoj stav na akceptujúci. (Zodpovedajúce stavy: $q_9$ a $q_{10}$)

Výsledný automat má tak tvar $M=(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9,q_{10}\},\{a,b\},\{a,b,X,Y,\Box\},$ $\delta,q_0,\Box,\{q_{10}\})$, kde prechodová funkcia $\delta$ je určená nasledujúcim diagramom.