Sie sind nicht angemeldet.

migu

free rider

  • »migu« ist männlich
  • »migu« ist der Autor dieses Themas

Beiträge: 2 643

Registrierungsdatum: 11.12.2001

Wohnort: Hannover

Beruf: Developer

1

22.08.2002, 10:29

Theo-Inf: Aufgaben

Hallo zusammen!

Dienstag steht die wunderbare Klausur zur Theoretischen Informatik an. Doch ich habe noch Fragen.

1) In der letzten Klausur musste in Aufgabe 8 der Automat minimiert werden. In der Klausur war ich an dieser Aufgabe verzweifelt, da das Verfahren, das ich kannte, nicht funktionierte. Wie minimiert man diesen Automat und geht das überhaupt?

2) Aufgabe 3 c): Nach meinen Erkenntnissen werden die Sprachen L3 und L6 erzeugt. Ist das richtig?

Vielen Dank im Voraus für hilfreiche Hinweise und Anregungen. :)

(migu)
tar: Anlegen eines leeren Archivs wird feige verweigert.

loki

Junior Schreiberling

  • »loki« ist männlich

Beiträge: 163

Registrierungsdatum: 11.12.2001

2

22.08.2002, 15:32

noch ne kleine frage...

Zu der aufgabe 5 in der letzten klausur:

a) L8= {(a^2)^n|n>=1}
b) L9= {(01)^n|n>=0}
c) L10={a^nb^n-3|n>=3}

Zu welcher Sprachklasse gehören die sprachen und warum zu keiner kleineren sprachklasse. mit Grammatik??? wir sind uns nicht einig....

schonmal vielen dank...

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

3

22.08.2002, 18:53

Zitat

Original von migu
1) In der letzten Klausur musste in Aufgabe 8 der Automat minimiert werden. In der Klausur war ich an dieser Aufgabe verzweifelt, da das Verfahren, das ich kannte, nicht funktionierte. Wie minimiert man diesen Automat und geht das überhaupt?
Das Verfahren aus der Vorlesung funktioniert. Eben ausprobiert. Am besten, du beschreibst mal genau deine Schritte bis zu der Stelle, an der du nicht weiterkommst.

Zitat

2) Aufgabe 3 c): Nach meinen Erkenntnissen werden die Sprachen L3 und L6 erzeugt. Ist das richtig?
Ich komme für die Sprache des Automaten auf den Ausdruck a^(n+1) b^(2n) mit n >= 0. Das wäre dann nur die Sprache L3.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

22.08.2002, 19:13

Zitat

Original von loki
a) L8= {(a^2)^n|n>=1}
Das ist glaube ich ein Fehler in der Klausurmitschrift. Ich meine, daß damals a^(2^n) gefragt war. (a^2)^n = (aa)^n wäre auch etwas arg einfach, da regulär.

Aber zu der Aufgabe habe ich schon mal was geschrieben:
http://forum.fsinf-hannover.de/thread.ph…16&styleid=1#16
(heißt dort im Thread zwar L7, ist aber die selbe Aufgabe)

Zitat

b) L9= {(01)^n|n>=0}
Ist regulär.

Grammatik:
S -> e | 0A
A -> 1S

L9 gehört zu keiner kleineren Sprachklasse, weil es keine kleinere Sprachklasse gibt.

Zitat

c) L10={a^nb^n-3|n>=3}
Ist kontextfrei.

Grammatik:
S -> a^3 A
A -> e | aAb

L10 ist nicht regulär, da L10 vom Typ a^k b^k ist.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

loki

Junior Schreiberling

  • »loki« ist männlich

Beiträge: 163

Registrierungsdatum: 11.12.2001

5

22.08.2002, 19:27

VIELEN DANK


KreiS

Senior Schreiberling

  • »KreiS« ist männlich

Beiträge: 701

Registrierungsdatum: 17.12.2001

Wohnort: Hannover

Beruf: moep

6

23.08.2002, 16:59

