Hallo Community,

wie ihr im Betreff schon sehen könnt komme ich bei einer Aufgabe nicht weiter. Ich soll einen DEA/DFA (Deterministischer Endlicher Automat) konstruieren, der die Binärdarstellung aller Zahlen "i" akzeptiert, wenn diese durch 5 teilbar sind (i%5=0). Eingabezeichen = binäres Alphabet.

Könnt ihr mit helfen?

Moin moin. Unszwar geht es darum, dass man die asymptotische Notation zeigen soll, also das log2 (n!) genau so schnell wächst wie (n log2 n), bei der Fakultätsfunktion n! = n* (n-1) * (n-2)...1.

Hierzu muss in Aufgabenteil a) gezeigt werden, dass log 2 (n!) höchstens so schnell wächst wie (n log2 n) und in Aufgabenteil b), dass es mindestens so schnell wächst

Mein Ansatz. Wenn man zwei Funktionen teilt und das Ergebnis gegen unendlich geht, gilt O (höchstens so schnell). Wenn das Ergebnis gegen 0 geht, gilt Ω. Wenn das Ergebnis der Division ein konstanter Faktor ist, gilt Θ. Man könnte also log 2n! durch (n log 2n) teilen und zeigen, dass ein konstanter Faktor rauskommt und daher Θ gilt.

Die Aufgabe zwingt einen jedoch dazu, sowohl O und dann Ω zu zeigen

Ich müsste also log2n! durch (n log2 n) teilen und zeigen, dass es gegen unendlich geht, um O zu zeigen. Aber dann müsste man auch zeigen, dass es gegen 0 geht. Der Ansatz funktioniert also nicht.

Eine andere Möglichkeit wäre

log2 n! <= c * (n log2 n) zu rechnen. Aber dann müsste man auch log 2 n! >= c * (n log 2n) zeigen. Und leider kann ich n! nicht wegkürzen. :(

Hallo

falls ihr das schon gemacht habt, ist das schwer? Bruacht man da viel aufwand?

Ich habe mal gehört dass sich da viele irgendwie die Zähne ausbeißen aber eigentlich ist das mit den Automaten ja ziemlich leicht.

Kann mih da wer aufklräen? Wie schwer ist das ca?

lg

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

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.

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?

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!

Hallo , habe ich folgende Aufgabe richtig gelöst ? oder habe ich einen Denkfehler:

Ich habe gesagt es gibt genau 3 Äquivalenzklassen nämlich :

[Epsilon] ,[a] und [z] wobei z elemt von Sigma stern ist aber ohne die Wörter die mit a beginnen.

Jetzt habe ich noch gezeigt das diese alle unterschiedlich sind und das die 3 wirklich alle sind. Hier bin ich mir aber nicht sicher.

Kann mir das eventuell jemand erklären ?

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

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

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

Wir haben in Informatik momentan als Thema Sortierverfahren und jeder im Kurs soll eines vorstellen. Nun, ich habe den Quicksort zugeteilt bekommen und ich soll mich bei diesem ebenfalls mit der Laufzeit auseinandersetzen. Beim Quicksort beträgt die Laufzeit im worst-case O(n^2), was ich ja noch verstehe. Im average und im best-case beträgt diese aber O(n*log(n)) und ich weiß bei Leibe nicht was das heißen soll.

Ich hatte daraufhin mal auf Wikipedia nachgeschaut, aber da stand nur das es sich um ein super lineares Wachstum handelt und ich habe leider keine Ahnung, was das heißen soll...

Wäre nett, wenn das irgendwer zufällig wissen sollte. :)

Guten Abend

Ansatz:

Zunächst erst mal alle unnötig kompliziert gegebenen Funktionen so umschreiben, dass sie sich vergleichen lassen

a (n) = 13n³, kann man nicht mehr vereinfachen

b (n) = log_4 n³ ist nichts anderes als 1,5 log_2 n

c (n) = 9 log_3 n hätt ich jetzt auch nicht weiter vereinfachen können

