Theoretische Informatik – die besten Beiträge

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