Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 11 von 11 Treffern
Autor Beitrag
Thema: Umsetzung Semaphor (Examensaufgabe Bayern)
Mathlet

Antworten: 0
Hits: 2.881
Umsetzung Semaphor (Examensaufgabe Bayern) 15.08.2016 17:27 Forum: Theoretische Informatik


Hallo zusammen,

jetzt habe ich gerade noch einmal eine Anfrage zu Semphoren. Mir ist klar wie die grundsätzlich funktionieren, aber mit einer Aufgabe hier komme ich gerade nicht 100%ig zurecht:
http://www.lehramt-informatik.de/downloa...66114-H2008.pdf => Letzte Aufgabe "Synchronisation"

Mir wird eine rudimentäre Klasse für Semphoren gegeben und ich soll das Problem Initialisieren und zwei Klassen vervollständigen.
Gegeben:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
public interface Sempahore{
	public void wait();
	public void signal();	
}
public class BinarySemaphore implements Semaphore{
	public BinarySemaphore(){ ... }
}
public class CountingSemaphore implements Semaphore{
	public CountingSemaphore(int N){ ... }
}


a) Bekomme ich soweit hin (wobei ich mir bei der Variablen studierende nicht sicher bin).
b) und c) bin ich mir aber nicht so sicher... Vor allem die while-Schleife ist ziemlich sicher falsch, da er ja mit dem Semaphor automatisch blockiert...
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
// Kontrolliert Zugang zum Vorzimmer des Professors
Semaphore vorzimmer = new CountingSemaphore(3);

// Der Professor bei der Beratungstätigkeit
Semaphore professor = new BinarySemaphore();

// Die auf den Sitzplätzen wartenden Studierenden
Semaphore studierende = new CountingSemaphore(0);

public class Student extends Thread {
	public void run() {
		vorzimmer.down(); // Student möchte Vorzimmer betreten

		<Student betritt das Vorzimmer des Professors>

		studierende.up();	// Sobald er drin ist, zeigt er an, dass er im Vorzimmer ist und sendet damit ein Signal an den Professor
		professor.down(); // Student möchte zum Professor

		<Student betritt das Zimmer des Professors>

		studierende.down();	// Student darf ins Zimmer, also ist ein Student weniger im Wartezimmer
		vorzimmer.up(); // Student gibt seinen Warteplatz im Wartezimmer frei, da er ja jetzt beim Professor sitzt.
	}
}

public class Professor extends Thread {
	public void run() {
		while ( !studierende.down() ) // Solange die Warteliste leer ist (Aber blockiert da der Professor nicht?)
		{
			<Professor forscht>
		}
		professor.up(); // Professor hat auf das Signal hin aufgehört zu forschen und Student darf rein

		<Professor berät einen Studenten>

		professor.up(); // Student verlässt den Professor
	}
}


Für hilfreiche Tipps jederzeit dankbar :-D
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
07.08.2016 12:26 Forum: formale Sprachen


Ich glaube, mein Graph müsste jetzt endgültig passen. Also danke, du musst dir nicht noch einmal extra die Mühe machen!
Nur noch kurz die Frage: Ich hab das richtig verstanden, dass ich mit diesem Graph eines DEA ja auch schon bewiesen habe, dass die Sprache definitiv regulär ist, richtig?
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
07.08.2016 09:35 Forum: formale Sprachen


Kein Ding! Vielen Dank schon mal für deine Hilfe und auch die von eulerscheZahl!
Ihr habt mich zu einer vermutlich richtigen Lösung geführt Daumen hoch
Hab gestern auch mal den regulären Ausdruck gemacht... großes Grinsen
Die Grammatik hab ich mir erst mal gespart...
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 23:16 Forum: formale Sprachen


Stattgegeben Daumen hoch
Wie ich da nen schönen NEA konstruiere unglücklich
Ich hab bisher eigentlich nur DEAs konstruiert und nen gegebenen NEA mit dem Potenzmengenalgorithmus auf nen DEA reduziert. Ist das konstruieren eines NEAs einfacher? Dann wäre es sicherlich die bessere Herangehensweise.
NEA --- Potenzmengenalgorithmus ---> DEA --- Table-Filling-Algorithmus ---> min. DEA
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 22:54 Forum: formale Sprachen


