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.

cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

21

Friday, February 25th 2011, 6:37pm

[4] Gesucht ein DEA zur Grammatik


(etwas groß geraten, sorry)

This post has been edited 1 times, last edit by "cartman" (Feb 25th 2011, 6:37pm)

  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

22

Friday, February 25th 2011, 7:09pm

Quoted from "cartman"

danke für die Hilfe, und ich wollt so sicher in den Keller gehen :-)

Jetzt hab ich mich noch an den weiteren versucht (mit Ausnahme des Automaten, der die Binärzahlen, die durch 3 teilbar sind akzeptiert)

[1]

Das ist schonmal kein DEA.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

23

Friday, February 25th 2011, 7:10pm

Quoted from "cartman"

[2]


[3]


[2]: aab sollte akzeptiert werden, wirds aber nicht.

[3]: baa sollte akzeptiert werden, wirds aber nicht.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

24

Friday, February 25th 2011, 7:16pm

Quoted from "cartman"

[4] Gesucht ein DEA zur Grammatik


(etwas groß geraten, sorry)

Der Automat akzeptiert (unter anderem) 001, was man mit der Grammatik jedoch nicht ableiten kann. Folglich kann der DEA nicht die gleiche Sprache akzeptierten wie die Grammatik generiert.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

25

Friday, February 25th 2011, 7:16pm

Quoted from "cartman"

[4] Gesucht ein DEA zur Grammatik


(etwas groß geraten, sorry)
ich glaube der ist so auhc nicht ganz richtig...

Z2 x 1 -> Z1

Z4 x 0 -> Z3

da er auf dem oberen pfad nicht mit 1 abbrechen kann

mfg Finn
Regierungen der industriellen Welt,...
  • Send private message

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

26

Friday, February 25th 2011, 7:20pm

- 1 geht mit erheblich weniger malarbeit, wenn du die ersten b Pfeile auf den gleichen Zustand zeigen lässt..
- 2 sieht falsch aus, ich würde das wie im Bild unten lösen.
- bei 3 dürfen, nachdem das erste b gelesen wurde durchaus noch a's kommen
- 4 sieht richtig aus, wobei ich gerad nicht 100% sicher bin, wie man Grammatiken in DEAs wandelt..^^

Zu 2:


edit: Ach Arne, wo du gerade hier bist... ;) - gehe ich richtig in der Annahme, dass bei DEAs von jedem nicht-Endzustand immer soviele Pfeile abgehen müssen, wie Variablen vorhanden sind? Irgendwas hab ich da in der Erinnerung - und du hast ja geschrieben, dass [1] kein DEA ist...

This post has been edited 2 times, last edit by "Xular" (Feb 25th 2011, 7:32pm)

  • Send private message

cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

27

Friday, February 25th 2011, 7:36pm



oder müssen da jetzt vom zweiten Endzustand zu z1, von z1->z2 und von z2->endzustand auch a's hin ?

This post has been edited 1 times, last edit by "cartman" (Feb 25th 2011, 7:38pm)

  • Send private message

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

28

Friday, February 25th 2011, 7:47pm

Da fehlen noch a's: Z1->Z1,Z2->Z2
Und ein b Ze->Ze2

This post has been edited 1 times, last edit by "Xular" (Feb 25th 2011, 7:48pm)

  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

29

Friday, February 25th 2011, 7:49pm

Quoted from "cartman"



oder müssen da jetzt vom zweiten Endzustand zu z1, von z1->z2 und von z2->endzustand auch a's hin ?


Ich glaube so müsste das sein...

mfg
Regierungen der industriellen Welt,...

This post has been edited 1 times, last edit by "Finn" (Feb 25th 2011, 7:49pm)

  • Send private message

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

30

Friday, February 25th 2011, 7:53pm

Jo :) - hatte ganz vergessen anzumerken, dass auch das leere Wort akzeptiert werden soll, wollte ich eigentlich mal vor ner halben std ^^
  • Send private message

cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

31

Friday, February 25th 2011, 8:03pm

stimmt, ich sollte nochmal auf Reset drücken

nochmal zu dem hier: L:={a^n b^m | 0 <= n <= 2 <= m}

die Wörter können hier folgendermaßen aufgebaut sein
a) kein a, mindestens 2 b's
b) ein a, mindestens 2 b's
c) zwei a, mindestens 2 b's

sehe ich das wenigstens richtig, bevor ich da einen neuen Anlauf starte
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

32

Friday, February 25th 2011, 8:05pm

Quoted from "cartman"

stimmt, ich sollte nochmal auf Reset drücken

nochmal zu dem hier: L:={a^n b^m | 0 <= n <= 2 <= m}

die Wörter können hier folgendermaßen aufgebaut sein
a) kein a, mindestens 2 b's
b) ein a, mindestens 2 b's
c) zwei a, mindestens 2 b's

sehe ich das wenigstens richtig, bevor ich da einen neuen Anlauf starte

Ja
Regierungen der industriellen Welt,...
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

33

Friday, February 25th 2011, 8:22pm



das ist meiner

mfg Finn
Regierungen der industriellen Welt,...
  • Send private message

cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

34

Friday, February 25th 2011, 8:52pm

sieht wohl gut aus, danke für die hilfe ! (bei mir war es ja a)kein DEA (danke auch für die Erinnerungen mit den abgehenden Pfeilen bei Nicht-Endzuständen) und b)hatte ich den Fall nicht beachtet, dass der Automat dann bei mehr als 2 a's in ner Endlosschleife verschwindet)

