Ein Eisenbahnzug besteht aus einer Reihe verschiedener Wagons. Er beginnt mit mindestens einer oder auch mehreren Lokomotiven, welche dann von null oder mehreren Guterwagons gefolgt werden. Nach diesen kann optional ein Begleitwagen kommen oder sofort eine Reihe von einem oder mehreren Personenwagons. Sind Personenwagons vorhanden, werden diese jedenfalls von einem Begleitwagen abgeschlossen. Beschreiben Sie diese Folge in Form einer Wirth’schen EBNF. Sie können folgendes Alphabet benutzen:

Σ = {Locomotive, GoodsTruck, PassengerCoach, GuardsVan}. GuardsVan bedeutet Begleitwagen. Sie können Σ aber auch erweitern, falls dies notwendig sein sollte

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?

Ist nicht jede Sprache eine reguläre Sprache?

Man kann doch einfach folgenden DFA konstruieren:

Startzustand gleichzeitig akzeptierter Zustand, Übergangsfunktion verweist für jede Eingabe auf den Startzustand. Ist das denn nicht etwas witzlos?

Entwickeln Sie einen deterministischen endlichen Automaten, der die Sprache aller Wörter über {0,1}*

beschreibt, welche mit dem Teilwort „10“ enden.

Ist dieser dea richtig?

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?

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

Wie gibt man die Sprache von der grammatik an , ich komme irgendwie nicht weiter und kann mir jemand sagen wie das geht ?

Also für alle, die nicht wissen, was es ist, es ist eines der Millenium Probleme, welches noch nicht gelöst wurde.

Kurze Zusammenfassung der Frage des P-NP Problems:

Bedeutet die Fähigkeit, korrekte Antworten schnell zu erkennen (NP) auch, dass es eine schnelle Möglichkeit gibt, diese Antworten zu finden (P)?

Beispiel:

Man hate einen Zauberwürfel mit auf jeder Seite hunderten Feldern, sobald er "gelöst" wird, kann man schnell erkennen, ob er richtig oder falsch gelöst wurde, allerdings würde man (nach dem heutigen Wissensstand) nahezu ewig brauchen, um ihn überhaupt lösen zu können, die Frage ist da halt: gibt es eine Möglichkeit, ihn schnell lösen zu können, da man ja auch schnell sehen kann, ob er richtig oder falsch gelöst ist.

Meine "Lösung" (als Gedankenexperiment; noch nicht rechnerisch nachgewiesen):

Man will ein Passwort hacken, weshalb man einen Algorithmus schreibt, welcher die Passwörter einzeln durchgeht (Problem in NP). Da wird ja schnell erkannt, ob ein Passwort richtig oder falsch ist (dadurch, dass man dann eingeloggt ist oder eben nicht), allerdings gibt es keine Möglichkeit, es anders herauszufinden, da es eben einfach keinen anderen Lösungsweg gibt. Also gibt es auch keinen schnelleren Lösungsweg, weshalb nur an diesem Beispiel theoretisch nachgewiesen wäre, dass P≠NP ist oder?

Ich würde mich über sachliche Antworten sehr freuen, mir ist bewusst, dass meine Antwort vermutlich viel zu einfach ist, damit sie als Lösung gesehen werden könnte und das andere Leute diese Idee vermutlich auch schon hatten. Mich würden nur eure Gedanken dazu interessieren!

Hallo, kann mir jemand bei der Aufgabe helfen? Ich verstehe gar nichts.

Die Aufgabe b)

Vielen Dank schonmal in vorraus.

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.

Ich schreibe bald eine Klausur in Digitaltechnik und weiß nicht genau, was in der Lösung gemacht wurde.

Was ich verstehe:

• Ich verstehe den Sachverhalt und:
• Zum Automaten wurde ein endlicher Automat erstellt.
• Es gibt drei Zustände und zwei Ausgänge. Anschließend wurde eine Wahrheitstabelle erstellt.

Was ich nicht verstehe:

• Wie die Eingänge im Automaten zustande kommen
• Wie man die Wahrheitstabelle erstellt hat
• Was bedeutet ,,alt" und ,,neu" in dem Kontext?
• Wie kommt die Anordnung der 0en und 1en in der Tabelle zustande?
• Wieso wurden nur die MIN-Terme der ,,neuen" Zustände hergeleitet?

kann mir jemand bei meiner Informatik Hausaufgabe helfen?

nummer 3 a und d

