Wir betrachten zuerst beliebige, monotone oder kontextfreie Grammatiken. Wir wissen, dass in diesen drei Fällen das Äquivalenzproblem unentscheidbar ist. Da aber ´L(G_1) = L(G_2)´ genau dann gilt, wenn sowohl ´L(G_1) sube L(G_2)´ als auch ´L(G_2) sube L(G_1)´ gelten, ergibt sich sofort aus der Entscheidbarkeit des Inklusionsproblems auch die Entscheidbarkeit des Äquivalenzproblems, die nicht gegeben ist. Daher ist das Inklusionsproblem für beliebige, monotone und kontextfreie Grammatiken unentscheidbar. Im Fall der regulären Sprachen ergibt sich wie folgt Entscheidbarkeit: Die Beziehung ´L(G_1) sube L(G_2)´ gilt genau dann, wenn ´L(G_1) setminus L(G_2) = O/´ gilt. Nun gilt

´L(G_1) setminus L(G_2) = L(G_1) nn C(L(G_2))´

Nun kann zuerst zu ´G_2´ ein deterministischer endlicher Automat ´A_2´ mit ´L(G_2) = T(A2)´, aus ´A_2´ ein deterministischer endlicher Automat ´A_2^'´ mit ´T(A_2^') = C(T(A_2)) = C(L(G_2))´, aus ´A_2^'´ eine reguläre Grammatik ´G_2^'´ mit ´L(G_2) = T(A_2^') = C(L(G_2))´, und aus ´G_1´ und ´G_2^'´ eine reguläre Grammatik ´G_3´ mit ´L(G_3) = L(G_1) nn L(G_2^') = L(G_1) nn C(L(G_2))´ bestimmt werden. Daher ist ´L(G_1)´ genau dann eine Teilmenge von ´L(G_2)´, wenn ´L(G_3)´ leer ist. Da das Leerheitsproblem für reguläre Sprachen entscheidbar ist, ist auch ´L(G_1) sube L(G_2)´ entscheidbar.