Theoretische Informatik

Erste Frage Aufrufe: 111     Aktiv: 05.10.2021 um 12:15

0

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 ?

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
0 Antworten