e { ω ∈ {0, 1, 2}∗ | ω = 1^n 0^2n+m 2 0^m - mit n ≥ 0 ∧ m > 0 }

Beschreiben Sie die Menge  durch eine angemessene Grammatik. Um welche Art von Grammatik handelt es sich bei Ihrer Lösung?

Mein Ansatz war:

S -> 1S00 | A

A -> 100B

B-> 2 | 0B0

Servus,

ich verstehe einfach nicht, wie ich mir die Berechnung der O-Notation von folgender "Funktion" erschließen kann:

Ich schätz mal O(1) ist der "y := x" Teil. Aber alles danach versteh ich einfach nicht xD

Wäre nett, wenn ich mir jemand weiterhelfen können.

Danke im Voraus!

Ich bin ehrlich gesagt, noch etwas verwirrt, wie das mit Myhill Neurode und diesen Äquivalenzklassen funktioniert.

Eine Sprache L besteht aus ab^k k ist element der Natürlichen Zahlen, von 0 bis n

Wie viele Äquivalenzklassen nach Myhill Neurode gibt es jetzt hier? Die Implizite Fehler Äquivalenzklasse lassen wir weg.

Wie geht man vor:
Erstmal, was sind gültige Wörter der Sprache

a, ab, abb, abbb, abbbb....

In{ } stehen die Wörter, dahinter die Präfixe

{a, ab, abb, abbb, abbbb...} Präfix b

Das selbe wäre möglich für

{a, ab, abb, abbb, abbbb..} Präfix epsilon

{a, ab, abb, abbb, abbbb..} Präfix bb

Wie man sieht stehen in jedem Klammerpaar {....} die selben Wörter.

=> Gibt es jetzt nur "eine" Äquivalenzklasse?

=> Was ist wieder mit epsilon? Bildet dies eine eigene Äquivalenzklasse?

{ epsi} als Präfix a

{epsi} als Präfix ab

{espi} als Präfix abb

...

Gibt es jetzt hier für ab^k eine eigene epsilon Äquivalenzklasse oder gibt es sie nicht?

Ich bin hier ehrlich gesagt ziemlich verwirrt, da ich keine klare Struktur erkenne, wann ich eine eigene epsilon Äquivalenzklasse brauche und wann nicht.

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!

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?

Ich welcher Komplexitätsklasse P, NP, NP-vollständig, NP-schwer

liegt die: Absolute Differenz zweier Zahlen: absdiff(x, y) = |x − y|

Es handelt sich hier um eine primitive Rekursion, welche auch loop Berechenbar ist.

Somit müsste dies auf jedenfall in der Komplexitätsklasse P liegen.

Wenn man nun davon ausgeht, dass P ist Teilemenge von NP gilt, dann müsste die absolute Differenz in P und NP liegen.

MFG

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

a)

L2 ist vom Typ 1

L3 ist vom Typ 2

L1 ?

b) Man könnte zu L1 eine reguläre Grammatik angeben, z. B.

S -> aA |aS

A -> bC

C -> cC | cD

D -> d

Wie man sieht ist die Grammatik zur Sprache L1 regulär Typ 3.

Wenn man aber an dann z. B. an das Pumping Lemma für Typ 3 Sprachen denkt, dann kann man ja nur eine Stelle Pumpen. Womit das Pumping Lemma zeigen würde, das die Sprache nicht von Typ 3 bzw. regulär ist.

Welchen Typ hat L1 jetzt in der Chomsky-Hierarchie?

Das Wortproblem Typ 1 für kontextsensitive Sprachen ist entscheidbar.

Bzgl. der Komplexität ist es NP-schwierig.

O(k^n) Komplexität

Laut der Folie kann man nicht zeigen, dass es in NP liegt. Es ist NP-schwierig.

Nun meine Frage: Ist das Wortproblem Typ 1 Turing-Maschinen berechenbar? Ja oder Nein, wenn es wie hier angegeben NP-schwierig ist?
Es gilt P Teilmenge von NP.

Es geht um Modul: Theoretische Informatik. Ich lerne gerade für die Klausur. Ist es so richtig? Leider habe ich keine Lösung dazu, deswegen bin ich mir unsicher.. Danke im voraus ❤

Ist nicht der vorletzte Teil AddOffset falsch? Weil warum geht es von Reg aus und dann wird s1 auf hilfsregister output umgeschaltet. Sollte doch eingang d ins hilfsregister reingehen und nicht ins reg.