d (n) = log_2 4 n^4/3 ist nichts anderes als log_2 (4) + log2 (n^3/4), also 2 + 3/4 log_2 n

e (n) = n^log_4 n^4 kann man umschreiben zu n^2 log_2 (n).

Ich hätte die Funktionen also sortiert (von langsam nach schnell):

c < d < b < a < e.

Problem: Mein Tutor meinte die richtige Reihenfolge wäre: d < b < c < e < a.

Ich versteh es nicht. c. hat ja log_3 (n) und das ist ja schon mal langsamer als alles mit log_2 (n). Bei d und b bin ich mir unsicher, weil die ja eigentlich asymptotisch gleich schnell wachsen sollten. b wächst vielleicht bissl schneller weil es mit 1,5 multipliziert wird, während d nur mit 3/4 multipliziert wird.

Großes Kopfzerbrechen bereitet mir die Tatsache, dass e langsamer wachen soll als a. Bei e (n) ist doch das "n" im Exponenten. Auch wenn man im TR z.B. für n = 17 die Funktion e (n) eingibt, also 17^log_4 (17)^4 ist das 2.9210^21, also eine tierisch hoche Zahl. Wärend n = 17 in die Funtkion a(n) eingesetzt, lediglich 1317³ = 63869 ergibt, also viel weniger wächst. Auf desmos kann man die Funktionen plotten, und dort ist e (n) [bzw. ich musste es hier f(n) nennen, weil das Programm den Buchstaben "e" direkt als Euler'sche Phi-Funktion interpretiert] auch viel stärker an der y-Achse dran, also müsste es doch eigentlich stärker wachsen, or?

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

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

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, ich verstehe die Konzept auf Reduktion, und auch Turing machine. aber ich weiss nich wie man mit so Aufgaben umgehen muss.

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?

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

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 ?

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.

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!

Hey, ich habe folgende Aufgabe:

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

Kann mir da jemand helfen?

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?

Im Buch Theoretische Informatik von Hoffmann ist die Kleene'sche Hülle über ein Alphabet (Sigma) definiert als:

(Sigma)* := Vereinigung von ((Sigma)^i) mit Index i=0 bis unendlich

(Leider gibt es hier keine LaTeX-Formatierung. Daher die etwas unschöne Formelschreibweise)

Meines Erachtens sind durch diese Definition auch unendliche Folgen inbegriffen, da eben der Index i bis unendlich zählt und damit unendliche Folgen (Sigma)^(unendlich) Elemente der Kleene'schen Hülle sind. Da die Menge aller unendlichen Folgen über (Sigma) m.E. überabzählbar ist (man korrigiere mich, wenn ich hier falsch liege), ist auch die Kleene'sche Hülle überabzählbar.

Nun lese ich jedoch überall, dass die Kleene'sche Hülle abzählbar unendlich ist mit dem Argument, dass alle Elemente endlich sind und man könne diese dann lexigrafisch ordnen. Wie allerdings oben aufgeführt, bin ich eher der Meinung, dass in der Kleene'schen Hülle auch unendlich lange Wörter enthalten sind und diese daher überabzählbar ist.

Wo liegt nun mein Fehler?

Hey :)

ich hab hier eine Aufgabe zu endlichen Automaten und einen Lösungsansatz.

Aufgabe:
Es soll ein endlicher Automat gezeichnet werden, der eine gerade Anzahl an Nullen akzeptiert.

A = {0,1}

Meine Lösung:

Hi,

Im Unterricht haben wir mit theoretischer Informatik und endlichen Automaten begonnen. Mein Lehrer hat uns ein Beispiel mit einem Lachautomaten gezeigt, bei dem aber nur ha/haha/hahaha/... ausgegeben werden kann. Dann hat er uns die Aufgabe gegeben, dass wir diesen Automaten so umgestalten/ erweitern sollen, damit er zusätzlich auch hi/hihi/hihihi/... und ho/hoho/hohoho/... ausgeben kann. Wir hatten keine Zeit mehr und nur einer hat es oberflächlich an die Tafel gemalt... als ich dann nachgefragt habe, konnte es mir selbst der Lehrer nicht erklären. Um es zu verstehen möchte ich die Aufgabe aber lösen, habe aber noch nicht mal einen Ansatz. Kann mir jemand helfen? Und geht das überhaupt? Es soll doch ein endlicher Automat sein. es ist auch ein Bild von der Lachmaschine bei der Aufgabe soll das Ausrufezeichen aber nicht Teil des Eingabealphabets sein.

