Theoretische Informatik – die neusten Beiträge

Ich habe heute wohl einen Quanten-Tag.. :) ich versuche es mal kurz zu fassen:

Quanten = Wahrscheinlichkeiten, 1+1=2 = deterministisch

Wie geht das (so gut) zusammen? Danke. :)

Woran liegt es, wenn jemand zb ein Studium mit 1,0 abschließt, aber sein theoretisches Wissen nicht umsetzen kann und in Praktischer Arbeit völlig "unbrauchbar" ist?

Hallo zusammen
Wie wandle ich diese NEA in einem DEA um?

Leute, habt ihr Erfahrungen mit einer Bachelorarbeit in Informatik? (theoretische informatik)

Sollte ich meine Abbildungen selber erstellen, damit alles einheitlich ist? und habt ihr gute Tipps?

Ich verstehe das Konzept von Automaten nicht bzw ihren Sinn. Was genau sind Automaten in der Informatik? Für was gibt es sie? Und sind sie wichtig im beruflichen Leben als Informatiker?

Kann mir jemanden erklären, wie man das löst?

Hallo,

Ich habe Probleme diese Aufgabe zu lösen und weiß nicht, wie ich das am besten machen kann. Kann das jemand lösen? Es reicht, wenn nur das Zeichen pro Nummer mit Begründung geschrieben wird.

Meine Antwort dazu wäre:

1. x (A C B)

2. x (A C B)

3. x (A C B)

4. x (B C A)

5. x (B C A)

6. =

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?

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?

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?

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.

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?

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?

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

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 ❤

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?

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:

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

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

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.

Hey, ich habe folgende Aufgabe:

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

Kann mir da jemand helfen?

Checke irgendwie nicht, wie ich überprüfen soll, mit dem pumping-Lemma, ob eine Sprache regulär ist oder nicht.

1. Ist eine platzbeschränkte Turing-Maschine immer zeitbeschränkt?
2. Ist eine zeitbeschränkte Turing-Maschine immer platzbeschränkt?

Beim P/NP-Problem geht es soweit ich weiß darum das ein effizienter Algorithmus für ein Problem zum Beispiel die Färbung von Graphen, die Existenz von effizienten Algorithmen für alle anderen Probleme der selben Komplexität impliziert, korrigiert mich gerne falls ich das falsch verstanden habe. Ich verstehe nur gerade nicht wie man die Komplexität eines Problems definiert wenn man nicht den effizientesden Algorithmus kennt? "Ein Problem ist K-schwer wenn sich alle anderen Probleme der Klasse K auf den Algorithmus zur diesem Problem zurückführen lassen", damit beißt sich die Katze aber in den Schwanz du definierst die Komplexität eines Problems K dadurch daß sich alle anderen Probleme der Klasse K auf den den selben Algorithmus zurückzuführen wie unseres Anfangsproblems lassen. Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?

Könnte mir vielleicht jemand helfen. Ich komme bei einer Aufgabe gar nicht klar.

4) Schreiben Sie reguläre Ausdrücke für folgende Sprachen über dem Alphabet Σ = {a,b,c}.

a) Die Menge aller Wörter über Σ, die nicht mit c starten.

b) Die Menge aller Wörter über Σ, die höchstens ein b besitzen.

c) Die Menge aller Wörter über Σ, die mit einem anderen Zeichen enden als sie starten. Beispielsweise befinden sich babc in der Sprache, während sich bacb nicht in der Sprache befindet. Hinweis: Die Wörter haben mindestens die Länge 2.

Danke für die Hilfe

Habe folgende Aufgabe. Ich soll den Kürzesten Pfad in einem Labyrinth Rekursiv finden.

Bisher kenne ich mich nur mit Wave Propagation (Iterativ) und wallfollower etc aus.

Meine Idee ists nun, dass ich Rekursiv erstmal das Maze entdecke und jedem Schritt eine Distanz zu ordne (Rekursive tiefe).

Nachdem alle Zellen discovered sind gehe ich vom Ziel aus und Suche dort Rekursiv per Backtracking den Kürzesten weg.

Ist das der Richtige Ansatz um das Problem zu lösen?

Das Labyrinth kann auch keine Wände haben und sehr großen Freiraum. Siehe Beispiel:

new String[]{
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "S               D",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
}

Es wird per Aufgabe zugesichert, dass der Weg maximal 65535 schritte lang ist. Das springt sofort ins Auge, weil unsigned short so groß ist. Dies würde meine Theorie bestätigen wenn man eine unsigned short matrix nehmen würde zum tracken der besuchten Zellen.

Oder gibts da eine bessere Lösung? Hab noch nie wirklich rekursiv gearbeitet und mag Rekursion nicht wirklich bisher.

