gdzie \(X\in V\), \(\alpha,\beta,\gamma\in(\Sigma\cup V)^{*}\), \(\gamma\neq\varepsilon\) (\(V\) – zbiór symboli nieterminalnych, \(\Sigma\) – zbiór symboli terminalnych).
Uwaga. Przy powyższym sprowadzeniu trzeba na ogół powiększyć zbiór symboli nieterminalnych.
Uwaga. Automaty liniowo ograniczone są określone podobnie jak maszyny Turinga, z tym, że jedyną dostępną pamięcią są komórki taśmy zajęte na początku przez słowo wejściowe (przy czym koniec słowa jest zaznaczony specjalnym markerem).
Wskazówka. Wykorzystać język obliczeń maszyny Turinga, która akceptuje język nieobliczalny.
Wywnioskować dalej, że ani języki kontekstowe, ani języki obliczalne nie są zamknięte na ilorazy przez języki regularne.
Które z czterech klas hierarchii Chomsky'ego są zamknięte na operacje \(\cup,\cap,-\) ?