Ich verstehe die Rechnung aber was wenn das Codewert mit 1 endet anstatt mit 0, am Ende wird ja dann eine 1 runtergezogen anstatt die 0. Hieße das das der Codewort falsch ist?

stimmt die aufgabe was er gemacht hat wo er am ende 2,75 bekommen hat?

Kann mir ma jemand erklären, wie man hier vorgeht?

Der Kellerautomat soll in Greibach-Normalform überführt werden:

a) Hat der Kellerautomat hier nur einen Zustand?
Was bedeutet das umgedrehte kleine e? Der Übergang(z, a, S) enthält ...(z, ...)?
Übergang(z, a, S) ∋ (z, SBB)

∋ (z, ASB)

∋(z, BB)

∋(z,AB)

Übergang(z,a,A) ∋ (z, epsi)

Man liest im Zustand z ein a, im Keller steht ein großes A, so ließt man dieses große A aus dem Keller aus/weg.

Übergang(z,b,B) ∋ (z, epsi)

Selbe Erklärung nur, das man hier ein B aus dem Keller wegliest.

b) Das Wort aaabbb soll verarbeitet werden.

Kann man hier jemand mal die ersten drei Zeilen erklären. Ich lese ein a aus dem Wort

(z,a,S) -> aSB im Keller steht SBB ??? Was passiert hier?

Ich lese das zweite A aus dem Wort

(z,a,S) -> AB im Keller steht jetzt ABBB?

Wenn bei der Zerlegung x y z das |y| > 0 sein soll. warum darf man dann bei einem Beweis von L = {a^n b^n | n>= 0} und einem ansatz von a^p b^p wobei p = die anzahl der Zustände ist, x y^0 z wählen?

Ich mein wenn |y| nicht 0 betragen darf warum darf ich dann y^0 setzen? Ist doch ein wiederspruch oder?

Wie wähle ich bei den drei Sprachen am besten mein n für die Vorgabe

|x| >= n sein?

Bei c kürzestes Wort mit k = 0 ist epsilon. Mit Pumpen 2k Länge

Demensprechend würde ich mein n = 2k sätzen

a) und b) wie setze ich hier mein n? Ich will ja "generell" zeigen, das sich das PL erfüllt für alle v^i, wenn ich Pumpe. Oder eben nicht erfüllt, und damit die Sprache nicht regulär ist.

Programm stoppt immer beim Pluszeichen. Warum? Habe den Code vorher angepasst, so dass die beiden Zahlen addiert werden.

Gebe in den Simulator 110+10 ein. Load, start

name: Addierer
init: z0
accept: zE

// Fahre nach ganz rechts auf der ersten Zahl
z0,0
z0,0,>

z0,1
z0,1,>

z0,_
z0,_,>

z0,+
z0,+,>

// Suche das Ende der zweiten Zahl
z0,-
z1,-,<

// Addiere 1
z1,0
z2,1,<

z1,1
z1,0,<

z1,_
zE,1,-

// Fahre nach ganz links und beende
z2,0
z2,0,<

z2,1
z2,1,<

z2,_
zE,_,>

z2,+  // Falls ein '+' gefunden wird, bewege nach rechts, da es bereits verarbeitet wurde
z2,+,>

Wie kommt man hier darauf, das für x = 1 -> y + 2 zurückgegeben wird?

Wenn x = 1 ist, gehe ich in return ackermann(1-1, ackermann(1, y-1));

=> Wird jetzt hier zuerst die innere ackerman(x, y-1 ausgeführt)
oder die äußere ackermann(x-1, ackermann(x, y-1))?

A --> Ba (linksreguläre Grammatik)

A --> aB (rechtsreguläre Grammatik)

Wieso ist " a " nichtterminal?
Wieso ist das Erste links- und das Zweite rechtsregulär?

a* a|b ab sind reguläre Ausdrücke. Hier die Aufgabe:

Wie geht man bei a) sowie b) am besten vor? Um den regulären Ausdruck zu erzeugen?

Woran erkenne ich an diesem Kellerautomaten den Nichtdeterminismus?

a;A -> AA und epsi;A -> A ? Wenn ja, warum?

m >= 1, d. h. das kürzeste Wort in der Sprache hat die Länge 3m bzw.

|z| = 3n > = n

D. h. wenn mein n = 1 ist, dann hat mein Wort die Länge 3.

Jetzt muss ich eine Aufteilung von |vwx| wählen, dass gilt |vwx| <= n