Schonmal Danke, wenn mir jemand helfen kann!!!

PS das ist KEINE (!) Hausaufgabe

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 ?

Meine Lösung:

NFA in DFA umgewandelt

Feedback bitte!

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?

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

Ich soll die Big O Notation von folgenden Funktionen beweisen:

Ist O(x):

 Element von O(ln n) Ist O (n^2)

Für mich macht das das erste und das 3. keinen Sinn, da n*ln(n) ja nicht quadratisch ist, sondern logarithmisch. Und das erste hat ja einen Wurzel Faktor in sich.

Wie gehe ich da vor? Habe ich einen Denkfehler?

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

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

Ich komme leider nicht weiter beim Beweisen. Wie kann ich beweisen dass RoS nicht dasselbe ist wie SoR. Vorgegeben ist es mittels Prädikatenlogik zu lösen. Ich hab leider keine Vorstellung davon wie ich RoS so umformen kann dass ich beweise dass es ungleich SoR ist. Jede Antwort würde helfen!!

Danke im Voraus

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?

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?

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

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!

falls das eine dumme frage ist, entschuldige ich mich 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?

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.

Hallo,

ich würde gerne ack(3,3) und ack(4,4) berechnen, nur sind die Zahlen so groß bzw die Rekursionstiefe so groß, dass keins meiner Programme dies berechnen kann.

Gibt es eine Möglichkeit die Zahlen herauszubekommen?

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

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

Gruß

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

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

LG

Jensek81

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 ?

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!

Hallo weiß jemand wie man hier das Pumping Lemma anwedet ?

Zeigen Sie mithilfe des Pumping-Lemmas, dass die Sprache

L={w∈Σ∗: |w| ist eine Primzahl } über dem Alphabet Σ = {”Frohe“,”Adventszeit“} nicht regular ist.

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

Auch wer keine Ahnung von Informatik hat sollte sehen, dass hier was falsch ist, oder peile ich gerade einfach was nicht?

Kurz zur Erklärung:

Terminal = la oder le oder lu

Nicht-Terminal (quasi ne Variable) = S, A, B...

Erst steht im Buch folgender Satz:

Dann das auf der nächsten Seite (beachtet nur die rechte Blase):

Dort steht nun es könnte ein Nicht-Terminal alleine stehen. Darunter sieht man aber ganz klar ein Terminal (das lu) alleine! Dass ich hier eig. nichts verwechsle beweist doch der Satz im 1. Bild, oder was verstehe ich nicht?

P.S. Hier werden gerade reguläre Sprachen bzw. Grammatiken definiert.

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!

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.

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.

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.

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

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?

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

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.

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

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

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

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?

A --> Ba (linksreguläre Grammatik)

A --> aB (rechtsreguläre Grammatik)

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

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

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

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?

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!

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

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

Ziel: 1 Token in S7

Woran erkenne ich an diesem Kellerautomaten den Nichtdeterminismus?

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

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

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?

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ß

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!

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?

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.

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!

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

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, kann mir jemand bei der Aufgabe helfen? Ich verstehe gar nichts.

Die Aufgabe b)

Vielen Dank schonmal in vorraus.

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.

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,

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

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

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?

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?

Hallo,

Ich habe den Kellerauromaten aus der Theoretischen Informatik soweit verstanden, allerdings weiß ich nicht wie man die delta-Funktion nun aufschreibt. Man bildet dabei ja eine Kombi aus Zustand, Kellersymbol und Buchstabe auf ein Wort über dem Kelleralphabet und einem Zustand ab. Was sind hier aber diese Worte über dem Kelleralphabet?

Danke