Hierarchia Chomsky’ego

1. Dowieść, że każdą gramatykę monotoniczną, czyli o regułach \(\alpha\to\beta\), gdzie \(|\beta|\geq|\alpha|\), można sprowadzić do postaci, w której każda reguła ma formę
   \(\alpha X\beta\to\alpha\gamma\beta\)

   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.

2. Dowieść, że języki kontekstowe, to dokładnie języki rozpoznawane przez niedeterministyczne automaty liniowo ograniczone.

   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).

3. Dowieść, że iloraz języka kontekstowego przez język regularny może nie być językiem obliczalnym.

   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.

4. Dowieść, że języki częściowo obliczalne są zamknięte na ilorazy przez języki częściowo obliczalne.

5. Które z czterech klas hierarchii Chomsky'ego są zamknięte na operacje \(\cup,\cap,-\) ?