migu : die Sprache ist a | ( ( a | (a | b ) ) b* a (a|b)*
zusammen fassen kann man s1 und s5 zu s15 und s2 und s4 zu s24, das wars.

hat einer aufgabe 1 richtig gelösst, das entfernen an sich sollte ich richtig haben, nur zum DFA ergeben sich bei mir 8 zustände ;)
kaneda spring <-> ks <-> KreiS
"surrender is an option ...time to change everything" (ks '04)

Dakota-Indianer(Weisheit),"Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab"

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

7

23.08.2002, 17:37

Zitat

Original von KreiS
migu : die Sprache ist a | ( ( a | (a | b ) ) b* a (a|b)*
zusammen fassen kann man s1 und s5 zu s15 und s2 und s4 zu s24, das wars.
Hmmm, die neuen Zustände habe ich auch so, aber einen anderen regulären Ausdruck (mit deiner Klammerung scheint etwas nicht zu stimmen):

a |
a (a|b) b* a (a|b)* |
b+ a (a|b)*

(könnte man zwar noch zusammenfassen, das macht das ganze aber nicht lesbarer)

Zitat

hat einer aufgabe 1 richtig gelösst, das entfernen an sich sollte ich richtig haben, nur zum DFA ergeben sich bei mir 8 zustände
Ich komme auch auf acht Zustände, nämlich:
  • s0/1/5
  • s2
  • s7
  • s3/4
  • s0/1/5 / s3/4
  • s0/1/5 / s3/4 / s6
  • s0/1/5 / s6
  • s2 / s7
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

KreiS

Senior Schreiberling

  • »KreiS« ist männlich

Beiträge: 701

Registrierungsdatum: 17.12.2001

Wohnort: Hannover

Beruf: moep

8

23.08.2002, 18:47

also irgendwie stimmt bei 1 es wohl doch net
also s1 und s3 habe gestrichen bei e entfernung.

bei der Sprache habe ich wohl falsch vom Blatt abgeschrieben

entweder a
oder (aa | ab | b ) b* a (a|b)*
zusammen gebaut sollte es a | [ (a(a|b) | b) b* a (a|b)* ]

so, also ist es schon korrekt ;) hatte beim ersten post nen | b unterschlagen :-( auf dem Blatts stehts wenigstesns korrekt :-)

kaneda spring <-> ks <-> KreiS
"surrender is an option ...time to change everything" (ks '04)

Dakota-Indianer(Weisheit),"Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab"

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

9

23.08.2002, 20:01

Zitat

Original von KreiS
also irgendwie stimmt bei 1 es wohl doch net
also s1 und s3 habe gestrichen bei e entfernung.
Bei mir fallen s0, s1 und s2 zu s0/1/2 zusammen sowie s3 und s4 zu s3/4.

Dann ergibt sich für Aufgabenteil a) folgende Übergangstabelle:

Quellcode

1
2
3
4
5
6
7
  | s0/1/5 |   s2   |  s3/4  |   s6   |   s7   |
--+--------+--------+--------+--------+--------+
a |   s2   |   s7   |   s2   |   s7   |   s7   |
--+--------+--------+--------+--------+--------+
b | s0/1/5 |  s3/4  |  s3/4  |   s6   |  s3/4  |
  |   s6   | s0/1/5 |        |        |        |
--+--------+--------+--------+--------+--------+
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

KreiS

Senior Schreiberling

  • »KreiS« ist männlich

Beiträge: 701

Registrierungsdatum: 17.12.2001

Wohnort: Hannover

Beruf: moep

10

23.08.2002, 20:19

s3 lässte man weg und verbindet s2 mit s4 oder man vereint sie, kommt aus selbe hinaus.

bei s0 schlage ich ne verbindung zu s1
s0 a -> s2
s0 b -> s6 oder s0


wenn ich s1 und s0 zusammen fasse stimmts ja soweit auch.aber warum s5 mit s12 dann verschmelzen lassen, das blicke ich gerade net ;) ist das falsch was ich einschlage?! ;)

kaneda spring <-> ks <-> KreiS
"surrender is an option ...time to change everything" (ks '04)

Dakota-Indianer(Weisheit),"Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab"

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

11

23.08.2002, 20:37

Zitat

Original von KreiS
s3 lässte man weg und verbindet s2 mit s4 oder man vereint sie, kommt aus selbe hinaus.

bei s0 schlage ich ne verbindung zu s1
s0 a -> s2
s0 b -> s6 oder s0

wenn ich s1 und s0 zusammen fasse stimmts ja soweit auch.aber warum s5 mit s12 dann verschmelzen lassen, das blicke ich gerade net ;) ist das falsch was ich einschlage?! ;)
?( Kann ich gerade nicht ganz nachvollziehen, deine Beschreibung ist nicht besonders exakt.

Daher liste ich nochmal die Schritte auf, die ich durchgeführt habe. Kommt wahrscheinlich das selbe raus wie bei dir, der einzige Unterschied ist wahrscheinlich die Benennung der Zustände:

  1. s0 und s1 fallen zusammen zu s0/1. s0/1 ist dann Startzustand und Teil folgender Übergänge:
    s0/1: a -> s2
    s0/1: b -> s0/1
    s0/1: e -> s5
  2. s0/1 und s5 fallen zusammen zu s0/1/5. s0/1/5 ist dann Startzustand und Teil folgender Übergänge:
    s2: b -> s0/1/5
    s0/1/5: a -> s2
    s0/1/5: b -> s0/1/5
    s0/1/5: b -> s6
  3. s3 und s4 fallen zusammen zu s3/4. s3/4 ist dann Endzustand und Teil folgender Übergange:
    s2: b -> s3/4
    s7: b -> s3/4
    s3/4: a -> s2
    s3/4: b -> s3/4
    [/list=1]
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

KreiS

Senior Schreiberling

  • »KreiS« ist männlich

Beiträge: 701

Registrierungsdatum: 17.12.2001

Wohnort: Hannover

Beruf: moep

12

23.08.2002, 21:01

sorry ;p

bei deinem zweiten schritt, das ist doch e weg machen plus minimierung an der stelle ;)

