Allg. Fragen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:12 Sa 15.02.2014 | | Autor: | vadi |
| Aufgabe | 2^() = ()
L* = (e) falls L=(e)
L x () = ()
Jede unendliche Sprache enthält das leere Wort
Wenn eine Funktion f: X* -> X* berechenbar ist, dann terminiert das Programm fp, das f berechnet für alle w e X*
Wenn eine Funktion f: X* -> X* nicht berechenbar ist, dann gibt es für jede berechenbare Funktion fp einen Wert w e X* an dem f nicht mit fp übereinstimmt.
Zu jeder berechenbaren Funktion f: X* -> X* gibt es ein Programm P, so dass f = fp für alle w e X* |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
e steht für Elemente
() Klammern entrechten Mengen Klammern, daraus folgt () = leere Menge
klein x steh für Mal.
Ich habe ein paar Thesen, welche ich noch bewerten muss bei denen ich mir nicht sicher bin ob sie stimmen oder nicht! Würde mich über eure Antworten freuen! Es gibt nur richtig oder falsch, aber über eine Begründung von euch würde ich sehr dankbar sein!
Also schonmal viel Dank vorab!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:05 So 16.02.2014 | | Autor: | tobit09 |
Hallo vadi und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
Wie du Punkt 8. der Forenregeln entnehmen kannst, versteht sich dieses Forum nicht als "Lösungsmaschine", sondern Lösungen werden zusammen mit den Fragesteller(inne)n erarbeitet.
Der erste Schritt im Falle dieser Aufgabenstellung lautet: Mache dir die Definitionen klar und poste Sie hier.
> 2^() = ()
Was bedeutet [mm] $2^M$ [/mm] für eine Menge $M$?
> L* = (e) falls L=(e)
Was bedeutet [mm] $L^\*$ [/mm] für eine Sprache $L$?
> L x () = ()
Was bedeutet [mm] $L_1*L_2$ [/mm] für Sprachen [mm] $L_1,L_2$?
[/mm]
> Jede unendliche Sprache enthält das leere Wort
Nenne mal ein paar unendliche Sprachen.
> Wenn eine Funktion f: X* -> X* berechenbar ist, dann
> terminiert das Programm fp, das f berechnet für alle w e
> X*
Wie habt ihr definiert, wann eine Funktion berechenbar ist?
> Wenn eine Funktion f: X* -> X* nicht berechenbar ist, dann
> gibt es für jede berechenbare Funktion fp einen Wert w e
> X* an dem f nicht mit fp übereinstimmt.
(Ich nehme mal an, mit "für jede berechenbare Funktion [mm] $f_p$" [/mm] ist gemeint: "für jede berechenbare Funktion [mm] $f_p\colon X^\*\to X^\*$")
[/mm]
Hier braucht es ausnahmsweise gar nicht die genaue Definition der Berechenbarkeit:
Kann es eine nicht berechenbare Funktion [mm] $f\colon X^\*\to X^\*$ [/mm] geben, die mit einer berechenbaren Funktion [mm] $f_p\colon X^\*\to X^\*$ [/mm] auf allen Werten [mm] $w\in X^\*$ [/mm] übereinstimmt?
> Zu jeder berechenbaren Funktion f: X* -> X* gibt es ein
> Programm P, so dass f = fp für alle w e X*
Wie habt ihr "berechenbar" definiert?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:51 So 16.02.2014 | | Autor: | vadi |
Naja unendliche Sprachen sind beispielsweise N.... etc.
Berechenbar bedeutet erstens das die Funktion / das Programm terminiert und zweitens das von uns gewollte Ergebnis erhalten..... halt berechnen im üblichen Sinne.
Hilft dir das weiter?
Mir leider nicht sonderlich.....
Es geht bei meinen Aufgaben auch nicht um eine HA oder sowas.... sowas gibts bei mir gar nicht mehr, sondern viel mehr um meine Abschluss Fragen für mein Verständnis.... Also hab mir da schon was dabei Gedacht!
Vielen Dank schon einmal vorab!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:07 So 16.02.2014 | | Autor: | tobit09 |
> Naja unendliche Sprachen sind beispielsweise N.... etc.
Meinst du mit $N$ die Menge [mm] $\IN$ [/mm] der natürlichen Zahlen?
Sie ist zwar eine unendliche Menge, aber keine Sprache (über irgendeinem Alphabet).
Schlage also zunächst nach, wie eine Sprache (über einem Alphabet [mm] $\Sigma$) [/mm] genau definiert ist.
Dann kannst du dich auf die Suche nach einer unendlichen Sprache ohne das leere Wort machen.
> Berechenbar bedeutet erstens das die Funktion / das
> Programm terminiert und zweitens das von uns gewollte
> Ergebnis erhalten..... halt berechnen im üblichen Sinne.
Funktionen können überhaupt nicht terminieren oder nicht terminieren.
Programme terminieren im Allgemeinen bei gewissen Eingaben und bei anderen Eingaben nicht.
Wann heißt nun eine Funktion [mm] $f\colon X^\*\to X^\*$ [/mm] berechenbar?
Vermutlich habt ihr folgende Definition getroffen:
Eine Funktion [mm] $f\colon X^\*\to X^\*$ [/mm] heißt berechenbar, wenn ein Programm $p$ existiert, das für alle [mm] $w\in X^\*$ [/mm] terminiert und [mm] $f_p=f$ [/mm] erfüllt.
Liege ich damit richtig?
Wenn ja, versuche damit, die letzte und die drittletzte Aussage auf ihre Korrektheit zu überprüfen.
> Hilft dir das weiter?
> Mir leider nicht sonderlich.....
Angenommen [mm] $\IN$ [/mm] wäre eine unendliche Sprache wie von dir (fälschlicherweise) vermutet.
Enthält sie das leere Wort? Nein. Also hättest du eine unendliche Sprache gefunden, die nicht das leere Wort enthält. Damit wäre die Aussage
"Jede unendliche Sprache enthält das leere Wort."
falsifiziert.
> Es geht bei meinen Aufgaben auch nicht um eine HA oder
> sowas.... sowas gibts bei mir gar nicht mehr, sondern viel
> mehr um meine Abschluss Fragen für mein Verständnis....
> Also hab mir da schon was dabei Gedacht!
Dann teile uns doch diese Gedanken mit. Gerade da du sowieso gar nicht die Lösungen sondern das Verständnis brauchst, bringt das ungleich mehr.
Es würde sicher schneller gehen, wenn du auf alle meine Rückfragen eingehen würdest.
Möglicherweise weißt du nicht alle Definitionen genau. Dann gilt es nachzuschlagen!
Eine Sache habe ich bisher noch vergessen nachzufragen: Soll bei der Aussage
" L* = (e) falls L=(e) "
e dass leere Wort bezeichnen oder einen Buchstaben oder noch etwas anderes?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:07 So 16.02.2014 | | Autor: | vadi |
Danke für deine Bemühungen.......Naja danke aufjedenfall für die Langen Tipps und Ratschläge.... Auch wenn das keine Lösungsfabrik sein soll.... Hätten deine Antworten ruhig konkreter sein können mittlerweile in einem langen Prozess alles gelöst!
Es ist nicht gleich eine Lösungsfabrik, wenn die Lösungen vorgeschlagen werden und dann darüber diskutiert wird.... Naja wie auch immer wünsche euch noch ganz viel Spaß!!! Und vokalem Erfolg für mich ist das hier definitiv nichts.....
Mein Fazit: Das hat nichts mit Hilfestellung zu tun.... Alles das wusste ich auch schon lange vorher..... tipps ohne Tipps zu geben funktioniert nunmal nicht!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:30 So 16.02.2014 | | Autor: | tobit09 |
> Danke für deine Bemühungen.......Naja danke aufjedenfall
> für die Langen Tipps und Ratschläge.... Auch wenn das
> keine Lösungsfabrik sein soll.... Hätten deine Antworten
> ruhig konkreter sein können mittlerweile in einem langen
> Prozess alles gelöst!
Wenn du die Aufgaben selbst lösen konntest, ist das doch ungleich besser als eine fertige Lösung studiert zu haben!
> Es ist nicht gleich eine Lösungsfabrik, wenn die Lösungen
> vorgeschlagen werden und dann darüber diskutiert wird....
Wenn du tatsächlich über die Lösungen diskutieren möchtest, kannst du gerne deine posten.
> Naja wie auch immer wünsche euch noch ganz viel Spaß!!!
> Und vokalem Erfolg für mich ist das hier definitiv
> nichts.....
> Mein Fazit: Das hat nichts mit Hilfestellung zu tun....
> Alles das wusste ich auch schon lange vorher.....
> tipps
> ohne Tipps zu geben funktioniert nunmal nicht!
Ich habe dir doch zu allen sieben Teilaufgaben Tipps gegeben. Gerade wenn du nun die fertigen Lösungen vor dir liegen hast, ist mir ein Rätsel, wieso du nicht siehst, dass ich dich ziemlich in deren Richtung versucht habe zu stupsen:
Bei den ersten drei Aufgabenteilen ergeben sich die Lösungen fast direkt aus den entsprechenden Definitionen.
Bei der vierten Aussage geht es darum, eine unendliche Sprache ohne das leere Wort zu finden. Schwierigkeiten hattest du offenbar dabei, eine unendliche Sprache zu finden. Daher kann mein Hinweis, dies zu versuchen nicht so verkehrt gewesen sein.
Fünf und Sieben ergeben sich direkt aus der Definition der Berechenbarkeit, wie ich sie formuliert habe.
Zu Teil Sechs habe ich auch aus meiner Sicht das Entscheidende geschrieben.
Deine Posts haben auf mich nicht den Eindruck gemacht, dir sei alles von mir Geschriebene schon klar. Umso wichtiger ist es als Fragesteller zu schildern, was einem schon klar ist und woran es noch hakt. Wenn Fragesteller zur aktiven Mitarbeit bereit sind, dringen die Antworten in der Regel auch bis zum Kern der Schwierigkeiten vor.
|
|
|
|