Hallo,
Ich würde gerne die Zahl - 21,25 im IEEE single Format darstellen. Dafür wird die Kommazahl ja erstmal in Binär umgewandelt. Jetzt weiß Ich jedoch nicht genau wie das geht. Ich weiß wie man negative ganze Zahlen im Einerkomplement, Zweierkomplement und Vorzeichendarstellung darstellt, Ich weiß auch wie man positive Kommazahlen darstellt, jedoch weiß Ich nicht wie man dies mit Kommazahlen macht. Mit Ek,Zk Vorzeichendarstellung?
Wäre super wenn mir jemand helfen könnte vielleicht auch mit einer beispielhaften Rechnung :)
Danke schonmal!

In dieser Aufgabe sollte ich den DEA zu einem Automaten zeichnen, der nur Wörter akzeptiert, die nicht "00" enthalten, wobei Σ = {0;1}. Wäre dieser Automat zulässig, bzw. was müsste ich verbessern ?

Hey könnte mir bitte jemand bei den Aufgaben helfen?

Entwerfen Sie einen DFA, der die Sprache L erkennt, wobei L wie folgt definiert ist:

L = {w ϵ {0,1}* | w endet mit 010 oder mit 01}

a) Geben Sie 3 möglichst unterschiedliche Worte aus L an.

b) Geben Sie 3 möglichst unterschiedliche Worte an, die nicht zu L gehören.

c) Geben Sie den DFA sowohl durch einen Zustandsgraph als auch seine Transitionstabelle an.

Vielen Dank im voraus!

Ich habe bis :

hA(n) ist Turing Berechenbar genau dann wenn , eine Turing Maschine existiert die auf Input n eine 1 schreibt falls n element A und ansonsten unendlich läuft. Was Äquivalant dazu ist, dass A semi entscheidbar ist.

also ist die Menge ja gleichmächtig wie die Menge der semi entscheidbaren Sprachen ? oder nicht?

sind die Semi entscheidbaren Sprachen denn abzählbar unendlich ? wenn ja wie beweise ich das wenn nein wo ist mein Fehler ?

Gibt es eine maximale Speichergröße die in einem System vorhanden sein kann und hängt die damit zusammen wie viele bit ein System hat ? Die Frage ist nur theoretisch und hat für mich keinen praktischen Nutzen.

Meine Überlegung:

Wenn eine Speicheradresse maximal 64bit lang sein kann dann kann es doch auch nur nur begrenzte bit im ganzen System geben die korrekt angesteuert werden können ?

Bsp: Für 64bit binär gibt es dezimal 2^64 Möglichkeiten also doch auch 2^64 verschiedene Adressen. Aufgrund dessen das jede Speicheradresse 64bit enthält kommt ich auch ein ganzes von (2^64)*64bit womit ich auf ein totales von

(2^64)*8*(0,1^15) petabyte = 147.573 petabyte

Oder

147.573.952 GB

Das sind natürlich utopische Mengen, jedoch bei einem 32bit system wären es dann nur

17,18 GB

Also wo liegt mein Denkfehler ?

Meine Kenntnisse vom Aufbau eines Computers sind nicht überweltigend, jedoch will ich ja was lernen also wenn die Antwort mit Google-recherche zu verstehen ist bin ich zufrieden.

Vielen Dank schonmal vorab

Hallo, evtl. kennt sich jemand mit der Pumping-Zahl aus.

Diese ist nämlich jene minimale Zahl p, sodass gilt:

Jedes Wort w aus der Sprache L mit einer Länge von mind. p (also |w| = p) kann in w = xyz aufgespalten werden, derart, dass

1. |xy| <= p
2. y =/= e (leeres Wort)
3. x(y^i)z ist in L

------------------------

Ich hätte mich jetzt gefragt, was die Pumping-Zahl von 0001*, 1011 und ((011) u (1*0*) ist.

-----------------------

Beim Ersten hätte ich p = 4 vermutet. Begründung: x = 000, y = 1, z = e

Dann |xy| <= p, y =/= e, und xy^iz ist in L (weil 000111...11 in L) für jedes i aus IN.

----------------------

Beim Zweiten bin ich mir nicht sicher, ob es da überhaupt eine Pumping-Zahl gibt, weil ich 1011 eigentlich nicht aufpumpen kann. Vielleicht weiß da jemand mehr.

----------------------

Beim Dritten hätte ich eine Pumping-Zahl von 1 vermutet. Begründung: Setze x = e, y = 1 und z = e

Dann |xy| <= p, y =/= e und xy^iz ist in L (weil 111...11 in L) für jedes i aus IN.

---------------------

Stimmen meine Vermutungen? Was mache ich mit dem endlichen Ausdruck 1011?

Ich wollte mal eure meine dazu wissen, ob dieser endliche Automat deterministisch ist oder nichtdeterministisch ist?

Meiner Meinung nach ist dieser Automat nichtdeterministisch, weil es kein eindeutigen Startzustand gibt, da man mit b oder c das Wort anfangen kann.

Lg

Hallo leute,

weiß jemand wie man das darstellt?

Man muss die Laufzeit in 0-Notation bestimmen von dem Algorithmus ggT (größten gemeinsamen Teilers). Also Schritt für Schritt z.B:

0(1)

0(1) => T(0) = 0(1)

......

wäre super wenn das jemand könnte. :)

Lg