und dann beim pumpen das Wort Teil meiner Sprache bleibt.

|vwx| <= 1 geht nicht. Macht keinen Sinn, ich muss ja a und b und c einzeln pumpen. a,b,c hat mindestens die Länge 3. Somit macht n = 1 keinen Sinn. n = 2 geht auch nicht. Ich muss mindestens n = 3 wählen. Also z = aaabbbccc nun muss ich |vwx| <= 3 wählen, d. h. ich kann nur 2 von den 3 Symbolen (einzeln) pumpen. ab und c oder a und bc , das macht keinen Sinn.

Fazit:

Man müsste a b c separat (einzeln) pumpen, damit das erzeugte Wort Teil meiner Sprache bleibt, dies ist hier aber nicht möglich egal wie man v und x wählt.

Langt dies als Begründung, oder wie argumentiert man hier am besten?

|z| = 2n >=n das kürzeste Wort hat die Länge 2 somit hat auch mein n mindestens die Länge 2.

Wieder muss ich |vwx| so wählen, dass gilt |vwx| <n und beim pumpen dann das Wort Teil meiner Sprache bleibt.

Wie wähle ich nun hier u, v, w, x, y?

https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/
Wie gibt man hier ein | ein. Bei mir wird dies immer wieder entfernt.

• [ | ] - For "or", use the standard pipe character that you use while coding.

Möchte S -> A | B eingeben der Pipe character geht bei der Eingabe nicht.

In der Realität will man doch eh immer nur Kryptocoins von A nach B senden. Was bringt es also, dass z.B. Ethereum turingvollständig ist?

Pumping Lema für kontextfreie Sprachen Typ 2.

Das Wort z lässt sich in uvwxy zerlegen und |z| >= n

Untere Grafik:

=> Eine Variable muss doppelt vorkommen. Klar!

=> Unteres A wird vom oberen A abgeleitet. Klar!

|vx| darf nicht leer sein => Vorgegeben. A -> AB über ok.

Fragen:

=> Warum teilt sich A immer "genau" in vwx auf? Warum nicht in uvw oder wxy?

Wenn ich pumpe wächst mein v und mein x. d. h.

uv^iwx^iy

Nehmen wir ich habe das Wort z = abababab d. h. n = 8

=> Wie soll man jetzt hier uvwxy wählen um zu zeigen, dass das Wort das PL erfüllt oder nicht. Wie geht man hier am besten vor. Mir ist dies ehrlich gesagt nicht verständlich, wie ich hier vorgehen soll.

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?

Hi,
kann uns jemand hier erklären, wie man bestimmt welche Flags zu welchen Signalen gehören?
Wir haben im Netz rechachiert, was die Flags machen, aber können es trotzdem nicht richtig zuteilen, weil wir nicht wissen, wie man richtig vorgeht..

LG und vielen Dank!

rechts sind die Möglichkeiten, die man in der Box hinzufügen kann

bei f bin ich mir nicht sicher.
hier sind meine Notizen, falls das hilft:

Vielen Dank im Vorraus!

Meine Lösung:

NFA in DFA umgewandelt

Feedback bitte!

Beim Pumping Lemma:

Das angeblich reguläre Wort wird in w = xyz zerlegt, dabei muss gemäß der ersten Bedingung |y| > 0 sein.

für alle i = 0,1,2... muss gelten W = xy^iz ist Element der Sprache L

y^i wird aufgepumpt.

Wenn man jetzt y^0 setzt, d. h. i = 0, kommt w = xz heraus. Klar soweit!

Allerdings, wenn y^0 = epsilon ist, das leere Wort,

dann wäre dies doch ein Widerspruch zur Bedingung |y| > 0 ???

Ich soll einen Keller Automaten zur folgenden Sprache erstellen

L={a^3nb^2n | n>=0}

Ich weiß ehrlich gesagt nicht, wie dieser Automat aufgebaut ist. Ich soll ein Diagramm erstellen. Ich weiß allerdings nicht wie das für ein Kellerautomat für dieses Sprache geht

Alphabet sigma = {0, 1}

Für d) L4 beinhaltet doch alle Wörter über sigma oder?

Für c) Die Wörter in L2 werden ja aus dreier Blöcke gebildet (sigma^3)

Wenn L3= sigma* \ L2 gilt sollte doch Wörter der Länge != 3n , die 101 als Teilwort enthalten, auch in L3 liegen. Dann gilt aber L3 = L2^c. Welcher ist richtig?

