hey ich befinde mich gerade in der Klausurvorbereitung für Theoretische Informatik und habe noch ein paar Fragen. Wäre super dankbar, falls jemand iwas beantworten könnte:
1)Es soll gezeigt werden, dass folgende Sprache nicht regulär ist: Lk ={c^r a^n b^n |1≤r≤k,n∈N+} mit beliebigem k. ist der Ansatz soweit richtig mit dem Pumming Lemma "ca" aufzupumpen, damit dann folglich a und b nicht mehr in gleicher Anzahl vorkommen ?
2) ist die folgende Menge entscheidbar oder unentscheidbar ? : Ak ={(i,j) ∈ N×N |i ≤ k und M_i (j)hält} Meine Vermutung ist nein, da es ja sehr ähnlich zum unentscheidbaren allgemeinen Halteproblem aussieht ?
Punkte: 10
Markdown wird unterstützt.