Teil 1

Man weiß, dass

´L = {a^(r_1), a^(r_2), …, a^(r_n)} uu {a^p}^** {a^(s_1), a^(s_2), …, a^(s_m)}´

für gewisse ´0 <= r_1 < r_2 < … < r_n < s_1 < s_2 < … < s_m´ gilt. Diese Menge wird von der Grammatik

´({S,S'}, {a}, {S -> a^(r_i) | 1 <= i <= n} uu {S -> a^(s_j) S' | 1 <= j <= m} uu {S' -> a^pS', S' -> lambda}, S)´

mit zwei Nichtterminalen erzeugt. Somit gilt ´n(L) <= 2´.

Teil 2

Als ´L_1´ nimmt man die Menge ´{a}´, die von ´({S}, {a}, {S -> a}, S)´ erzeugt wird. Da ohne Nichtterminal nur die leere Menge erzeugt wird, muss für ´L_1´ mindestens ein Nichtterminal verwendet werden. Beide Aussagen zusammen ergeben ´n(L_1) = 1´.

Man betrachtet ´L_2 = {a} uu {a^5}^** {a^2} = {a, a^7, a^12, a^17, …}´. Diese Sprache wird nach 1. von einer Grammatik mit ´2´ Nichtterminalen erzeugt. Damit gilt ´n(L_2) <= 2´. Da ´L_2 != O/´, muss mindestens ein Nichtterminal benutzt werden. Angenommen, es gilt ´L_2 = L(G)´ für eine Grammatik ´G = ({S}, {a}, P, S)´ mit nur einem Nichtterminal ´S´.

Falls es eine Satzform mit mindestens zwei Vorkommen von ´S´ gibt, so gelten (da nur ´a´s erzeugt werden, können wir die Reihenfolge der Buchstaben vertauschen, ohne die Sprache zu ändern, weshalb nachfolgende Ableitungen allgemein sind):

´S =>^** wSS =>^** a^xSS =>^** a^xaS =>^** a^xaa´ ´S =>^** wSS =>^** a^xSS =>^** a^xaS =>^** a^xaa^7´

wobei ´w =>^** a^x´ eine terminierende Ableitung aus ´w´ ist und wegen ´a´, ´a^7 in L_2´ die Ableitungen ´S =>^** a´ und ´S =>^** a^7´ existieren. Damit haben wir

´x + 2 = 5 * n + 2´ und ´x + 8 = 5 * m + 2´

Durch Umstellung nach ´x´ und Gleichsetzung erhalten wir ´5n = 5m − 6´, was unmöglich ist. Damit haben alle Satzformen höchstens ein ´S´ und alle Regeln sind regulär (´S -> a^xS´ oder ´S -> a^y´ wegen der Vertauschbarkeit der Reihenfolge). Damit gilt:

´P = {S -> a^(x_1)S, …, S -> a^(x_n)S, S -> a^(y_1), …, S -> a^(y_m)}´

mit gewissen ´1 <= x_1 < x_2 < … < x_n´ und ´0 <= y_1 < y_2 < … < y_m´. Wegen der Unendlichkeit von ´L_2´ und dem Fakt, dass terminiert werden muss, gilt ´n >= 1´ und ´m >= 1´. Damit liegen ´a^(r * x_1 + y_1)´ für ´r >= 1´ in ´L_2´.

Wegen ´2x_1 + y_1 = 5_n + 2´ und ´3x_1 + y_1 = 5_m + 2´ folgt ´x_1 = 5(m−n) >= 1´. Da aber ´a in L_2´ ist, muss es die Regel ´S -> a´ geben. Also gibt es die Ableitung

´S => a^(x_1) S = a^(5(m−n)) S => a^(5(m−n)) a = a^(5(m−n)+1)´

Dies ist aber unmöglich, da Wörter aus ´L_2´ mit mindestens zwei Buchstaben die Form ´a^(5k + 2)´ haben.