eine sehr sparsame methode wie ich eingestehen muss, werde meinen automaten wohl auf jlap mal abilden und dann mit dem veränderten vergleichen, sollte ja aber das gleiche rauskommen. ;)
kaneda spring <-> ks <-> KreiS
"surrender is an option ...time to change everything" (ks '04)

Dakota-Indianer(Weisheit),"Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab"

Yann

Praktikant

Beiträge: 8

Registrierungsdatum: 19.08.2002

Wohnort: France

13

25.08.2002, 23:33

Aufgabe 4b

Weiß einer was diese §$%&/! Turingmaschine anrichtet?

Dividiert sie durch 3 mit rest angabe? wie ihr verhalten zeigen würde:

#0# -> endet auf #s1# bsw. #s4# also rest 0.

#0|# -> endet auf #s2# bws. #s4|# also rest 1.

#0||# -> endet auf #s3# bws. #|s4|# also rest 2.

#0|||# -> endet auf #s1# bws. #s4# also rest 0.

usw...

------------------------------------------------------------------------

Allerdings klapp es mit 1:3 und 2:3 nicht -> man erhält nämlich 1 bsw. 2...

------------------------------------------------------------------------

ist es ein modulo 3?

------------------------------------------------------------------------

und warum wird das Wort #||...||# akseptiert? weil er bringt alles durcheinander:

1,4,7,10 * | --> rest 0
2,5,8,11 * | --> rest 1
3,6,9,12 * | --> rest 2

------------------------------------------------------------------------

Ich glaub ich bin zu blöd... kann mir einer heeeeeeeeeelfen? ;(

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

14

26.08.2002, 00:44

Zitat

Original von Yann
Weiß einer was diese §$%&/! Turingmaschine anrichtet?
TM rechnet mod 3 mit der zweiten Zahl, siehe http://forum.fsinf-hannover.de/thread.ph…0&boardid=16#10.

Zitat

Allerdings klapp es mit 1:3 und 2:3 nicht -> man erhält nämlich 1 bsw. 2...
Ist ein Fehler in der Klausurmitschrift. Der dort genannte Zustandsübergang (s_0, |, s_1, #, r) müßte korrekt (s_0, | s_0, #, r) lauten. Dann macht das ganze auch wieder Sinn ...
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Diktator

Senior Schreiberling

  • »Diktator« ist männlich

Beiträge: 605

Registrierungsdatum: 12.02.2002

Wohnort: Region Hannover

Beruf: Gartenbau

15

26.08.2002, 11:15

klausuraufgabe 3

zu a)
expansive grammatik, da:
linke seite <= rechte seite (bei allen produktionen)

zu b)
a, aabb, aaabbbb sind die 3 kürzesten worte!

zu c)
L3 wird erzeugt, nachzuprüfen durch:
#a=k+1; #b=2*k

kann jemand diese ergebnisse verifizieren? ?(
Diktator
Holzhacken ist deshalb so beliebt, weil man bei dieser Tätigkeit den Erfolg sofort sieht. - Albert Einstein

Tara

Junior Schreiberling

Beiträge: 131

Registrierungsdatum: 21.04.2002

16

26.08.2002, 11:24

Hab mal n paar Fragen zu Turingmaschinen.

Wie leitet man das ab, wenn man ||0|| hat z.B. ???? Geht man einmal nach rechts alles durch und dann wieder zurück nach links und guckt dann was übrig bleibt???? Versteh das alles nicht ?(

Und wenn ich dies habe

#|0 s0 |# und jetzt hab ich:

(s0, 0, s1, c, l)

Wie sieht dann die nächste Zeile aus. Wenn ich nach rechts gehe ist mir das klar, aber wie sieht das aus wenn ich nach links gehe?

Diktator

Senior Schreiberling

  • »Diktator« ist männlich

Beiträge: 605

Registrierungsdatum: 12.02.2002

Wohnort: Region Hannover

Beruf: Gartenbau

17

26.08.2002, 11:38

klausuraufgabe 5

zu a)
eine mögliche grammatik wäre
S->Saa|aa.
sie erzeugt eine gerade anzahl von a's, mindestens aber zwei.
L8 gehört ferner zu regulären sprachen, da es einen endlichen automaten A gibt (drei zustände), so dass gilt L8=L(A).

zu b)
eine grammatik ist
S->e|01|S01 mit e=leeres wort.
L9 ist auch reguläre sprache, da ein endlicher automat mit drei zuständen existiert, der wörter von L8 erzeugt.

zu c)
eine grammatik ist
S->aaaTb; T->e|aTb.
L10 ist eine Typ-1-Sprache, da es keine kontextfreie grammatik dazu gibt. die genannte grammatik ist kontextsensitiv. folglich gibt es auch keinen kellerautomaten zu L10.

kann jemand auch diese ergebnisse bestätigen oder für schwachsinn erklären? ?(
Diktator
Holzhacken ist deshalb so beliebt, weil man bei dieser Tätigkeit den Erfolg sofort sieht. - Albert Einstein

Yann

Praktikant

Beiträge: 8

Registrierungsdatum: 19.08.2002

Wohnort: France

18

26.08.2002, 14:51

"Und wenn ich dies habe

#|0 s0 |# und jetzt hab ich:

(s0, 0, s1, c, l)

Wie sieht dann die nächste Zeile aus. Wenn ich nach rechts gehe ist mir das klar, aber wie sieht das aus wenn ich nach links gehe?"

Der näste eintrag sieht so aus: #| s1 c |#.

Du betrachtest nur die Zeichen die in der bewehgungs richtung sind... also hier nach links.


  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

19

26.08.2002, 15:09

Zitat

Original von Diktator
[Aufgabe 3]

kann jemand diese ergebnisse verifizieren?
Kann ich bestätigen.


Zitat

Original von Diktator
zu a)
eine mögliche grammatik wäre
S->Saa|aa.
sie erzeugt eine gerade anzahl von a's, mindestens aber zwei.
L8 gehört ferner zu regulären sprachen, da es einen endlichen automaten A gibt (drei zustände), so dass gilt L8=L(A).
Die Begründung finde ich etwas seltsam. Am besten, du argumentierst direkt über die Grammatik, d. h. stellst fest, daß die angegebene Grammatik linkslinear ist, es sich also bei L8 maximal um eine reguläre Sprache handelt. Zudem solltest du noch schreiben, warum L8 zu keiner kleineren Sprachklasse gehört. Das ist in diesem Fall klar: es gibt nämlich keine.

Zitat

zu b)
eine grammatik ist
S->e|01|S01 mit e=leeres wort.
Geht auch einfacher: S->S01|e

Zitat

L9 ist auch reguläre sprache, da ein endlicher automat mit drei zuständen existiert, der wörter von L8 erzeugt.
Solltest du IMHO anderes begründen (siehe meine Antwort zu a) )

Zitat

zu c)
eine grammatik ist
S->aaaTb; T->e|aTb.
Kleiner Fehler: Mit dieser Grammatik erzeugst du ein b am Ende zuviel. Sie müßte lauten: S->aaaT, T->e|aTb

Zitat

L10 ist eine Typ-1-Sprache, da es keine kontextfreie grammatik dazu gibt. die genannte grammatik ist kontextsensitiv. folglich gibt es auch keinen kellerautomaten zu L10.
Komische Begründung. Diese Grammtik ist kontextfrei, da auf der linken Seite immer nur ein Nichtterminal steht. Sie ist nicht regulär, da sie vom Typ a^kb^k ist. Und das ist bekanntlich mindestens kontextfrei.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

KreiS

Senior Schreiberling

  • »KreiS« ist männlich

Beiträge: 701

Registrierungsdatum: 17.12.2001

Wohnort: Hannover

Beruf: moep

20

26.08.2002, 15:32

zu 4c) hab ich nun nen Loop programm geschrieben
also das erste kann ich ja überspringen, ist ne dummy loop schleife halt :-)
das unten ist halt so, die schleife durchläuft x2 mal, wenn x2 = 1 oder =2 oder = 0 ist wird nix getan(brauche ja nur das am ende ausgeben :-D) sonst immer abgezogen
am ende wird es abgezogen,

read (x1, x2);
x3 := x2 + 0 ;

loop x1 do nop end;
loop x2 do
if x2 = 0 then nop
else
if x2 = 1 then nop
else
if x2 = 2 then nop
else
x2 := x2 - 3
endif;
endif;
endif;
end;

write (x2);
kaneda spring <-> ks <-> KreiS
"surrender is an option ...time to change everything" (ks '04)

Dakota-Indianer(Weisheit),"Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab"