Állítás: $S\ensuremath{\rightarrow} SaSb\;\vert\;\epsilon$ nyelvtan azt a nyelvet generálja, amiben: (1) a nyelv szavainak minden kezdõszeletében legalább annyi a van, mint b (2) a szó egészében pedig az a-k és a b-k száma megegyezik Bizonyítás Amit a nyelvtan generál, az ilyen, mert a-kat és b-ket mindig párosával generál és egy b generáláskor mindig tesz elé a-t is. Minden helyeset elõ lehet ezzel állítani. Ezt az a-k (vagy ami ugyanaz: a b-k) számára (n) menõ teljes indukcióval bizonyítjuk. Ha n=0, akkor a szó az $\epsilon$, amit a nyelvtan tényleg generál. Tegyük fel, hogy vmi n-re már megvan az állítás. Ekkor egy n+1 a-t tartalmazó (1) és (2) tulajdonságú szó esetén a következõt tegyük: Az utolsó jelhez, mely szükségképpen b, keressük meg a párját, azaz azt az a-t amelyre hátulról haladva elõször teljesül, hogy hátulról odáig a szóban ugyanannyi a van mint b. (Azaz az addigi részszavakban több b volt, mint a, mivel hátulról nézve az teljesül a nyelvbeli szavakra, hogy a b-k száma legalább annyi, mint az a-k száma.) Ezt az a-t nevezzük a b párjának. Ekkor mind az utolsó b és a párja által bezárólag határolt szóra, mind az utolsó b párja elõtt keletkezõ szóra teljesül (1) és (2) (meggondolni!!), így az indukció miatt generálhatók S-bõl. Tehát az eredeti szó is generálható, elõbb egy $S\ensuremath{\rightarrow} Sasb$-t használunk, utána meg a fenti két levezetést. Az is igaz, hogy a nyelvtan egyértelmû. Ugyanis ha az utolsó b párjának nem a fenti módon kijelölt a-t választjuk, vagyis azt próbáljuk erõltetni, hogy az utolsó b nem azzal az a-val együtt kerül be a leveztési fába, akkor vagy a választott a elõtt vagy az a és a b között keletkezõ szó nem lesz levezethetõ S-bõl (meggondolni!!), de akkor az egész szó sem lesz.