Das Pumping Lemma ist hier erfüllt. Es soll sich hier um eine kontrexfreie Sprache vom Typ 2 handeln. Woran erkenn ich dies?

Die Sprache ist nicht regulär, dies kann man über das Pumping Lema zeigen.

Soweit konnte ich dies nachvollziehen, allerdings:

Generell setzt man ja n = k.

wenn i = 0 ist gilt uw = a^(k - |v|)b^k

Warum ist dies jetzt nicht Teil meiner Sprache? Wenn ich nichts Pumpe und n = k z. B. n = 1 dann steht doch hier ab, was Teil meiner Sprache ist?

Wie kommt man auf den generellen Ansatz uw = a^(k - |v|) b^k ???

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

falls das eine dumme frage ist, entschuldige ich mich im voraus!

Hier sei eine angeblich "einfache" Aufgabe, einen NEA zu erstellen, doch ich verzweifle:

Dritter Punkt. Was bedeutet das "mal". Der Dozent hat leider auch nicht mehr geschafft als g_1 mal irgendwas zu lesen, die Bedeutung ist mir nicht klar.

O(g_2) ist eine Menge, g_1 irgendeine Funktion, wie üblich eben. Was heißt es denn wenn eine Funktion mit einer Menge multipliziert wird?

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

L1, L2 und L3 sind Sprachen

Warum ist links das Element ab mit drinnen und rechts ist ab nicht mit drinnen?

Der * bedeutet, das hier auch das leere Wort mit drinnen liegt.

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.

Ich hab mal so eine Frage bzgl. Algorithmen und Datenstrukturen. In unserer Übung sollen wir beurteilen, ob ein Kochbuch ein Algorithmus wäre und dabei bin ich während einer Recherche ins grübeln gekommen.

Erstmal ist natürlich klar, dass ein Algorithmus eine endliche Abfolge von genau definierten Anweisungen zur Behebung eines Problems ist. Nun muss man bei einem Kochbuch bedenken, dass Anweisungen wie "Eine Prise Salz" nicht genau definiert sind und auch bei der Durchführung es unterschiedliche Resultate geben würde, z.B auf Grund verschiedener Backöfen, Kochtöpfe etc. was der Definition eines Algorithmus widersprechen würde. Wenn man wiederum die Umgebung digital simulieren würde, wäre das Resultat immer identisch.

Daher wollte ich euch mal fragen, wie ihr darüber denkt und ob ein Kochbuch ein Algorithmus wäre oder nicht

Ich stehe vor folgender Aufgabe

L1=(a^nb^m | n>=0, m>=1)

L=(a,bab)

1. Erstellen Sie für die Sprache L1 und L2 sowie für die Sprache L3= L1 U L2 jeweils einen endlich Automaten

2. Geben Sie die vollständige Grammatik für L1/L2/L3 an

Ich weiß, was ein DEA ist und wie er aufgebaut ist. Ich weiß ebenfalls, wie eine Grammatik aufgebaut ist

G=( V,T,P,S)

Allerding weiß ich nicht, wie ich nun von diesen Sprachen ein DEA erstellen soll. Ich weiß auch nicht, was hier die Vereinigung verwirkt und wie ich in Aufgabe 2 auf die Gesamte Grammatik (V,T,P,S) kommen soll. Vor allem verstehe ich nicht, wie ich auf P kommen soll.

Ich bräuchte, wenn's geht, eine verständliche Schritt für Schritt Erklärung. Vielen Vielen Dank schon Mal!!

Wie löst man die obige Aufgabe. Habe mir jetzt ein paar Videos zum Thema angeschaut und kann ein paar Algorithmen analysieren. Bei obigem komme ich aber nicht weiter.

Beim ersten Algorithmus muss ich die Multiplikation ja jedes mal durchführen, während beim zweiten nur ein einziges mal am Ende multipliziert wird. Daher hätte ich gesagt:

1. Algorithmus O(n), da ich die Multiplikation jedes mal durchführen muss
2. Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Meine Fragen:

1. Ist die Analyse korrekt?
2. Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?
3. Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

Ziel: 1 Token in S7

Wahr oder Falsch: Sei Σ = {0, 1} und sei L ⊆ Σ∗ regulär. Sei L′ die Sprache, die man aus L erhält, indem man in jedem Wort aus L jedes zweite Vorkommen von 0 durch 10, und jedes dritte Vorkommen von 1 durch 01 ersetzt. Dann ist L′ regulär. Begründen Sie Ihre Antwort.