für heute lasse ich das aber erstmal besser, ich kann keine kreise mehr sehen
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

35

Friday, February 25th 2011, 9:07pm

Quoted from "cartman"

sieht wohl gut aus, danke für die hilfe ! (bei mir war es ja a)kein DEA (danke auch für die Erinnerungen mit den abgehenden Pfeilen bei Nicht-Endzuständen) und b)hatte ich den Fall nicht beachtet, dass der Automat dann bei mehr als 2 a's in ner Endlosschleife verschwindet)

für heute lasse ich das aber erstmal besser, ich kann keine kreise mehr sehen
ämm was meinst du damit??

also bei einem DEA müssen von JEDEM zustand (egal ob end- oder nicht) für JEDES element aus dem eingabealphabet GENAU EIN pfeil ausgehen

mfg Finn
Regierungen der industriellen Welt,...
  • Send private message

cartman

Junior Schreiberling

  • "cartman" is male

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

36

Friday, February 25th 2011, 9:10pm

ok, noch eine erkenntnis mehr, ich und die theoretische informatik werden keine freunde mehr

(xular hatte das ja so angedeutet)

This post has been edited 1 times, last edit by "cartman" (Feb 25th 2011, 9:11pm)

  • Send private message

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

37

Friday, February 25th 2011, 10:10pm

Quoted from "Finn"

Quoted from "cartman"

sieht wohl gut aus, danke für die hilfe ! (bei mir war es ja a)kein DEA (danke auch für die Erinnerungen mit den abgehenden Pfeilen bei Nicht-Endzuständen) und b)hatte ich den Fall nicht beachtet, dass der Automat dann bei mehr als 2 a's in ner Endlosschleife verschwindet)

für heute lasse ich das aber erstmal besser, ich kann keine kreise mehr sehen
ämm was meinst du damit??

also bei einem DEA müssen von JEDEM zustand (egal ob end- oder nicht) für JEDES element aus dem eingabealphabet GENAU EIN pfeil ausgehen

mfg Finn


Soweit ich mich erinnere gilt das nicht für Endzustände, oder?

In meinen Übungsunterlagen haben nur ca die Hälfte der DEAs Pfeile bei den Endzuständen...
  • Send private message

Finn

Alter Hase

Posts: 126

Date of registration: Oct 10th 2010

38

Friday, February 25th 2011, 10:20pm

skript seite 7:

Quoted

Bemerkung: δ ist total, d.h. für alle z ∈ Z und a ∈ Σ gibt es ein z' ∈ Z, so dass

δ(z, a) = z'

Endzustände sind auch ∈ Z

mfg Finn
Regierungen der industriellen Welt,...
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

39

Saturday, February 26th 2011, 10:39am

Quoted from "Xular"

Quoted from "Finn"

Quoted from "cartman"

sieht wohl gut aus, danke für die hilfe ! (bei mir war es ja a)kein DEA (danke auch für die Erinnerungen mit den abgehenden Pfeilen bei Nicht-Endzuständen) und b)hatte ich den Fall nicht beachtet, dass der Automat dann bei mehr als 2 a's in ner Endlosschleife verschwindet)

für heute lasse ich das aber erstmal besser, ich kann keine kreise mehr sehen
ämm was meinst du damit??

also bei einem DEA müssen von JEDEM zustand (egal ob end- oder nicht) für JEDES element aus dem eingabealphabet GENAU EIN pfeil ausgehen

mfg Finn


Soweit ich mich erinnere gilt das nicht für Endzustände, oder?

In meinen Übungsunterlagen haben nur ca die Hälfte der DEAs Pfeile bei den Endzuständen...


Bei einem DEA *muss* es für jeden Zustand, insbesondere auch die Endzustände, für *jedes* Symbol des Eingabealphabets einen Übergang geben. Sonst ist das kein DEA.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Xular

Trainee

  • "Xular" is male

Posts: 62

Date of registration: Oct 7th 2007

40

Sunday, February 27th 2011, 2:25pm

Danke für die Klarstellung.
Um mal von den DEAs wegzukommen - kann mir jemand den Satz von Rice erklären?
Google versagt da leider und in den Übungen wurde nur die Lösung vorgestellt zu 3 solchen Aufgaben, ohne genauer drauf einzugehen, wie man zu der Lösung kommt...

Beispielsweise an der Aufgabe 5 der letzten Klausur:

5. Ist die Sprache
L := { w € {0,1}* | es gibt nur endlich viele Wörter x, so dass Mw bei Eingabe x hält }
entscheidbar?

Lösungshinweis:
L ist unentscheidbar nach dem Satz von Rice, da
L = { w € {0,1}* | Mw berechnet eine Funktion aus der Menge S }
für S := Menge aller Funktionen mit endlichem Definitionsbereich.


Der Lösungshinweis ist höchstwahrscheinlich nicht das, was in der Klausur zu einer vollen Punktzahl geführt hätte - weil ohne Erklärung.

Was wäre denn eine Lösung, die zu einer vollen Punktzahl geführt hätte?

Und wie kommt man auf "S := Menge aller Funktionen mit endlichem Definitionsbereich." - ist das IMMER so? Wohl eher nicht...?

This post has been edited 1 times, last edit by "Xular" (Feb 27th 2011, 2:26pm)

  • Send private message