Ich habe eine Email erhalten, in der als Absender I.A. [Name] steht.

Was genau bedeutet I.A.? Heisst das, dass dieser nicht der Verfasser ist?

Wie antworte ich auch die Email?

Wenn ich "Sehr geehrter [Name]," schreibe, ist das dann falsch?

Wie lautet der Überbegriff für Programmiersprachen, Auszeichnungssprachen und Scriptsprachen, gibt es eine Oberkategorie?

+ ? Oberbegriff ?
  ++ Auszeichnungssprache
   +++ HTML
  ++ Programmiersprache
   +++ Java
   +++ C#

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.

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

Meine Lösung:

NFA in DFA umgewandelt

Feedback bitte!

Hey, ich habe folgende Aufgabe:

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

Kann mir da jemand helfen?

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?

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

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!

Nach Satz von Myhill-Nerode

(a) L = {a(b^k)c | k ∈ No} No sind die natürlichen Zahlen mit 0

Warum gibt es hier genau 3 Äquivalenzklassen? Der Suffix Z ist einmal epsi, c und ac.
Soweit ok.

Warum schaut man sich nicht als Suffix z. B. bc, oder bbc, oder bbbc an?

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.

Hallo,

ich wäre sehr dankbar, wenn mir jemand im Teil b) der Aufgabe weiterhelfen könnte:

Meine Lösung a)

 0(1)*(101|01(0)*0)(0*1*)* als regulärer Ausdruck

b) Die Nichtdeterminus Stellen habe ich markiert im NFA

Jetzt soll man noch den NFA in einen DFA überführen. Normal bildet man doch jetzt die PotzenMenge, dies wären 2^7 = 128 Zustände (und arbeitet dort die Verbindungen ab...)

=> Dies kann man doch sicherlich einfacher lösen.

Bitte es so erläutern, dass es auch jemand versteht der nicht Profi in den Formalen Sprachen ist. Danke!

=> Wie sähe der DFA am Ende aus?

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?

Vorab geht um Formale Sprachen - nicht RegEx auf Codebasis

Ich hab folgende Aufgabe:

Für meine Frage ist insbesondere (b) von Interesse. Ich hab da schonmal was aufgeschrieben, bin mir aber nicht sicher ob es richtig ist. Ich habe hier 2 Ansätze, kann aber nicht sagen welcher formal richtig ist. Ich tendiere zum zweiten.

Nicht wundern, (a) steht mit dabei

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?

Ich komme da nicht weiter...

Mein bisheriger Ansatz:

S -> X Y | ε

X -> aaXY | aXbY | XbbY | aa | bb | ab

Y -> XccY | XcYd | XYdd | cc | dd | cd

Dadurch ist aber z.B. X S Y -> bb ε XccY -> bb ε aa cc dd möglich, wobei bb vor aa kommt und das ja nicht geht.

Ich muss ja wegen n+m = s+t das ganze von der Mitte her aufbauen, aber dann schaff ichs nicht, die Reihenfolge und Gleichheit der Anzahl zu halten. (Jetzt passt die Anzahl, weil in der X "Schleife" auch ein Y dazu kommt, aber das zerstört die Reihenfolge. Lass ich das weg, passt die Reihenfolge, aber nicht die Anzahl)

Hat jemand nen Tipp für mich, bitte keine ganze Lösung? :)

Guten Abend,

ich würde meine Texte ganz gern formal schreiben. Dies ist leider nicht möglich, weil mir häufig die richtigen Begriffe nicht einfallen, trotzdem war Deutsch eins meiner Lieblingsfächer.

Ich möchte nicht alle meiner Texte von einer KI schreiben lassen, ich möchte diese selber formal schreiben.

Z.B. brauch ich das für meine Bewerbung, welche aufjedenfall nicht informal klingen darf.

Manche Leute nennen diese Texte auch „wie von Doktoren oder KI‘s geschrieben“.

Hätte jemand Tipps für mich wie man das „erlernen“ kann?

Ich hoffe diese Frage ist verständlich genug formuliert.

LG

Die folgende Grammatik einer Programmiersprache ist in EBNF gegeben:

Übertragen Sie diese Grammatik in die klassische Grammatiknotation. Nehmen Sie verständliche Namen für die Nonterminalsymbole.

Hey Leute, könnt ihr mir bei diesem Übungsbeispiel helfen?

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

Hallo,

ich arbeite gerade das Buch Compiler Engineering von Cooper durch und habe schon mehrere Fragen dazu. Vllt gibt es ja einen ITler, der mir helfen kann.

