Was heißt es:

man kann jedes Problem in P auf jedes andere Problem in P reduzieren

?

Angenommen als Beispiel:

• L1 ist die Entscheidung, ob eine Zahl z1 gerade ist
• L2 ist die Entscheidung ob eine Zahl z2 prim ist

Ich kann nun spaßhalber eine Reduktion von L1 -> L2 machen, indem ich

zuest L1(z1) löse und wenn das Ergebnis

• ja ergibt, füttere ich L2 mit dem Input 3
• nein ergibt, füttere ich L2 mit dem Input 6

Dann habe ich L1 in Polyzeit auf L2 reduziert: man schreibt



bzw. man sagt

" L2 ist mindestens so schwierig wie L1"

Ich könnte aber auch umgekehrt eine Reduktion von L2 -> L1 machen, indem ich

zuest L2(z2) löse (wie auch immer, aber eben in Polyzeit) und wenn das Ergebnis

• ja ergibt, füttere ich L1 mit dem Input 2
• nein ergibt, füttere ich L1 mit dem Input 1

Dann würde ich schreiben können:



bzw. sagen

L1 ist mindestens so schwierig wie L2"

Das würde bedeuten, dass P1 und P2 gleich schwierig sind, was aber klarerweise nicht der Fall ist. Hab ich da was falsch verstanden?

Wie ist das also diese Notation zu interpretrieren?? Irgendwas stimmt doch hier nicht...wo bin ich falsch abgebogen?

Die Turing-Maschine ist scheinbar ein wichtiges Konzept in der theoretischen Informatik. Ich selbst bin ein kompletter Laie in der Informatik, habe aber in anderen Zusammenhängen immer wieder davon gehört. Bisher habe ich aber nie verstanden, wozu man das Konzept einer "nicht-deterministischen Turing Maschine" (NTM) benötigt: Soweit ich laienhaft verstanden habe, tut man so, als könne diese NTM Ergebnisse für eine Eingabe quasi erraten (Orakel) und dann schnell auf Akzeptanz prüfen. Was meint man hier mit erraten? Wo ist der konzeptionelle Unterschied zu deterministischedn TMs? Auch dort kann ich ja auf beliebig viele Berechnungspfade aufspalten (Speicher ist ja unbegrenzt) und quasi "parallel" rechnen. Es geht ja bei NTM nicht darum wie effizient diese sind - aber dann verstehe ich nicht, was daran so interessant ist.

Kann mir jemand ein konkretes Beispiel liefern, sodass ich den Vorteil des Konzepts erkennen kann?

Wieso ist hier die Hamming Distanz d = 1, wenn 0001 und 0010 doch eine HD von 2 haben?

Ich habe an der Uni eine Aufgabe erhalten und sitze jetzt schon seit mehreren Stunden daran, aber ich habe absolut keine Idee, wie ich sie lösen soll.

Kann mir jemand helfen?

Meine Frage besteht darin, ob sich das Kellersymbol, welches zu Beginn im Keller ist, nennen wir es #, entfernen lässt.

also eine 90% Chance auf ein positives Ergebnis

Ich habe große Probleme bei der Chomsky Normalform.

Im ersten Schritt soll man ja die ε-Übergänge entfernen. Ich bin mir in dem Beispiel nicht sicher wie ich das machen soll und wie ich mit D verfahren soll. Aus D kann man ja nur ε ableiten und es kommt ja nur bei A zum Einsatz, bei welchem man 01 ableiten kann. Das ε ist ja dabei total irrelevant. Daher die Frage ob man das D nicht eigentlich ganz entfernen könnte.

Folgender selbst selbst erdachter NEA akzeptiert die Sprache die aus den Wörtern die mit 01 oder 11 beginnen.

Wenn ich den in ein DEA umwandeln möchte, bin ich mir nicht sicher, wie ich mit nicht definierten Übergängen (In dem Fall 0 bei q1) umgehen soll.

Gibt es vielleicht hier Mathematiker die beides belegt haben, wenn ja was empfindet Ihr als entspannter?

ich hab da paar Komplexitätsklassen also O Notationen ,die sind bissle komplexer ,kennt ihr einen rechner der die mir sortieren kann nach größe?

kann man bei der programmierung mit mehreren threads, aus auf einem system ausgefürt werden soll, welches eine nebenläufiige ausführung unterstützt deterministische ausführung gewährleisten? wenn ja wie, wenn nein warum

Hey Leute,

wie schon in der Überschrift erkennbar, verstehe ich diese zwei Arten von Algorithmen nicht ganz? Besonders was der Unterschied sein soll?

Vielen Dank,

Lyn

Verstehe ich das richtig, wenn ich z. B. ein Array mit 8 Elementen habe, z. B.

11, 25, 33, 42, 54, 58, 67, 96, und jetzt wissen will, wie viele Vergleiche die Binäre Suche braucht, um das Element 11 zu finden, kann ich dann einfach die Komplexitätsklasse zu Hilfe nehmen? Also hier O(log n) und da es 8 Elemente sind, brauche ich hier 3 Vergleiche, da O(log2(8)) = 3 ist? In dem Fall haut es doch hin, da es bei der Suche der 11 nicht um den Best Case O(1) handelt, weil die 11 nicht in der Mitte steht.

Falls das richtig ist, klappt das immer? Also bei anderen Algorithmen auch, zumindest wenn ich den Fall (Best, Worst und Average) erkenne und dann die entsprechende Komplexität nutze?

for i := 0; i < len(n); i++ { // O(n)

  for j := 0; j < len(n); j++ { // O(n)

    if x >= 30 { // O(1)

      for k := 0; k < len(n); k++ { // O(n)

        value = value + 10 // O(1)

      }

    } else {

      value = value + 2 // O(1)

    }

  }

}

ich hab den code und soll die Komplexitätsfunktion angeben ansich komm ich klar nur hab ein ein problem bzw ich stimme nicht mit chat gpt ein er sagt nähmlich=

O(n)(O(n)(O(1)+O(n)O(1)+O(1)))+O(1)

ich verstehe aber das erste + net ich hätte jetzt mal gesagt

also: O(n)(O(n)(O(1)*(O(n)O(1))+O(1)))+O(1)

G = ⟨{S}, {a, b, c, d}, {S → aSc | bSd | ε}, S⟩

Welche Sprache werde von dieser Grammatik generiert?

Ich verstehe welche Sprache damit erzeugt wird, da sie auch recht simpel ist, jedoch weiß ich nicht wie ich das aufschreiben soll. Kann mir Jemand weiterhelfen?

Vorab: Es geht um Reguläre Ausdrücke im Sinne der theoretischen Informatik.

Der "+"-Operator ist doch bei Anwendungen von Reguläre Ausdrücke wie ein XOR zu betrachten. "a+b" enthält die Wörter a und b aber nicht ab. (a+b)* würde a,b,ab,abab... wiederum enthalten. Oder sehe ich das falsch?

Bei Flaci, das ist ein Tool für sowas, ehemals auch AtoCC wird mir bei a+b nur ab als Wort der Sprache L angezeigt

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?

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?

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.

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!

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?

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:

Was bedeutet das "mal" beim dritten Punkt? 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 und 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.?

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

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.

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

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

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

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!

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?

Hallo an alle,

Ich habe mal eine Frage:

Wie lang braucht eigentlich eine Nachricht um die Erde über das Internet(theoretisch)? Kann mir bitte jemand diese Frage beantworten, wenn möglich bitte auch mit Quelle(außer Wikipedia). Danke schon mal im Voraus.