Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 15 von 19 Treffern

Seiten (2): [1] 2 nächste »

Autor

Beitrag

Thema: Ableitungsbaum aus dem CYK Algo

foogi

Antworten:	2
Hits:	6.749

10.02.2007 17:39

Forum: Theoretische Informatik

ok wie ich den Baum erstelle weiß ich nun:

Man muss sich nur beim ausfüllen der Tabelle notieren, welche Produktionen man genutzt hat, notieren, dass man die Regel S -> BD angewandt hat, um aus den Feldern (1,3) und (4,6) auf das S in (1,6) zu schließen.

Gibt es nun eine Möglichkeit, um auf die Sprache zu kommen?
also was wäre hier L(G)?

und kann man eine Aussage darüber treffen, ob L deterministisch kontextfrei ist? wenn ja anhand von was?

Thema: Entscheidbarkeit von Zahlen..

foogi

Antworten:	4
Hits:	6.604

09.02.2007 12:15

Forum: Theoretische Informatik

Zitat:

Original von Tobias
Eine Menge heißt rekursiv entscheidbar oder einfach entscheidbar, wenn es einen Algorithmus gibt, der nach endlicher Zeit terminiert und entscheidet, ob die Eingabe zur Menge gehört oder nicht. (Wikipedia)

Du musst also nur entscheiden, ob ein vorgegebenes (aber beliebiges) Element zu Menge gehört oder nicht. Sprich hier: Ist die Zahl n gerade oder ungerade.

Den Rest kannst du dir selber denken.

ich fragte das, weil mir nciht klar ist, warum die Goldbachsche Vermutung nicht entscheidbar ist. Diese basagt, das jede Zahl größer 4, als Summe zweier Primzahlen dargestellt werden kann. Wieso geht das dann hier niciht, wenn es aber bei den Geraden Zahlen geht?

Thema: Ableitungsbaum aus dem CYK Algo

foogi

Antworten:	2
Hits:	6.749

Ableitungsbaum aus dem CYK Algo 09.02.2007 12:09

Forum: Theoretische Informatik

hallo,

wenn ich eine CNF Normalform habe, und dise dann kann man ja mit dem CYK Algorithmus bestimmen, ob das Wort in der Sprache ist oder nicht. Wenn das Wort nun in der Sprache ist, so ist ja das letzte Nichtterminal ein S, bzw das Startsymbol. Soweit so gut, kann ich nun systematisch den Ableitungsbaum erstellen, oder geht das nur mit rumprobieren?

also ich hab folgendes Wort zum ableiten:

abbaba

die Grammatik ist folgende:

S--> AB|BA|AC|BD
A--> a| BE
B--> b| AF
C--> BS
D--> AS
E--> AA
F--> BB

so, das Wort ist in der Sprache, weil ich ja als letztes auf S komme,
(1,6).
wie komme ich nun auf den Ableitungsbaum?

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	X 1 2 3 4 5 6 1 A S B S C S 2 B F C 3 B S C S 4 A S D 5 B S 6 A

EDIT: Code-Tags zugefügt -- ED

Thema: Entscheidbarkeit von Zahlen..

foogi

Antworten:	4
Hits:	6.604

Entscheidbarkeit von Zahlen.. 31.01.2007 15:40

Forum: Theoretische Informatik

hallo,

wie kann man eigentlich entscheiden, ob nun gerade Zahlen entscheidbar sind oder nicht?

sind sie es? wenn ja warum?

ich dachte man kann nur etwas entscheiden wenn man es auch beweisen kann, aber die Zahlen sind doch unendlich?

und wie sieht es mit Primzahlen aus?

danke

Thema: Angabe einer kontextfreien Grammatik

foogi

Antworten:	5
Hits:	7.007

31.01.2007 15:38

Forum: Theoretische Informatik

ja, und wie wäre es denn nun richtig?

Thema: Angabe einer kontextfreien Grammatik

foogi

Antworten:	5
Hits:	7.007

Angabe einer kontextfreien Grammatik 29.01.2007 17:28

Forum: Theoretische Informatik

hallo,
ich möchte für folgende sprache eine KFG angeben. nun weiß ich nicht ob ich das so richtig gemacht habe, und dann wollte ich noch wissen ob es denn ein systematisches vorgehen dabei gibt? denn ich brauch da immer viel zu lange...

L= { a^i b^j c^k| i,j,k >=0 und (i>=j oder j >= k)}

also entweder muss a=b oder größer b sein oder b=c oder größer c.

da bin ich auf folgendes gekommen:

S -> AS | EF | G
A -> aAb |aA | epsilon
E -> bEc | bE | epsilon
F -> c
G -> aGc | Gc | epsilon

ist die Lösung den richtig?

Thema: Pumping Lemma 2

foogi

Antworten:	3
Hits:	5.534

15.01.2007 15:42

Forum: Theoretische Informatik

Zitat:

Original von Tobias
Dein Beweis geht garnicht auf die Sprache ein.

Deine Zerlegung ist quatsch, denn das x hat nichts mit der Sprache zu tun. Deine anschließende Argumentation ist auch total konfus.

Wenn ein n existiert, so muss ein Wort der Länge 2n natürlich auch eine aufpumpbare Zerlegung haben.

Das Wort sieht dann so aus: [latex]a^nb^n[/latex]

Die Zerlegung ist ja dann auch klar:

Wegen $[latex]|uv| \leq n[/latex]$ muss [latex]uv = a^r[/latex]

mit $[latex]r \leq n[/latex]$ sein.

Kommst du nun weiter?

mit dem x meinte ich das die Wortlänge größer gleich n sein muss, wenn ein Pumping Lemma existiert. Und die länge von n kann man doch selber wählen, dachte ich, deswegen 2n. wenn ich 2n einsetze, so ist das Wort länger als n.

Die Zerlegung ist mir nicht ganz klar verwirrt

das Wort sollte man doch immer in 3 Teile zerlegen können? oder nicht?

Thema: Pumping Lemma frage

foogi

Antworten:	9
Hits:	8.898

15.01.2007 15:31

Forum: Theoretische Informatik

ok danke, die Aufgabe hab ich nun verstanden, allerdings fehlt mir noch einiges um andere Aufgaben selbst Lösen zu können.

Thema: Eine kontextfreie Grammatik für eine Sprache

foogi

Antworten:	5
Hits:	7.292

15.01.2007 15:26

Forum: Theoretische Informatik

hallo,

ich hatte folgende Sprache:

L={a^i b^j c^k |i,j,k >=0 und (i>=j oder j>=k)}

ich wäre auf folgende Lösung gekommen:

S--> A | B

A --> aAb | aA | epsilon

B --> bBc | bB | epsilon

da ja nur eine der Bedingungen erfüllt sein muss, müsste es doch richtig sein oder was meint Ihr dazu?

danke

Thema: Pumping Lemma 2

foogi

Antworten:	3
Hits:	5.534

Pumping Lemma 2 14.01.2007 19:35

Forum: Theoretische Informatik

hallo,

nach dem Beitrag vom Pumping Lemma, habe ich nun dazu weitere Fragen.

1. Kann ich nachdem selben Prinzip wie im vorigen Beitrag mit allen Sprachen umgehen? oder nach was muss ich mich da genau richten.

Beispiel:

wie würde ich diese Aufgabe denn richtig angehen? Denn wenn ich nach dem Prinzip vom vorigen Beitrag vorgehe, so komme ich irgendwie nicht auf die Lösung? oder?

L={a^k b^k| k>=1}

wenn ich nun als Wort 2n wähle, |x| >=n
dann zerlege ich das wort x= uvw in
u = x^q
v= x^r
w=x^s

2n = q+r+s

wegen |uv|<=n und |v|>=1 gilt ja 1<=r<=n

wenn ich nun aufpumpe, so habe ich

2n<|2n +r|<=2n+n

das nächste Wort wäre doch dann 2n+2, bei n=1 wäre es nicht enthalten,
ab n=2 aber schon??

Was habe ich nun falsch gemacht?

Danke

Thema: Pumping Lemma frage

foogi

Antworten:	9
Hits:	8.898

13.01.2007 22:40

Forum: Theoretische Informatik

Zitat:

so un habe ich mich nochmal damit beschäftigt, ich kann nun fast alles nachvollziehen, leider felht noch etwas..

Es geht darum die maximalen Grenzen von r auszuloten.
.. geht es im Pumping Lemma immer darum?

untere Schranke: $[latex]|v| = |a^r| = r \geq 1[/latex]$

obere Schranke: $[latex]|uv| = |a^qa^r| = q+r \leq n[/latex]$ . Das Lemma verbietet uns nicht q=0 und somit u=leeres Wort zu setzen. Nur mit q=0 kann man r maximal wählen, denn es gilt wegen $[latex]q \geq 0[/latex]$
$[latex]q+r \leq n \iff r \leq n-q \leq n[/latex]$

Wenn [latex]v = a^r[/latex]

dann ist $[latex]v^2 = a^{2r}[/latex]$ .

Somit ist wegen [latex]q+r+s = n^2[/latex]

$[latex]uv^2w = a^qa^{2r}a^s = a^{q + 2r + s} = a^{q+r+s}a^r = a^{(n^2)}a^r[/latex]$

Wir kennen nun die Grenzen von r: $[latex]1 \leq r \leq n[/latex]$ :

$[latex]|a^{(n^2)}a| \leq |a^{(n^2)}a^r| \leq |a^{(n^2)}a^n|[/latex]$

$[latex]a^{(n^2)}a^r[/latex]$ liegt also immer zwischen zwei Quadratzahlen, denn

und wie siehst du das? das die zwischen zwei quadratzahlen liegen

$[latex]|a^{(n^2)}a| > a^{(n^2)}[/latex]$
$[latex]|a^{(n^2)}a^n| < |a^{((n+1)^2)}|[/latex]$

den letzten Vergleich verstehe ich nicht, und wie kommst du auf
$[latex]{((n+1)^2)}[/latex]$ woher kommt das?

Sorry für die vielleicht dummen fragen, aber habs noch nicht ganz drauf..

Thema: Eine kontextfreie Grammatik für eine Sprache

foogi

Antworten:	5
Hits:	7.292

10.01.2007 22:33

Forum: Theoretische Informatik

hallo,

und wie könnte das konkret aussehen?
verwirrt

Thema: Eine kontextfreie Grammatik für eine Sprache

foogi

Antworten:	5
Hits:	7.292

Eine kontextfreie Grammatik für eine Sprache 10.01.2007 10:39

Forum: Theoretische Informatik

hallo,

gibt es ein systematisches Vorgehen, wenn man eine kontextfreie Grammatik für eine Sprache angben möchte?

ich möchte für diese Sprache:

L={a^i b^j c^k |i,j,k >=0 und (i>=j oder j>=k)}

eine kontextfreie Grammatik angeben.
Ich komme da auf keine Lösung, vor allem weiß ich nicht wie man da systematisch vorgehen kann..?

Thema: Eine Kontextfreie Sprache zur CNF

foogi

Antworten:	3
Hits:	5.744

10.01.2007 08:37

Forum: Theoretische Informatik

Zitat:

Original von Tobias
......
Eliminieren von $[latex]A \to \varepsilon[/latex]$

$[latex]S \to AC \; | \; C[/latex]$
$[latex]A \to aAb \; | \; ab[/latex]$
$[latex]C \to cC \; | \; \varepsilon[/latex]$

Eliminieren von $[latex]C \to \varepsilon[/latex]$

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to aAb \; | \; ab[/latex]$
$[latex]C \to cC \; | \; c[/latex]$

Nun führen wir für jedes Terminalsymbol [latex]a[/latex]

ein Nichtterminalsymbol [latex]X_a[/latex]

ein und ersetzen es überall dort, wo es gemischt mit Nichtterminalsymbolen vorkommt. Außerdem ergänzen wir die Regel $[latex]X_a \to a[/latex]$ .

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to X_aAX_b \; | \; X_aX_b[/latex]$ hmm wieso hast du eigentlich ab ersetz? weil oben hast du ja erwähnt, das nur diejenigen ersetzt werden, die gemischt sind? oder hab ich das falsch verstanden?
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Die Regel $[latex]A \to X_aAX_b[/latex]$ besteht aus drei Nichtterminalen. Das umgehen wir, indem wir einfach eine neue Produktion $[latex]Y \to AX_b[/latex]$ ergänzen und dann substituieren: $[latex]A \to X_aY[/latex]$ . Dieses Verfahren kann man ggf. mehrfach anwenden.

$[latex]S \to AC \; | \; C \; | \; A \; | \; \varepsilon[/latex]$
$[latex]A \to X_aY | \; X_aX_b[/latex]$
$[latex]Y \to AX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Die Produktion $[latex]S \to A[/latex]$ eliminieren wir, indem wir einfach die Produktionen von A zu S überleiten: $[latex]S \to X_aY | \; X_aX_b[/latex]$ .

Ebenso verfahren wir mit $[latex]S \to C[/latex]$ : $[latex]S \to X_cC \; | \; c[/latex]$

Wir erhalten also:
$[latex]S \to AC \; | \; X_aY | \; X_aX_b \; | \; X_cC \; | \; c \; | \; \varepsilon[/latex]$
$[latex]A \to X_aY | \; X_aX_b[/latex]$
$[latex]Y \to AX_b[/latex]$
$[latex]C \to X_cC \; | \; c[/latex]$
$[latex]X_a \to a[/latex]$
$[latex]X_b \to b[/latex]$
$[latex]X_c \to c[/latex]$

Das sollte es sein (hoffe ich).

achja dann wollte ich noch wissen:
wir haben ja folgendes eliminiert:
- Löschregeln
- Nutzlose Symbole

haben wir hier im Beispiel keine Kettenregel gehabt?
Hast du vielleicht ein einfaches Beispiel für eine Kettenregel, und wie man diese entfernt?

Deine Erklärung finde ich sehr gut.. Augenzwinkern

Thema: Eine Kontextfreie Sprache zur CNF

foogi

Antworten:	3
Hits:	5.744

Eine Kontextfreie Sprache zur CNF 10.01.2007 00:14

Forum: Theoretische Informatik

hallo,

ich habe ein konteztfreie Grammatik, und ich möchte diese in ein Chomsky Normalform umwandeln.
Ich weiß das dies nicht schwer ist, doch habe ich kein ausführliches Beispiel gefunden.

ich habe also:

S--> AC
A--> aAb | epsilon

C--> cC | epsilon

Nun muss man ja die epsilon Regeln entfernen, Kettentregeln, und Hilfsregeln benutzten.
Wie würde das anhand diesem einfachen Beispiel funktionieren.

Eine Schrittweise erläuterung wäre sinnvoll, so das ich das nachvollziehen kann.

vielen Dank

Zeige Beiträge 1 bis 15 von 19 Treffern

Seiten (2): [1] 2 nächste »