Theoretische Informatik – die besten Beiträge

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

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?

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?

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

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

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

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?

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!

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