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