ich soll mit Pumping-Lemma beweisen, dass die folgende Sprache nicht regulär ist: L={0^m1^n|n!=m}

ist mein ansatz richtig so? :

sei n element N,

sei k >= 1 und setze w = 0^n1^(n-k) mit w element L und |w|>=n,

zerlegung w = xyz mit |xy|<=n und y nicht leer,

dann xy= 0^p mit p<=n, y=0^k mit k>=1,

setze i=0 --> xy^0z=0^(n-k)1^(n-k)

somit ist xy^0z nicht in L und L nicht regulär

Könnte mir jemand dazu die Fragen beantworten, die ich in dem Bild gestellt habe?

Hi, ich verstehe den Sinn hinter dem Pumping Lemma nicht. Es soll ja dazu benuzt werden um zu zeigen das eine Sprache die eine Wortlänge größer oder gleich n ist nicht regulär ist.

Aber man kann mittels des Pumping Lemmas auch sehr häufig Sprachen die nicht regulär sind mittels Pumping Lemma als akzeptierte Sprache darstellen. Und andersrum kann man auch Sprachen die regulär sind sehr häufig als irregulär darstellen.

Das Pumping Lemma ist ja dann fast komplett nutzlos oder verstehe ich da etwas falsch?

Hallo Leute,

ich frage mich, ob diese Sprache kontextfrei ist oder nicht. Wenn nicht, wie würde denn der Pumping Lemma Beweis dafür aussehen?

Vielen Dank im Voraus

Ist

L = {bin(3m) | m ∈ Element aller natuerlichen Zahlem mit 0}

eine regulaere Sprache?

Wenn ich das Pumping Lemma anwende fuer das Wort 11011 und

u = 1101

v = 1

w = leere Menge

und ich v mit 6 pumpe kommt 1101111111 raus was keine vielfache von 3 ist. In meinem Loesungsbuch steht jedoch das es sich um eine regulaere Menge handelt. Was mach ich falsch oder ist das richtig was ich gemacht habe?

Kann mir bitte Jemand weiterhelfen, diesen NFA/NEA zu konstruieren?

Mit "alle drei" Automaten sind jeweils der Automat von [0-9], [0-9]* und [0-9][0-9]* gemeint.

Für [0-9] habe ich den Automaten:

-->(q0)----[0-9]---->((q2))

Für die restlichen beiden habe ich auch eine Lösung, jedoch wurde mir gesagt, dass wir Epsilon bzw. Lambda nicht benutzen dürfen.

Ich verstehe jedoch nicht wie ich dann 5 Zustände und 6 Kanten erreichen soll beim finalen Automat.

0 und 1 wird kodiert zu

000 und 111

Das sind unsere Codewörter. Die Hamming Distanz ist 3.

Jedem dieser Codewörter wird nun ein Fehlercodewort zugeordnet, das sich in einem Bit unterscheidet, also 001, 010, 100 gehören zu 000 und kann korrigiert werden. Bei 111 analog vorgehen.

Da die Hamming Distanz 3 ist, kann 1 Bit Fehler korrigiert werden. Aber anscheinend können 2 Bit Fehler erkannt werden, warum?

000 wird zu 011 (zwei Bit Fehler) und das wird korrigiert zu 111 (ist dem eben am ähnlichsten)... Damit ist die Korrektur falsch und Hamming, liefert meiner Meinung Schwachsinn...

Hey, wenn ich eine Grammatik habe die eine Rekursion enthält also zB :

G:

S -> SS

S -> a

dann ist L(G) ja eine unendliche menge, das ist mir klar.

Aber gibt es ein wort in L(G) das unendliche Länge hat ?

Meine erste Intention war, ja gibt es man braucht nur eine unendlich lange derivation.

Mein zweiter Gedanke war das L(G) ja so definiert ist: L(G) = {w in Sigma* | S =>* w }

und wenn ich jetzt sage es gibt ein unendlich langes wort dann muss es ja trotzdem diese derivation S =>* w geben und wenn ich die jetzt so veränder das ich einmal mehr S->SS anwende dann habe ich ein neues wort das länger wie w ist. Und somit kann w nicht unendlich lang sein ?

Welcher Gedanke stimmt ? Danke :)

Hallo, ich hänge an der Aufgabe 9, ich weiß nicht wie ich weiter kommen soll. Hat jemand eine Idee oder einen Lösungsvorschlag?

