Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 4 von 4 Treffern

Autor

Beitrag

Thema: EBNF Grammatik

joho

Antworten:	3
Hits:	4.303

22.01.2017 16:07

Forum: formale Sprachen

Zitat:

Jetzt z.B bei aabab zu a{(ab)}{a}

Das erste a stimmt

Genau, das a aus aabab deckt das erste a aus dem Ausdruck $[latex]\underline{a}\{(ab)\}[b]\{a\}[/latex]$ .

Zitat:

darauf folgt ab von aabab was wieder an der richtigen Position steht (" $[latex]a\{(ab)\}[b]\{a\}[/latex]$ ") danach folgt ab von aabab das b kann weggelassen werden zur Bedingung ( " $[latex]a\{(ab)\}[b]\{a\}[/latex]$ " )und das a auch ? Ich verstehe nicht ganz inwiefern die Postionen der Buchstaben eine Rolle spielen. Anscheinend ja schon und wieder rum nicht.

Also die zwei ab aus aabab werden von $[latex]\{(ab)\}[/latex]$ abgedeckt, da die geschweiften Klammer ja beliebig oft wiederholt werden können, wie du ja selber gesagt hast.
Das [latex][b][/latex]

und das $[latex]\{a\}[/latex]$ am Ende werden bei dem Wort aabab gar nicht benutzt.
Die Positionen spielen eine Rolle, da keine Gruppe bzw keine Buchstaben aus dem Ausdruck vor einem anderen benutzt werden darf, wenn er dahinter steht.

Zitat:

z.B bei ab ich nenne ab mal "Prüfterm" zur Bedingung $[latex]a\{(ab)\}[b]\{a\}[/latex]$

Das a steht an erster Stelle von ab. Dann folgt als Bedingung a{(ab)} so kann ich jetzt das {(ab)} weglassen oder muss ich dies sogar weil die Position von meinem "Prüfterm" ab nicht stimmmt.

Für das Wort [latex]ab[/latex]

musst du dann das $[latex]\{(ab)\}[/latex]$ weglassen, da sonst durch das [latex]a[/latex]

von $[latex]a\{(ab)\}[/latex]$ ja mindestens [latex]2 a[/latex]

am Wortanfang stehen müssten.

Zitat:

Quasi, das ich aab als "Prüfterm" definieren müsste anstatt ab wenn die Bedigung a(ab) genannt worden wäre ? ab wäre bei der bestimmung von a(ab) falsch ?

Ja, bei a(ab) wäre aab auch ein akzeptiertes Wort und ab nicht.

Zitat:

Wenn ich die Bediung weiter mit ab durch gehe könnte ich ja {a} weglassen und zu beginn {(ab)} was passiert jetzt mit dem b von ab ? Muss dies irgendwie in die Bedingung eingebracht werden? Was man nach {(ab)}[b].. bei dem [b] machen könnte oder spielt das keine Rolle wahrscheinlich schon.

Das b muss auf jeden Fall auch mit abgedeckt sein. Genau wie alle anderen Buchstaben in einem Wort immer durch einen Teil des Ausdrucks abgedeckt sein müssen.
Im Fall von [latex]ab[/latex]

und $[latex]a\{(ab)\}[b]\{a\}[/latex]$ wäre es genau wie du geschrieben hast. Das [latex]a[/latex]

wird durch das [latex]a[/latex]

ganz am Anfang abgedeckt und das [latex]b[/latex]

durch

Generell musst du dir überlegen ob sich irgendwie durch die Verwendung der einzelnen Teile des Ausdruck, das zu überprüfende Wort basteln lässt. Dabei können die optionalen Teile an jeder Stelle weggelassen werden oder natürlich auch öfter wiederholt im Falle der geschweiften Klammern.

Thema: Bestimmung Anzahl der Operationen & Komplexität

joho

Antworten:	1
Hits:	3.384

Bestimmung Anzahl der Operationen & Komplexität 22.01.2017 00:19

Forum: Berechenbarkeits- und Komplexitätstheorie

Hey,

generell schaut man sich für alle Schritte eines Algorithmus an wie oft sie wiederholt werden und wieviele Schritte dort jeweils ausgeführt werden.
Anschließend fasst man diese Schritte zusammen und vereinfacht sie (Konstanten sind nicht relevant, da sie für das Wachstum bei Betrachtung von großen [latex]n[/latex]

nicht ausschlaggebend sind).

Bei deinem Beispiel sollte das wie folgt aussehen:

1. Initialisieren von min und max. 2 Schritte und 1. wird nicht wiederholt. [latex]O(2)[/latex]

2. paarweiser Vergleich und 2 Vergleich für min und max -> also 3 Schritte. 2. wird insgesamt für alle [latex]i=1,3,5,...,n[/latex]

wiederholt. Also $[latex]\frac{n}{2}[/latex]$ mal. Zusammen ist das für 2. $[latex]O(3 * \frac{n}{2}) = O(\frac{3}{2}* n)[/latex]$

Insgesamt wäre die Laufzeit also:
$[latex]O(O(2) + O(\frac{3}{2}* n)) [/latex]$
$[latex]\Rightarrow O(O(\frac{3}{2}* n))[/latex]$
$[latex]\Rightarrow O( O( n))[/latex]$
$[latex]\Rightarrow O(n)[/latex]$ , da sich die Konstanten [latex]O(2)[/latex]

und die $[latex]\frac{3}{2}[/latex]$ aus $[latex]O(\frac{3}{2}* n)[/latex]$ kürzen lassen.

Falls du noch Fragen hast gerne her damit.

LG

Thema: EBNF Grammatik

joho

Antworten:	3
Hits:	4.303

EBNF Grammatik 21.01.2017 22:51

Forum: formale Sprachen

Hey,

also das erste [latex]a[/latex]

von $[latex]a\{(ab)\}[b]\{a\}[/latex]$ ist wie du als zweites vermutet hast eine Bedingung und bedeutet nichts anderes als, dass das Wort auf jeden Fall mit einem [latex]a[/latex]

beginnen muss.

Du kannst es dir auch als $[latex](a)\{(ab)\}[b]\{a\}[/latex]$ vorstellen, nur das man sich die runden Klammern um das einzelne [latex]a[/latex]

auch sparen kann.

An den Wörtern [latex]aba[/latex]

und

ändert dies jedoch nichts.

$[latex]a\{(ab)\}[b]\{a\}[/latex]$ bedeutet ausgeschrieben:

Ein Wort wird akzeptiert wenn es mit einem [latex]a[/latex]

beginnt. Daraufhin darf beliebig oft [latex]ab[/latex]

folgen. Im Anschluss kann noch ein [latex]b[/latex]

kommen und ganz zuletzt kann das Wort mit beliebig vielen [latex]a's[/latex]

enden.

Weiter Beispielwörter die akzeptiert werden wären:

a, ab, aabb, aabab, abaa, aaaaaaa...

Ich hoffe das konnte dir irgendwie schon mal helfen. Sonst kannst du gerne noch weiter fragen.

LG

Thema: PSPACE-vollständigkeit

joho

Antworten:	0
Hits:	2.908

PSPACE-vollständigkeit 21.01.2017 22:30

Forum: Berechenbarkeits- und Komplexitätstheorie

Hallo allerseits Wink

,

ich hänge bei dem Beweis der PSPACE-vollständigkeit der Sprache:

$[latex]L = \{\langle c(M), w, 1^n \rangle :[/latex]$ Turingmaschine [latex]M[/latex]

, die das Wort [latex]w[/latex]

akzeptiert und dabei höchstens [latex]n[/latex]

Bandzellen besucht $[latex]\}[/latex]$

1. Reicht es um zu zeigen, dass $[latex]L \in PSPACE[/latex]$ , wenn eine universelle TM konstruiert wird, welche [latex]M[/latex]

simuliert, aber nach spätestens [latex]n[/latex]

Schritten stoppt, falls M nicht vorher terminiert?

2. Für den Beweis, dass [latex]L[/latex]

auch

ist, muss ich [latex]L[/latex]

auf ein anderes Problem aus [latex]PSPACE[/latex]

reduzieren?

und genau bei 2. stehe ich echt auf dem Schlauch.

Schon mal vielen Dank im voraus smile

Zeige Beiträge 1 bis 4 von 4 Treffern