Im zweiten Kapitel habe ich reguläre Ausdrücke kennengelernt, mit welcher man eine reguläre Sprache beschreiben kann.

Der Scanner erzeugt also Wörter, die an den Parser weitergegeben werden.

Frage 1: Jetzt arbeitet der Parser mit einer regulären Grammatik, um eine Syntaxanalyse durchzuführen. Zu Beginn dachte ich, bei den Terminalen handelt es sich um Wörter aus der Sprache, aber wenn ich es jetzt richig verstehe, sind Terminale Zeichen aus dem Alphabet, über welchem die Sprache gebildet wird.

Wie erzeugt der Parser daraus eine Syntaxprüfung, wenn nicht die Reihenfolge der Wörter, sondern die, der Buchstaben analysiert wird. Sind die Grammatiken denn so komplex, dass die Wortreihenfolge kontrolliert werden kann? Bzw. wieso werden für beide Phasen dann nicht einfach eine Grammatik oder RegExes genutzt, anstatt beides zu definieren?

Frage 2: Ich dachte immer, eine Reg Gram und eine RegEx wären unterschiedliche Dinge. Hier https://de.wikipedia.org/wiki/Regul%C3%A4re_Grammatik#Regul%C3%A4re_Sprachen und im Beitrag unter Regulären Sprachen, wird aber gesagt, dass dies beide äquivalente Konzepte sind.

Was mich daran stört.

Als nicht reguläre Sprache wird häufig die Sprache L = a^n b^n genannt. Mir ist zwar bewusst, dass ich die Sprache nicht durch eine RegEx oder einen Automaten abbilden kann (von denen mir bewusst ist, dass sie äquivalent sind), aber ich könnte doch mit einer Regulären Grammatik bspw. die Ableitungsregel S -> aSb | € (epislon soll das sein :P) erzeugen und hätte damit doch eine Beschreibung für die Sprache.

Wenn RegExes und RegGrams aber äquivalent sind, dann scheine ich ja einen Fehler in der Ableitung zu machen.

Frage 3: Definition Reguläre Sprachen https://de.wikipedia.org/wiki/Regul%C3%A4re_Sprache#Definition

Hier wird beschrieben, dass eine der Bedingungen erfüllt sein muss, damit es sich um eine Reg Sprache handelt. Aber wenn eine Bedingung erfüllt ist, sind nicht gleichzeitig alle Bedingungen erfüllt?

Verwirrt mich alles ziemlich

Gegeben sei die menge A, die alle Wörter mit folgender Eigenschaft sind: Wenn der Buchstabe a im Wort nicht vorkommt , muss mindestens ein b vorkommen.

Die Menge B sei die Menge aller Wörter, wo gilt: Wenn der Buchstabe c mindestens einmal vorkommt, muss auch der Buchstabe b mindestens einmal vorkommen.

Enthält diese Menge A alle Wörter, die auch in B schon enthalten sind oder weniger? Generell sprechen wir nur von Wörter wo a,b und c vorkommt.

Wie viele ÄK (Äquivalenzklassen) gibt es?

[epsi] hier ist es ob ich als Suffix ad oder abcd , oder abcbcd, oder abcbc....d anhänge der Präfix epsi bleibt immer gleich deshalb eine ÄK

[a(bc)*d] Hier stehen lauter Wörter in der KLasse an denen ich epsi anhänge und es liegt ein Wort der Klasse vor.

Soweit klar!

Schauen wir uns mal die beiden Aufschriebe in rosa an. Wie man sieht, sind die Präfixe in den beiden Klassen gleich, aber die Suffix die man anhängt sind hinten verschieden:
Oben (rosa) hängt man bcd an

unten (rosa) hängt man d an.
D .h. wieder , wenn die Präfixe einer Klasse gleich sind und die Suffixe sind verschieden, dann kann man eine Klasse streichen?

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.

L1 ist Deutsch

L2 ist Englisch

L3 ist Spanisch

Drei Formale Sprachen:

Wie geht man hier jetzt vor?

(L1 v L2) L3
L1 = { Fußball, Mutter, Esel}

L2 = {want, will, good}

L3 = {Hola, Dinero}

d. h. für mich (L1 v L2) ist die Menge {Fußball, Mutter, Esel, want, will, good}

(L1 v L2)L3 => ? Was kommt jetzt hier raus?

Ist das (L1 v L2)L3, das selbe wie (L1 v L2) * L3,

d. h. die Menge (L1 v L2) geschnitten mit L3?