Megszámlálhatóan végtelen sok generatív nyelv van egy adott véges ábécé felett Ezt fogjuk belátni. 1. Van legalább ennyi generatív nyelv, hiszen az egy szóból álló nyelvek mind generatívak (triviális módon), ezekbõl viszont megszámlálhatóan végtelen sok van. 2. Megmutatjuk, hogy nincsen több, mint megszámlálhatóan végtelen sok generatív nyelv. Ezt úgy tesszük, hogy felsoroljuk a generatív nyelveket nyelvtanaik szerint. Ha egy nyelv generatív, akkor van hozzá egy nyelvtan. Ezt a nyelvtant alakítsuk át úgy, hogy ha k darab nemterminális van benne, akkor azokat nevezzük $N_1,\cdots,N_k$-nak. Ezek után soroljuk fel az nyelvtanokat úgy, hogy elõször felsoroljuk valamilyen sorrendben azon nyelvtanokat, melyek leírása 1 hosszúságú, majd azokat, melyek hossza 2, aztán 3, 4, 5, stb. A nyelvtan hosszúsága a szabályok leírásához szükséges karakterek száma, például az $N_1\ensuremath{\rightarrow} aN_1b\;\vert\;ab$ nyelvtan hossza 8. (Nem kell megadni, hogy ki terminális és ki nem az, mert a terminális ábécé adott és azt sem kell megadni, hogy ki az S, mert az az S, aki elöl áll.) Világos, hogy egy adott l hosszúságra csak véges sok nyelvtan van, melynek hossza l (hiszen csak véges sok karakter fordulhat elõ: a terminálisok, max. l darab nemterminális meg még pár jel), ezért a fenti felsorolás lehetséges. Így minden generatív nyelvet felsorolunk legalább egyszer (persze, lehet, hogy többször is, ha több nyelvtan is elõállítja), vagyis legfeljebb csak megszámlálható sok ilyen nyelv van. Tehát készen vagyunk