Suche Home Einstellungen Anmelden Hilfe  

Q1  (3 points)

Gegeben sei eine berechenbare Funktion f: X->Y.
An der Stelle aX gilt f(a)=.

Erläutern Sie, was das bedeutet.
 

Q2  (5 points)
Ist folgende Funktion f: IN0->IN0 berechenbar?
 
1. Ja. 
2. Nein. 

Q3  (3 points)
Wann stoppt ein endlicher deterministischer Akzeptor seine Berechnung?
1. Sobald das leere Wort gelesen wird. 
2. Sobald das Eingabewort vollständig gelesen wurde. 
3. Nach einer vorher festgelegten Anzahl von Schritten. 
4. Sobald ein Endzustand erreicht wird. 
5. Durch einen äußeren Eingriff. 
6. Sobald ein festes Endezeichen von der Eingabe gelesen wird. 
7. Je nach Eingabesituation möglicherweise gar nicht, wenn er in eine Endlosschleife gelaufen ist. 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Q4  (10 points)
Sei X ein endliches Alphabet, aX und K, L, M seien Sprachen über X.
Welche der folgenden Aussagen sind wahr?
1. L+=M+ => L=M 
2. LL=L => L={
3. L*=L => L hat unendlich viele Elemente. 
4. (KL)M=KMLM 
5. L{a}=M{a} => L=M 
6. L*=M+ => L=M 
7. L*=M+ => LC
8. L*=M+ => MC
9. K(LM)=(KL)M 
10. (K*L*)*=(KL)*

Q5  (4 points)
Sei A=({a,b},{p,q,r,s},,p,{s}) eine endlicher Akzeptor mit (p,a)={q}, (p,b)={r}, (q,a)={s}, (q,b)={q,r}, (r,a)={s}, (r,b)=(s,a)=(s,b)=Ø.

Welche der folgenden Aussagen sind wahr?
1. A ist deterministisch. 
2. A ist nichtdeterministisch. 
3. Die von A erkannte Sprache L(A) ist
L(A)={w{a,b}* | die Anzahl der a's in w ist gerade und die Anzahl der b's in w ist ungerade}. 
4. Die von A erkannte Sprache L(A) wird durch folgenden regulären Ausdruck beschrieben:
(ab**b)b)a(ba)*

Q6  (6 points)
Gegeben seien zwei Mengen A und B.
Es ist zu beweisen, daß A=B gilt.
Erläutern Sie kurz, wie Sie im Beweis vorgehen.
 
 
 
 
 
 
 

Q7  (1 point)
Jede unendliche Sprache enthält das leere Wort.
1. Das ist richtig. 
2. Das ist falsch. 

Q8  (3 points)
Sei L={}.
Welche der folgenden Aussagen sind wahr?
1. L*={}. 
2. L*={}*
3. L={}*
4. L+={}. 
5. L+={}+
6. L={}+

Q9  (2 points)
Sei X ein beliebiges endliches Alphabet.
Dann ist jede Teilmenge der Menge X* eine reguläre Sprache.
1. Das ist richtig. 
2. Das ist falsch. 

Q10  (3 points)Sei X={a,bbb}.
Welche der folgenden Wörter liegen in X*?
1. aaaa 
2. aabbbaa 
3. aaaaaa... (unendl. langes Wort bestehend aus a's) 
4. das leere Wort 
5. babab 
6. bbb 

 

Benutzer: Gast • Besitzer: mthomas • Zuletzt geändert am: