Formale Sprachen - Was ist ein Wort?

Bild zum Beitrag

Ein Wort setzt sich ja aus dem Symbolen eines Alphabets zusammen. In dem Beispiel 0 und 1

Wenn ich in den DFA das Wort 00101 eingebe, wäre das ja ein ungültiges Wort nach meinem Verständnis. Meine Frage ist, ob ich die Eingabe/Wort 00101 o.a immer als ein zusammenhängendes Wort betrachten muss oder auch 00 und 101 möglich wäre.

Die Frage kommt daher, da in meinem Entwurf der Automat in den Endzustand "Invalid" kommt sofern 00 oder 11 enthalten ist.

Also vielleicht ist der Gedanke auch totaler Quatsch aber ich wollte es trotzdem mal erfragen.

Bild zum Beitrag

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

teehouse

19.03.2024, 21:27

Ja, 00101 führt zum invalid state. Und ja, mit 00 oder 11 im Wort kommt man in den invalid state. Wenn du ein Wort prüfen willst, musst du natürlich das ganze Wort eingeben. Oder ich verstehe die Frage nicht.

Nachtrag: Man könnte sich noch fragen, ob der Automat auch wirklich minimal ist. Aber ich glaube das ist er.

PsySkill

Fragesteller

19.03.2024, 21:49

Mit der Frage hast du jeden Aspekt meiner Frage beantwortet. Danke

Ähnliche Fragen

NFA in DFA umgewandelt?

Meine Lösung:

NFA in DFA umgewandelt

Feedback bitte!

...zur Frage

Sei L die formale Sprache der syntaktisch korrekten Java-Programme?

...zur Frage

reguläre Sprachen epsilon als eigene Äquivalenzklasse?

Wie viele Äquivalenzklassen dieser regulären Sprache gibt es, die Lösung ist nachfolgend angegeben.

Lösung:

Wie man sieht gibt es hier genau 3 Äquivalenzklassen.

Was mich verwundert ist, warum man hier epsilon selbst als Äquivalenzklasse berücksichtigt? epsi mit Präfix ac steht doch nicht in Relation zu epsi mit präfix abc oder epsi mit Präfix abbc ...?

Anderes Bsp. Sprache ist wieder regulär

....

Es gibt unendlich viele Äquivalenzklassen. Soweit klar!

Warum berücksichtig man jetzt hier in dem Bsp. nicht epsilon selbst als Äquivalenzklasse, wie in dem Bsp. zuvor

epsi + Präfix ab oder epsi + Präfix aabb oder epsi + Präfix aaabbb...

Kann mir dies bitte jemand erklären. Danke!

...zur Frage

Warum lässt sich jedes Problem in P auf jedes andere Problem in P reduzieren und was heißt das?

Ich habe gerade gelernt, dass man jedes Entscheidungsproblem L1 über Σ in P auf jedes andere Problem L2 über Σ aus P reduzieren kann. Mit hat es hier "die Kette rausgehauen":

Eine Reduktion ist ja eine berechenbare Abbildung

jetzt könnte ich festlegen Σ = Natürliche Zahlen von 1 bis 1 Million

L1 = {w ∈ Σ | w ist prim)

L2 = {w ∈ Σ | w ist gerade)

und definieren:

f(w) = 6 wenn w prim

f(w) = 7 wenn w nicht prim

Dies erfüllt genau die obige Definition einer Reduktion.

Nur welchen Sinn macht es, hier von einer "Reduktion" zu sprechen, denn ich habe ja den Primtest auf eine Zahl nicht auf den Test auf Geradheit einer Zahl zurückgeführt.

Ich hätte intuitiv etwas als Reduktion bezeichnet, wenn ich durch die Entscheidung L2 auch L1 entscheiden kann. Hier liegt aber aus meiner Laiensicht ein "fauler Zauber" vor, denn in der Abbildungsvorschrift f ist eigentlich schon enthalten, dass ich dafür schon die Entscheidung auf Prim durchführen, also L1 lösen muss. Es "hört sich aber so an", als könnte man nun einen Primtest (der ja, obwohl in P liegend, relativ komplex ist) auf etwas "reduzieren", wo man nur auf Geradheit prüft (was ja von der Komplexität nicht vergleichbar ist). Jedenfalls ist das nicht im Sinne der Erfindung eines "funktionierenden" Algorithmus für L1, den ich zu lösen vermag, indem ich L2 löse.

Ich hoffe, ich habe mich in meiner Notation verständlich ausgedrückt und man weiß, was ich meine...(bin kein Informatiker, daher bitte Milde walten lassen ;-)

Habe ich eine falsche Vorstellung von einer Reduktion oder ist das einfach so?

...zur Frage

Kontextfreie Grammatik erstellen?

Hey, ich habe folgende Aufgabe:

Aufgabe a habe ich hinbekommen, aber bei Aufgabe b bin ich planlos.

Kann mir da jemand helfen?

...zur Frage

Äquivalenzklassen gemäß Myhill-Nerode genau drei Stück?

1 Reihe, die Wörter sind alle Elemente der Sprache, man würde als Präfix epsi dranhängen. Klar soweit

2 Reihe hier fehlt jeweils ein b, damit die Wörter Elemente der Sprache sind

3 Reihe: alle anderen Wörter. Dies verstehe ich nicht:

{a } hier fehlt ein einzelnes b. Oder ist dieses {a} eigentl. schon in der 2 Reihe dabei?

{ epsi} hier fehlt ab , dies müsste die 3 Reihe darstellen, auch wenn hier steht alle anderen Wörter
Warum gibt es hier "genau" drei Äquivalenzklassen?

...zur Frage

Theoretische Informatik Halteproblem etc.?

Fragen:

=> In welche Komplexitätsklasse fällt das Halteproblem?

Das Halteproblem ist unentscheidbar. Liegt es somit in NP-schwer oder in überhaupt einer Komplexitätsklasse?

Für Sprachen von Typ 3 und Typ 2 gilt, dass diese unter Vereinigung abgeschlossen sind. Was gilt dann für Typ 3 vereinigt mit Typ 2?

=> Ist diese Vereinigung dann auch abgeschlossen?

MFG

...zur Frage

Warum ist die folgende Aussage zur Schnittmengen bei Formalen Sprachen falsch?

Mit L1, L2 und L3 seien drei beliebige Sprachen.

Warum ist die folgende Aussage falsch? Siehe das Gegenbeispiel. Bitte es so erklären, dass es auch jemand versteht der nicht Mathematik studiert hat.

Warum kommt links im ersten Bsp. das leere Wort raus und Rechts nicht das leere Wort?

Bitte es so erklären, dass es auch jemand versteht der nicht Mathematik studiert hat.

...zur Frage

formale Sprachen, eine Grammatik aufstellen?

Grammatik für Uhrzeit (HH:MM:SS) aufstellen und welcher Typ

Ich weiß die Stunden können von 00 bis 24 gehen, die Minuten von 00 bis 59 und die Sekunden von 00 bis 59

S -> A

A -> ...

Wie krieg ich das als Grammatik einer formalen Sprache hin?

...zur Frage

Wie kann ich diese kontextfreie Grammatik erzeugen?

Die Kontextfreie Grammatik, die erzeugt werden soll ist: "zwischen zwei a´s liegt immer eine gerade Anzahl von b´s"

Jetzt weiß ich aber nicht, wie das funktionieren soll, denn auch ab oder abbabbaaaa wäre in der Sprache enthalten, wie kann ich a´s spammen aber so, dass zwischen zwei a´s nur gerade Mengen von b. enthalten sind. Ebenso für ba, bbba uns.?

...zur Frage

Zählen von Wörtern in einer Zeichenkette?

Wieso kommt die Falschw Anzahl von dem gesuchtem Wort heraus, wenn ich das Programm ausführe und wie repariere ich das?

Als Beispiel kommt wenn ich als Satz eingebe: du und ich und die welt

Und nach dem Wort 'und' suche 8mal heraus.

...zur Frage

Java short und char binär dargestellt?

Hallo,

wir hatten folgende Klausuraufgabe:

Wie sieht der Bildschirmausdruck

short x;
char c;
System.out.println("x: "+x); 
System.out.println("c: "+c);

aus, wenn die Variablen im Speicher auf folgende binäre Werte gesetzt sind:

x: 1011 0000 1110 1010
c: 0000 0000 0101 1001

Meine herangehensweise wäre für den Char C

0101 1001b -> 59h -> 'Y' (ASCII)

Für den short Wert x ist mir allerdings nicht ganz klar wie das funktioniert. Kann mir hier zufällig jemand helfen?

...zur Frage

Formale Sprachen NFA und DFA?

In der Regel geht man so vor, das man aus einer Sprache L(G) mit einer Grammatik einen NFA(Nichtdeterministischen Automaten) konstruiert. Dann aus dem NFA eine DFA (Deterministischen Automaten) und daraus wieder die Sprache mit Ihrer Grammatik ableitet L(G).

L(G) zu NFA zu DFA zu LG?

Was ich mich jetzt Frage ist, kann man auch anders herum vorgehen, d. h. man aus einer L(G) einen DFA und aus diesem dann einen NFA und daraus leitet man wieder seine Grammatik ab?

Oder ist diese Vorgangsweise um einiges komplizierter als von

LG zu DFA zu NFA zu LG

...zur Frage

Wie erstelle ich diese reguläre Grammatik?

Kann mir jemand bei Aufgabe 8 a) helfen? Ich verstehe nicht, wie ich die Grammatik entwickeln soll. Es sollen Ausdrücke wie 089-KP7 rauskommen, steht ja am Anfang wie, weiß nur nicht wie ich es umsetzen soll. Danke im Voraus.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen