Zeige Beiträge 1 bis 12 von 12 Treffern |
|
Thema: Verständnisfragen zu Aufgabe zur primitiven Rekursion |
|
Leider kann ich einen Schritt in einer Übungsaufgabe nicht nachvollziehen:
Sei definiert durch für alle
Zeigen Sie, dass f primitiv rekursiv ist, indem Sie angeben, wie sich f aus
den primitiv rekursiven Grundfunktionen und der Multiplikationsfunktion mul
mittels der Operatoren Sub und Prim erzeugen lässt.
Nun soll laut Lösung die folgende zweistellige Funktion f die Rekursionsgleichung erfüllen:
1. Warum findet die Rekursion über y statt? Intuitiv würde ich zwar ebenfalls y nehmen, aber mir ist nicht wirklich klar warum.
2. Was für mich viel wichtiger ist: Wie kommt man auf die Umformung zu f(x,y+1)? Meines Erachtens kann man zwar das letzte Glied der Summe, also von der Summe abtrennen, aber die weiteren Umformungen sind mir leider schleierhaft und so fällt es mir leider schwer den Rest der Lösung zu verstehen.
|
|
Thema: Programmieren lernen... aber wie? |
Asgard
Antworten: |
10 |
Hits: |
14.197 |
|
|
Ich gestehe, dass ich das Buch schon lange nicht mehr angerührt habe und dass auch nicht alles mit Java Gently gemacht wird. Aber vieles lässt sich leider nicht direkt anhand des Buches nachvollziehen; wenn ich mich recht entsinne ist das simple Einlesen einer Datei ein Beispiel.
Uns wurde das Buch auch von einer Professorin empfohlen; in der Übung wurde jedoch nie etwas von Java Gently verwendet, sondern lediglich die Klassen, welche Java direkt bietet.
|
|
Thema: Programmieren lernen... aber wie? |
Asgard
Antworten: |
10 |
Hits: |
14.197 |
|
|
"Java lernen" ist ganz niedlich, aber lediglich tauglich für eine Einführungsvorlesung. Judy Bishop beschreibt lediglich anhand des Paketes "Java Gently", welches aber normalerweise niemals Einzug in ein ernsthaftes Java-Programm finden würde. In unserem Programmierpraktikum hätten sie uns wohl gesteinigt, hätten wir was davon eingebaut
Mein Rat: Finger weg von diesem Buch, wenn man es nicht gerade unbedingt für eine Vorlesung braucht.
Eine weitere gute Quelle ist "Java ist auch eine Insel". Kann kostenlos heruntergeladen werden, ist aber meines Erachtens etwas knapp gehalten, so dass ein paar Vorkenntnisse nicht schaden würden.
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Jetzt sehe ich ihn nicht mehr, aber Du veränderst auch gerade Deine Aussagen
Zitat: |
...
|
Zitat: |
Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist.
...
Wenn M und N beliebige Mengen sind, dann kann man sagen: |
Jetzt bin ich verwirrt
Doch so langsam kommt die Erleuchtung auf simplem Wege:
Aus folgt ja eigentlich, dass , für den Fall, dass .
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Ich verstehe nur Folgendes nicht so ganz:
Zitat: |
Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist. |
Wenn nun also , so müsste dann doch auch für jedes gelten, da doch laut obiger Aussage das leere Wort in der Konkatenation zweier Sprachen liegt, wenn es in beiden Sprachen vorhanden ist. Wo ist hier mein Denkfehler?
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Ist hier nicht ein Widerspruch?
Zitat: |
Original von Tobias
Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist.
Sei also in mindestens einem für . Für i=1 ist der Fall klar. Für i>1 gilt:
und somit greift der Satz von oben. |
Auf der einen Seite ist wenn und .
Auf der anderen Seite ist aber , wenn in mindestens einem für n>0 ist. Somit könnte doch durchaus ein existieren.
Auch steht im Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning Folgendes:
Zitat: |
Mit bezeichnen wir |
EDIT: Wie menschlich das Versagen! Mein Fehler liegt darin, dass alles was ich meine, auf Alphabete bezogen ist und nicht auf Sprachen.
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Entweder verstehe ich Dich falsch, oder in unserer Vorlesung wurde etwas anderes gelehrt.
Für sei
- der Kleene-Abschluss von L.
Folgerung:
Laut dieser Definition würde doch das leere Wort bei einer Sprache ausschließen?!?
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Es gilt z.B.:
Mit dem Sternchen beschreibt man die Menge aller Wörter. Im Beispiel gilt also:
Mit dem Plus wird die Menge aller nichtleeren Wörter beschrieben. Das Epsilon fällt also raus.
Bei Deiner Aufgabe kann man sehen, dass aus S nicht das leere Wort gebildet werden kann. Um alle Nichtterminalzeichen zu eleminieren musst Du mindestens zwei Ableitungen ausführen, wobei Du Terminalzeichen erzeugst. Das gebildete Wort kann also nie leer sein.
Der Beweis sieht gut aus, vielen Dank. Dürfte für meine Klausurvorbereitung sehr nützlich sein
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Meine Beweisidee wäre Folgende, wobei ich aber auf Induktion verzichten würde. In unserer Übung wurde gesagt, man könne es auch ausformuliert aufschreiben, aber ich weiß nicht, ob das auch wirklich ausreichend ist. Wäre schön, wenn jemand mit Ahnung dazu etwas sagen könnte.
: Sei . Hier wäre zu zeigen, dass eine Ableitung existiert, um daraus zu folgern, dass .
: Sei nun . Dann gilt . Hier wäre dann der Wortaufbau zu beschreiben, wie es Tobias in seiner Herleitung der Sprache gemacht hat, um zu zeigen, dass .
Natürlich wäre ein Beweis mittels Induktion schöner, aber ich habe immernoch keine Ahnung, wie dieser auszusehen hätte.
|
|
Thema: Welche Sprache erzeugt diese Grammatik |
Asgard
Antworten: |
17 |
Hits: |
24.773 |
|
|
Müsste es nicht eher
lauten (also + statt *), da eine Epsilon-Produktion erst im zweiten Schritt möglich ist?
Um dieses zu beweisen, musst Du zeigen. wird bei uns meist durch Induktion über die Wortlänge, durch Induktion über die Anzahl der Ableitungsschritte gezeigt. Wie dies im konkreten Fall aussehen könnte ist mir aber selbst noch schleierhaft.
|
|
Thema: Grammatik zu Sprache finden |
Asgard
Antworten: |
7 |
Hits: |
11.277 |
|
|
Zitat: |
Original von lego
wenn ich keinen Gedankenfehler habe, dann wäre
S->aT
T->baT
T->#
rechtslineare Grammatik und
S->Tab
T->Tab
T->Va
V->#
linkslinar Grammatik oder nicht? |
Diese Produktionen würden weder zu einer rechts-, noch zu einer linkslinearen Grammatik gehören. Bei einer rechtslinearen Grammatik sind alle Produktionen von der Form A -> aB oder A -> # . Also fällt eine Produktion "T->baT" raus.
Zitat: |
Original von Abakus
Ja, wobei allerdings #-Produktionen nicht allzu beliebt sind. Meist wird versucht, ohne die auszukommen. |
Im Grunde hast Du ja Recht, aber bei rechts- bzw. linkslinearen Grammatiken sind Epsilon-Produktionen per Definiton gewünscht
Eine linkslineare Grammatik wäre meines Erachtens:
S -> Ta
T -> Sb | #
|
|
|
Zeige Beiträge 1 bis 12 von 12 Treffern |
|
|
|