Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 12 von 12 Treffern

Autor

Beitrag

Thema: Verständnisfragen zu Aufgabe zur primitiven Rekursion

Asgard

Antworten:	1
Hits:	4.683

Verständnisfragen zu Aufgabe zur primitiven Rekursion 14.02.2007 21:22

Forum: Theoretische Informatik

Leider kann ich einen Schritt in einer Übungsaufgabe nicht nachvollziehen:

Sei $[latex]f: \mathbb N ^2 \to \mathbb N [/latex]$ definiert durch $[latex]f(x,y) := \sum_{i=o}^y~x^i [/latex]$ für alle $[latex]x,y \in \mathbb N [/latex]$
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:

[latex]f(x,0)=1[/latex]

$[latex]f(x,y+1)=(x\cdot \sum_{j=0}^y~x^j)+1=(x\cdot f(x,y))+1[/latex]$

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 $[latex]x^{y+1}[/latex]$ 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:	13.994

13.02.2007 14:55

Forum: Sonstige Fragen

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:	13.994

13.02.2007 13:18

Forum: Sonstige Fragen

"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 großes Grinsen

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.261

10.12.2006 23:49

Forum: Theoretische Informatik

Jetzt ist das Licht endlich aufgegangen. Vielen Dank für Deine Geduld.

Thema: Welche Sprache erzeugt diese Grammatik

Asgard

Antworten:	17
Hits:	24.261

10.12.2006 22:11

Forum: Theoretische Informatik

Jetzt sehe ich ihn nicht mehr, aber Du veränderst auch gerade Deine Aussagen Augenzwinkern

Zitat:

$[latex]\epsilon \in L \iff \epsilon \in L^+[/latex]$

...

$[latex]x \in L^+ \iff x \in L^i \text{ fuer ein } i \geq 1[/latex]$

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: $[latex]x \in M \cup N \iff x \in M \vee x \in N[/latex]$

Jetzt bin ich verwirrt großes Grinsen

Doch so langsam kommt die Erleuchtung auf simplem Wege:
Aus $[latex]L^{+} = L^{*}L[/latex]$ folgt ja eigentlich, dass $[latex]\epsilon \in L^{+}[/latex]$ , für den Fall, dass $[latex]\epsilon \in L[/latex]$ .

Thema: Welche Sprache erzeugt diese Grammatik

Asgard

Antworten:	17
Hits:	24.261

10.12.2006 21:15

Forum: Theoretische Informatik

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 $[latex]\epsilon \in L^{+}[/latex]$ , so müsste dann doch auch $[latex]\epsilon \in L^{i}[/latex]$ für jedes $[latex]i \geq 1[/latex]$ 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.261

10.12.2006 19:29

Forum: Theoretische Informatik

Ist hier nicht ein Widerspruch?

Zitat:

Original von Tobias
$[latex] \Leftarrow [/latex]$
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 $[latex]\epsilon \in L^+[/latex]$ also in mindestens einem [latex]L^i[/latex]

für $[latex]i \geq 1[/latex]$ . Für i=1 ist der Fall klar. Für i>1 gilt:
$[latex]L^i = LL^{i-1}[/latex]$ und somit greift der Satz von oben.

Auf der einen Seite ist $[latex]\epsilon \in MN[/latex]$ wenn $[latex]\epsilon \in M[/latex]$ und $[latex]\epsilon \in N[/latex]$ .

Auf der anderen Seite ist aber $[latex]\epsilon \in L^{n}=LL^{n-1}[/latex]$ , wenn $[latex]\epsilon[/latex]$ in mindestens einem $[latex]L^{i}[/latex]$ für n>0 ist. Somit könnte doch durchaus ein $[latex]L^{i}~mit~\epsilon \not\in L^{i}[/latex]$ existieren.

Auch steht im Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning Folgendes:

Zitat:

Mit $[latex]{\sum}^{+}[/latex]$ bezeichnen wir $[latex]{\sum}^{*} - \{\epsilon\}[/latex]$

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.261

10.12.2006 18:35

Forum: Theoretische Informatik

Entweder verstehe ich Dich falsch, oder in unserer Vorlesung wurde etwas anderes gelehrt.

Für $[latex]L \subseteq {\sum}^{*}[/latex]$ sei

$[latex]L^{*} = \bigcup_{n\geq 0} L^{n} = \{w_1 ... w_n | n\geq 0, w_i \in L~fuer~i=1,...,n \}[/latex]$ der Kleene-Abschluss von L.
$[latex]L^{+} = \bigcup_{n\geq 1} L^{n} = \{w_1 ... w_n | n\geq 1, w_i \in L~fuer~i=1,...,n \} = LL^{*}[/latex]$

Folgerung: $[latex]L^{*} = L^{+} \cup L^{0} = L^{+} \cup \{\epsilon\}[/latex]$

Laut dieser Definition würde doch $[latex]L^{+}[/latex]$ das leere Wort bei einer Sprache ausschließen?!?

Thema: Welche Sprache erzeugt diese Grammatik

Asgard

Antworten:	17
Hits:	24.261

10.12.2006 17:18

Forum: Theoretische Informatik

Es gilt z.B.: $[latex]\{a\}^{*}\{a\} = \{a\}^{+}[/latex]$

Mit dem Sternchen beschreibt man die Menge aller Wörter. Im Beispiel gilt also: $[latex]\{a\}^{*} = \{\epsilon, a, aa, aaa, aaaa, ....\}[/latex]$
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 Augenzwinkern

Thema: Welche Sprache erzeugt diese Grammatik

Asgard

Antworten:	17
Hits:	24.261

10.12.2006 14:06

Forum: Theoretische Informatik

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.

$[latex]L \subseteq L(G)[/latex]$ : Sei $[latex]w \in L[/latex]$ . Hier wäre zu zeigen, dass eine Ableitung $[latex]S \Rightarrow ^{*} w[/latex]$ existiert, um daraus zu folgern, dass $[latex]w \in L(G)[/latex]$ .

$[latex]L(G) \subseteq L[/latex]$ : Sei nun $[latex]w \in L(G)[/latex]$ . Dann gilt $[latex]S \Rightarrow ^{*} w[/latex]$ . Hier wäre dann der Wortaufbau zu beschreiben, wie es Tobias in seiner Herleitung der Sprache gemacht hat, um zu zeigen, dass $[latex]w \in L[/latex]$ .

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.261

09.12.2006 21:36

Forum: Theoretische Informatik

Müsste es nicht eher

$[latex]L=\{w_1w_2 \mid w_1\in \{a,b\}^{+}, w_2\in \{a,b\}^{+}, \mid w_1 \mid = \mid w_2 \mid \}[/latex]$

lauten (also + statt *), da eine Epsilon-Produktion erst im zweiten Schritt möglich ist?

Um dieses zu beweisen, musst Du [latex]L = L(G)[/latex]

zeigen. $[latex]L \subseteq L(G)[/latex]$ wird bei uns meist durch Induktion über die Wortlänge, $[latex]L(G) \subseteq L[/latex]$ 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.004

09.12.2006 12:03

Forum: Theoretische Informatik

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 Augenzwinkern

Eine linkslineare Grammatik wäre meines Erachtens:

S -> Ta
T -> Sb | #

Zeige Beiträge 1 bis 12 von 12 Treffern