Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

81

Tuesday, February 11th 2003, 9:55pm

ok, dann müsste ich also nur noch Pumping Lemma machen, um zu zeigen, dass sie nicht Typ 3 ist und dann wäre der Beweis aber fertig und korrekt so?
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

82

Tuesday, February 11th 2003, 9:56pm

Quoted

Original von Cipher
ok, dann müsste ich also nur noch Pumping Lemma machen, um zu zeigen, dass sie nicht Typ 3 ist und dann wäre der Beweis aber fertig und korrekt so?



Jawoll, er wär' dann fertich und korrekt.
Matthias Galota
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

83

Tuesday, February 11th 2003, 10:10pm

da kommt doch freude auf :D
  • Send private message

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

84

Wednesday, February 12th 2003, 11:25am

So, kurz vor Toresschluss noch eine letzte Aufgabe :) zu
http://www-thi.informatik.uni-hannover.d…en/uebung08.pdf

Ein LBA der a^n b^n c^n | n>=1 erkennt:

M=({z0,z1,z2,z3,z4,z5}, {a,b,c}, {a,b,c,[],>,<}, o, [], {z5})

o:

;; a suchen und ersetzten
o(z0, a) = o(z1, [], R)

;; b suchen und ersetzen
o(z1, a) = (z1, a, R)
o(z1, []) = (z1, [], R)
o(z1, b) = (z2, [], R)

;; c suchen und ersetzen
o(z2, b) = (z2, b, R)
o(z2, []) = (z2, [], R)
o(z2, c) = (z3, [], L)

;; Zurück zum Anfang
o(z3, a) = (z3, a, L)
o(z3, b) = (z3, b, L)
o(z3, c) = (z3, c, L)
o(z3, []) = (z3, [], L)
o(z3, >) = (z4, >, R)

;; Nächstes a suchen
o(z4, a) = (z1, [], R)
o(z4, []) = (z4, [], R)
o(z4, <) = (z5, <, N)

z5 ist Endzustand


korrekt ?

Habs korrigiert !
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

85

Wednesday, February 12th 2003, 11:47am

ne, der funzt bei mir nicht.
wenn ich den test mit aabbcc mache, dann habe ich nach dem ersten "ganz nach links gehen" folgendes:
>[]a[]b[]c<
und dann ist er ja im z4 und geht wegen dem ersten [] einen nach rechts und bleibt in z4.
dann liest er ein a und macht es zu [] und geht in z1 über. das nächste zeichen ist dann aber ein [], aber das wird in z1 nicht erfasst -> das wort wird nicht akzeptiert.

Cipher
  • Send private message

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

86

Wednesday, February 12th 2003, 11:51am

Soo...besser ? :)
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

87

Wednesday, February 12th 2003, 11:56am

ne, noch ein kleiner fehler:

o(z3, >) = (z3, >, R)
müsste das sein:
o(z3, >) = (z4, >, R)
  • Send private message

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

88

Wednesday, February 12th 2003, 11:58am

Stimmt...thx.

So...bin dann erstmal off.
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

89

Wednesday, February 12th 2003, 12:46pm

Quoted

Original von sr409
So, kurz vor Toresschluss noch eine letzte Aufgabe :) zu
http://www-thi.informatik.uni-hannover.d…en/uebung08.pdf

Ein LBA der a^n b^n c^n | n>=1 erkennt:

M=({z0,z1,z2,z3,z4,z5}, {a,b,c}, {a,b,c,[],>,<}, o, [], {z5})

o:

;; a suchen und ersetzten
o(z0, a) = o(z1, [], R)

;; b suchen und ersetzen
o(z1, a) = (z1, a, R)
o(z1, []) = (z1, [], R)
o(z1, b) = (z2, [], R)

;; c suchen und ersetzen
o(z2, b) = (z2, b, R)
o(z2, []) = (z2, [], R)
o(z2, c) = (z3, [], L)

;; Zurück zum Anfang
o(z3, a) = (z3, a, L)
o(z3, b) = (z3, b, L)
o(z3, c) = (z3, c, L)
o(z3, []) = (z3, [], L)
o(z3, >) = (z4, >, R)

;; Nächstes a suchen
o(z4, a) = (z1, [], R)
o(z4, []) = (z4, [], R)
o(z4, <) = (z5, <, N)

z5 ist Endzustand


korrekt ?

Habs korrigiert !


Ist wohl zu spät aber dieser LBA ist falsch. Er akzeptiert z.B. auch aabcbc. Den gleichen Fehler habe ich übrigens auch bei meiner ersten Lösung gemacht :(
Matthias Galota
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

90

Wednesday, February 12th 2003, 1:13pm

kann man da auch einen 3-Band LBA benutzen ?

(falls es das überhaupt gibt...jedenfalls fällt mir dafür die lösung irgendwie leichter ein :) )
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

91

Wednesday, February 12th 2003, 1:24pm

Quoted

Original von Cipher
kann man da auch einen 3-Band LBA benutzen ?

(falls es das überhaupt gibt...jedenfalls fällt mir dafür die lösung irgendwie leichter ein :) )



3-Band-LBAs gibt es leider nicht :(
Matthias Galota
  • Send private message

pj

Praktikant

Posts: 13

Date of registration: Nov 27th 2002

92

Wednesday, February 12th 2003, 1:30pm

Quoted

Original von Cipher
kann man da auch einen 3-Band LBA benutzen ?

(falls es das überhaupt gibt...jedenfalls fällt mir dafür die lösung irgendwie leichter ein :) )



Na, da will ich doch auch mal einen Tipp geben, damit auch andere Ideen erwachsen...

Man muss ja nicht die angesehenen Zeichen (a,b,c) löschen, sondern kann sie auch in andere Buchstaben umwandeln...
Wie wäre es denn, a in A, b in B und c in C umzuwandeln?

Damit kann man sicherstellen, dass nicht am Ende nochmal ein abc auftauchen könnte... Hilft das vielleicht?

pj
  • Send private message