danke im Voraus!

Frage steht oben.

Ich suche konkret nach der Begründung für die Obergrenze.

Wie könnte man das effizient lösen?

Der O(n²) Algorithmus ist ja offensichtlich, aber wie geht's in O(n * log(n))?

Das Konzept alleine würde mir schon reichen. Oder ein Stichwort, zu welchem ich recherchieren kann. Ich überlege seit Stunden, aber komme einfach nicht drauf.

Sigma * ist ja in der Theoretischen Informatik die Kleenesche Hülle. Was ist dann Sigma+ ?

Hallo alle zusammen,

ist es egal, wo was n und m steht? Also bei welchem Attribut?

Beispielsweise habe ich die Attribute Mitarbeiter und Projekt... steht das n oder das m bei Projekt und was bei Mitarbeiter?

Dankeschön!!

Zb gegeben sei das Alphabet {a, b}. Man soll einen regulären Ausdruck angeben aller Wörter über das Alphabet wo nicht bab vorkommt. Wie geht man da vor?

Hier ist mein Ansatz. Ich bilde eine Typ-2 Grammatik zu dieser Sprache. Es gilt, dass zu jeder Typ-2 Grammatik eine Typ-2 Grammatik in CNF existiert. Wäre das ein Ansatz um zu zeigen, dass eine Sprache vom Typ-2 ist?

Gibt es noch andere Möglichkeiten? Ich könnte theoretisch auch einen PDA aufzeichnen oder?

Guten Abend,

ich bin bei meiner Klausurvorbereitung auf folgende Aufgabe gestoßen:

Gegeben ist die Sprache 𝐿, die durch den regulären Ausdruck 𝑝(𝑖|𝑎) (𝑝(𝑖|𝑎))∗𝑝𝑜 erzeugt wird.

Geben Sie den Übergangsgraphen eines deterministischen endlichen Automaten (DEA) an, der die Sprache 𝐿 akzeptiert. 

Dafür habe ich folgendes entworfen.

Meine Frage ist nun, was ich an den roten Fragezeichen hinschreiben kann. Es kann kein p sein, da es kein DEA mehr wäre. Wie würdet ihr es lösen?

Danke

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?

Das Marienkäfer namens Kara soll verschiedene Baumstämme mit Kleeblättern ausfüllen. Hierfür soll ich einen Algorithmus entwickeln aber ich habe keine Idee wie. Hat jemand vielleicht einen Plan? Die Aufgabe ist aus der 10. Klasse Informatik Grundkurs

Hallo,

ein paar kurze Fragen die ich nicht richtig verstehe:

wie viele terminale und nichtterminale dürfen bei den Formalen übergangsfunktionen auf der rechten Seite vom Pfeil stehen?(links darf immer nur eine nichtterminale stehen?)

reguläre Ausdrücke sind einfach nur eine andere Form von regulären Sprachen? (Wenn nicht, worin unterscheiden sie sich?)

müssen formale Sprachen jedes akzeptierte Wort berücksichtigen oder kann eine sprache auch einfach eine teilmenge aller akzeptierter Wörter sein?

danke für alle hilfreichen Antworten

Ich wäre sehr dankbar, wenn mir jemand behilflich sein könnte. Außerdem weiß ich nicht wie ich m ungleich n graphisch darstellen kann..

Lg

Hallo, es geht um theoretische Informatik.

Meine Frage ist, wo liegt der Unterschied zwischen formaler und akzeptierter Sprache? Formale Sprache ist eine Menge von Wörtern, welche sich aus den, im Alphabet befindenden Zeichen zusammensetzen lassen. Akzeptierte Sprache, bzw. L(A) ist eine Menge der akzeptierten Wörter, welche vom Startzustand aus auf einem akzeptierten Zustand enden.

Keine der beiden Mengen muss alle Wörter beinhalten.

Wenn ich eines oder vielleicht sogar beide der Begriffe falsch verstanden habe, dann klärt mich bitte auf und sagt mir, ob es sich bei den beiden Begriffen, um das Gleiche handelt, oder ob eine Grundlegend anders ist als das andere.

Hallo, ist die Kleenesche Hülle eine Menge, oder nicht?

Oder, ist sie nur ein Operator, der auf irgend eine Menge L (von mir aus) angewendet wird, und daraus die neue Menge L* entsteht ?

