Chomského hierarchie: Porovnání verzí

Poznámka: Lidé často z faktu, že například třída regulárních jazyků je „menší“ než třída bezkontextových jazyků, vyvozují, že totéž platí i pro jazyky, tedy že regulární jazyky jsou „menší“ než bezkontextové jazyky. Tato představa je mylná; největší jazyk nad libovolnou abecedou (množina všech řetězců nad touto abecedou) je regulární jazyk, čili patří do „nejmenší“ z uvedených tříd. Lepší je představa, že zatímco regulární jazyky „vysekávají“ z množiny všech řetězců jazyky dosti hrubě, bezkontextové jazyky jemněji, kontextové ještě jemněji, atd. Například ve snaze přiblížit se kontextovému jazyku <math>L = \{ a^{n}b^{n}c^{n}; n \in N \}</math> lze sestrojit regulární jazyk, kde počet symbolů <math>a</math>, <math>b</math>, <math>c</math> je stejný pouze do 1000 symbolů, tj. jazyk <math>L_{R} = \{ a^{n}b^{n}c^{n} | n \le 1000 \andland n \in N \} \cup \{ a^{i}b^{j}c^{k} | i > 1000 \andland j > 1000 \andland k > 1000 \}</math> a bezkontextový jazyk, který obsahuje pouze ta slova z <math> L_{R} </math>, která obsahují stejně symbolů <math>a</math> jako <math>b</math>, <math>a</math> jako <math>c</math> nebo <math>b</math> jako <math>c</math>.