Q2  (3 points)
Gegeben sei ein endlicher nichtdeterministischer Akzeptor, der die Sprache L akzeptiert.
Kann es vorkommen, daß ein äquivalenter deterministischer Akzeptor weniger Zustände besitzt als der nichtdeterministische?

	1.	ja.
	2.	nein.

Q3  (6 points)
Gegeben sei ein nichtdeterministischer endlicher Akzeptor mit n Zuständen.
Wieviele Zustände hat ein äquivalenter deterministischer endlicher Akzeptor höchstens?
Bitte begründen Sie Ihre Antwort.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Q4  (3 points)
Gegeben sei ein nichtdeterministischer endlicher Akzeptor?
Der Akzeptor befinde sich momentan im Zustand s, das nächste Zeichen auf dem Eingabeband sei x, und es gelte für die Zustandsübergangsfunktion (s,x)={s₁,s₂,s₃}.

Welche der folgenden Aussagen beschreiben das Verhalten des Akzeptors korrekt?

	1.	Der Akzeptor wählt willkürlich einen der drei Folgezustände s1,s2,s3 aus und nimmt diesen Zustand an. Zugleich wird das Zeichen x gelesen.
	2.	Der Akzeptor wählt zufällig einen der drei Folgezustände s1,s2,s3 - jeweils mit Wahrscheinlichkeit 1/3 - aus und nimmt diesen Zustand an. Zugleich wird das Zeichen x gelesen.
	3.	Eine solche Situation ist lt. Definition von nichtdeterministischen Akzeptoren gar nicht zugelassen.
	4.	Der Akzeptor wählt den kleinsten der drei Folgezustände s1,s2,s3 bezgl. einer vorgegebenen Numerierung aus und nimmt diesen Zustand an. Zugleich wird das Zeichen x gelesen.
	5.	Der Akzeptor wählt den Folgezustand aus s1,s2,s3 so aus, daß er schließlich einen Endzustand erreicht, sofern das Eingabewort in der akzeptierten Sprache liegt. Zugleich wird das Zeichen x gelesen.
	6.	Der Akzeptor merkt sich den Folgezustand aus s1, s2 oder s3, den er beim letzten Mal gewählt hat, als er im Zustand s war. Nun wählt er als Folgezustand s(i+1) mod 3. Zugleich wird das Zeichen x gelesen.

Q5  (2 points)
Kann die Sprache {0,1}^*{00}{0,1}^* durch eine rechtslineare Grammatik erzeugt werden?

	1.	Ja.
	2.	Nein.

 
 
 
 
 
 
 

Q6  (4 points)
Sei G = ( N, T, P, S ) eine Grammatik, wobei
N = { S, A, B }, T = { 0, 1 },
P = { S -> 0B, A -> A10, A -> , B -> A10 }.

Welche der folgenden Aussagen sind zutreffend?

	1.	G ist rechtslinear.
	2.	G ist linkslinear.
	3.	G ist weder links- noch rechtslinear.
	4.	L(G) ist regulär.
	5.	L(G) ist nicht regulär.

Q7  (2 points)
Sei X ein endliches Alphabet.
Geben Sie die (bezüglich Inklusion) kleinste und die größte reguläre Sprache über X an.

Answer:
1.
2.

Q8  (4 points)
Nennen Sie verschiedene Beschreibungsmöglichkeiten, um eine reguläre Sprache zu definieren.

Answer:

Q9  (4 points)
Ist die Sprache { w | w  {a,b}^*, w enthält genauso viele a's wie b's } regulär?

	1.	Ja.
	2.	Nein.

 

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