Doch noch mal einen neuen Zustand dazu... Gibt es jetzt noch Einsprüche?
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 22:46 Forum: formale Sprachen


Nächster Versuch... Oh mann... sowas im Examen und traurig
Und wenn ich gerade drüber nachdenke, passt es wieder nicht...
00110010 wird nicht akzeptiert....
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 22:23 Forum: formale Sprachen


Das wäre mein aktueller Versuch.. spontan finde ich auch keine Fehler mehr... (ja, Startzugang vergessen!)

EDIT: Bei Karlito würde folgendes Wort akzeptiert werden:
0010010
->q0->q1->q2->q3->q4->q5->q4->q5

EDIT2:
Sollte meine Lösung korrekt sein, dann verstehe ich nicht mehr die Teilaufgabe b) (=>Siehe Anhang erster Post), weil ich keinen neuen Zustand mehr brauche, um einen DEA zu konstruieren (mit b) und 7 Zuständen habe ich a) ja bereits bewiesen und einen DEA konstruiert....)...
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 22:15 Forum: formale Sprachen


Nein! Halt - immer noch ein Fehler! weil ja 0010010 akzeptiert wird... Zunge raus
EDIT: Da war ich zu spät, aber Karlitos Lösung ist auch noch nicht richtig... Wir sind nah dran!
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 22:10 Forum: formale Sprachen


Ah! Das schaut gut aus!
Ich bin gerade auf fast den gleichen gekommen, aber ich hatte q7 anders definiert - habs jetzt an deinen Graph angepasst und sehe gerade keinen Fehler mehr! Danke! :-)
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
06.08.2016 21:33 Forum: formale Sprachen


Hallo eulerscheZahl,

Erst mal Danke für deine Idee.

Den Graph hatte ich auch schon so in etwa... es müssten dann ja erst mal alle Zustände außer q8 Endzustände sein.
Aber (und vielleicht liegt hier irgendwo mein Denkfehler)...
Ich könnte mit dem DEA folgendes Wort konstruieren:
001000010 indem ich die Zustände ablaufe q0->q1->q2->q3->q4->q5->q6->q4->q4->q5
Das Wort würde (wenn q5 ein Endzustand wäre, was er zum Akzeptieren des Wortes 00100 sein müsste) akzeptiert werden, obwohl es zweimal die Folge 0010 beinhaltet... Oder hab ich da was mistverstanden?
Thema: Suche regulären Ausdruck/Grammatik für Sprache
Mathlet

Antworten: 22
Hits: 13.904
Suche regulären Ausdruck/Grammatik für Sprache 06.08.2016 19:55 Forum: formale Sprachen


Hallo zusammen,

mein erster Eintrag hier Willkommen

Ich habe eine Aufgabe, in welcher ich zeigen möchte, dass eine Sprache regulär ist:
Alphabet ist E={0,1} und Sprache L Teilmenge von E*

L = {w | in w kommt das Teilwort 0010 höchstens einmal vor}

Ich denke, ich könnte entweder eine rechtslineare Grammatik finden oder einen regulären Ausdruck oder einen DEA... aber irgendwo hackt es gerade Zunge raus - ich komm nicht dahinter, wie ich eines der drei Dinge konstruiere (wenn man eines hinbekommt, dann kommt man ja absolut easy auf die anderen...).
Über das Pumping-Lemma komm ich ja auch nicht weiter, wenn ich das Ding nicht irgendwie konstruieren kann, oder?

Danke für eure Ideen!
Liebe Grüße Matthias

EDIT: Ich lade mal die ganze Aufgabe hoch, denn die weiteren Teilaufgaben beinhalten vielleicht einen Hinweis auf die Lösung...
Zeige Beiträge 1 bis 11 von 11 Treffern