Á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.
Két lehetőség van: az utolsó b párja az első szóbeli jel. Ekkor az általuk közrefogott szó is (1) és (2) tulajdonságú (meggondolni!!) és így az indukció miatt generálható S-ből. Az eredeti szó pedig úgy jön, hogy először az $S\ensuremath{\rightarrow} Sasb$ szabályt használjuk, majd az első S-et epszilonra irjuk a második S-ből meg generálunk.
(b) az utolsó b párja nem az első a. Ekkor mind az utolsó b és 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.E 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.