Hallo, ich hab die O-Notation schon so mehr oder weniger verstanden, also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.

Was ich aber nicht verstehe, wie man das bei mathematischen Ausdrücken zeigen soll. Z.B.:

Was ich mir vorstellen könnte wäre, dass n die Eingabe entspricht und der Funktionswert der dann rauskommt gleich der Eingabe hoch vier entsprechen muss (ist hier ja aber nicht der Fall).

Moin, ich wüsste gerne, ob das hier richtig ist und wenn nein, was könnte ich besser machen?

Hey, Ich verstehe nicht wie ich folgende Aussagen durch ein Beweiser-Gegenspieler Argument begründen soll.

Hallo,

ich habe vor kurzen über die O Notation eines Algorithmus gelernt und da gibt es die O Notation O(log(n)) und da habe ich mich gefragt welche Sortieralgorythmen haben diese O Notation. Nach Recherche habe ich leider nichts gefunden. Kann mir da wer weiterhelfen?

Kann mir bitte jemand bei meinen Hausaufgaben helfen? Ich kann das alleine nicht :(

"Negieren Sie folgende Aussage formal (De Morgansche Regeln):

((x>14 ^ x<20) v (x>21 ^ x ≤34))

In Ihrem Ergebnis sollen nur mehr die logischen Operatoren UND (^) & OR (v) vorkommen (keine Negation!)"

Dieser Algorithmus läuft ja immer linear, warum insertionsort nicht, der ja auch eigentlich nur Vergleiche vollzieht?:

Lösung n-1 vergleiche überall,

Aufgabe:

Mein Problem hierbei ist, ich verstehe nicht, warum die zyklische Wartebedingung aufgehoben wurde. Es gibt ja immer noch Prozesse die die gleiche Gabel wollen und warten müssen, wenn einer die zuerst erhalten hat? Dadurch habe ich doch zyklisches warten?

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?

Hi, kann mir wer erklären wie genau der Diagonalisierungsbeweis funktioniert, verstehe diesen noch nicht ganz:

Also, ich verstehe nicht ganz warum dies am Ende ein Widerspruch ist dann. Ist es so gemeint, dass wir ja anfangs mit der Turingmaschine R die Diagonale definiert haben und dann mit D die R nutzt , grad das Gegenteil auf dieser Diagonalen stehen muss, was ja nicht gehen kann?

Gruß

Liebes Community,

kann mir bitte jemand erklären, was semi entscheidbar ist? Ich habe den unterschied mit unentscheidbar leider nicht ganz begriffen. Vielen Dank!

Hallo, ich bin auf eine schwierige Aufgabe bezüglich des Pumping Lemmas für reguläre Sprachen gestoßen und ich komme nicht weiter bei der Zerlegung eines Wortes s in xyz. Es handelt sich um die Sprache L = {a^n b^m c b^m a | n, m aus den natürlichen Zahlen}.

Ich hatte als s ursprünglich a b^p c b^p a gewählt, aber ich verstehe nicht, wie man hieraus einen Widerspruch formen kann, denn wenn sich y bloß aus a's zusammensetzt, wird das Pumping Lemma hier ja erfüllt.

Danke im Voraus!

Hi, also ich verstehe bei dieser Aufgabe in der Lösung den letzten Schritt im Induktions Schritt nicht so ganz:

Gruß

Auch wenn Duolingo nicht die effizienteste Methode ist, zu lernen, so ist es durch die Gamifizierung schon verdammt effektiv.

Mein Problem ist, dass mein ADHS Hirn so ein System wie Duolingo braucht, um länger als 5 Minuten am Ball zu bleiben.

Gibt es sowas auch für Informatik?

(also für Analysis, Theoretische Informatik etc. auf Studiumniveau)

vielen dank im Voraus! : )

Guten Abend,

ich würde gerne Informatik studieren an einer Hochschule, da der Matheanteil dort geringer ist und mehr Wert auf Programmieren gelegt wird.

Hier sind alle Module der Hochschule, ist der Matheanteil an dieser HS wirklich gering? Ich sehe nur drei Mathe-Module und der Rest scheint hauptsächlich IT zu sein. Ich habe im Mathe LK immer zwischen 10-13 Punkten bekommen aber Analysis, Algebra und Stochastik haben mir relativ viel Spaß gemacht.

Zudem frage ich mich was mit "Grundlagen der Informatik" oder "Theoretische Informatik" gemeint ist, könnte mir das jemand erläutern?