You are not logged in.

migu

free rider

  • "migu" is male
  • "migu" started this thread

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

1

Thursday, August 22nd 2002, 10:29am

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" is male

Posts: 163

Date of registration: Dec 11th 2001

2

Thursday, August 22nd 2002, 3:32pm

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

3

Thursday, August 22nd 2002, 6:53pm

Quoted

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.

Quoted

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

Thursday, August 22nd 2002, 7:13pm

Quoted

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)

Quoted

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.

Quoted

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" is male

Posts: 163

Date of registration: Dec 11th 2001

5

Thursday, August 22nd 2002, 7:27pm

VIELEN DANK


KreiS

Senior Schreiberling

  • "KreiS" is male

Posts: 701

Date of registration: Dec 17th 2001

Location: Hannover

Occupation: moep

6

Friday, August 23rd 2002, 4:59pm

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

7

Friday, August 23rd 2002, 5:37pm

Quoted

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)

Quoted

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" is male

Posts: 701

Date of registration: Dec 17th 2001

Location: Hannover

Occupation: moep

8

Friday, August 23rd 2002, 6:47pm

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

9

Friday, August 23rd 2002, 8:01pm

Quoted

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:

Source code

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" is male

Posts: 701

Date of registration: Dec 17th 2001

Location: Hannover

Occupation: moep

10

Friday, August 23rd 2002, 8:19pm

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

11

Friday, August 23rd 2002, 8:37pm

Quoted

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" is male

Posts: 701

Date of registration: Dec 17th 2001

Location: Hannover

Occupation: moep

12

Friday, August 23rd 2002, 9:01pm

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

Posts: 8

Date of registration: Aug 19th 2002

Location: France

13

Sunday, August 25th 2002, 11:33pm

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

14

Monday, August 26th 2002, 12:44am

Quoted

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.

Quoted

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" is male

Posts: 605

Date of registration: Feb 12th 2002

Location: Region Hannover

Occupation: Gartenbau

15

Monday, August 26th 2002, 11:15am

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

Posts: 131

Date of registration: Apr 21st 2002

16

Monday, August 26th 2002, 11:24am

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" is male

Posts: 605

Date of registration: Feb 12th 2002

Location: Region Hannover

Occupation: Gartenbau

17

Monday, August 26th 2002, 11:38am

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

Posts: 8

Date of registration: Aug 19th 2002

Location: France

18

Monday, August 26th 2002, 2:51pm

"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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

19

Monday, August 26th 2002, 3:09pm

Quoted

Original von Diktator
[Aufgabe 3]

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


Quoted

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.

Quoted

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

Quoted

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) )

Quoted

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

Quoted

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" is male

Posts: 701

Date of registration: Dec 17th 2001

Location: Hannover

Occupation: moep

20

Monday, August 26th 2002, 3:32pm

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"