Myhill Nerode Äquivalenzklassen?

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

Bild zum Beitrag

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 ?

15.12.2020, 14:18

Hier mal meine Überlegung

MagicalGrill

15.12.2020, 13:38

Jetzt habe ich noch gezeigt das diese alle unterschiedlich sind und das die 3 wirklich alle sind.

Wie sieht dein Beweis hierzu aus? Vllt bedarf es ja kaum zusätzlicher Erklärung.

Super427

Beitragsersteller

15.12.2020, 13:48

stimmt denn meine Annahme das es 3 Äquivlaenz klassen gibt.

Würde dir gerne meinen beweis schicken aber hier darf man nur 100 Buschstaben reinschreiben

1 Antwort

Vom Beitragsersteller als hilfreich ausgezeichnet

MagicalGrill

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

15.12.2020, 14:41

Ja, es gibt in der Tat genau 3 Äquivalenzklassen, nämlich

[ɛ], [a] und [z] mit z ∈ ∑ \ {a}.

Um zu zeigen, dass die paarweise verschieden sind, kannst du ja einfach zeigen, dass der jeweilige Repräsentant in keiner der anderen beiden Klassen liegt.

Um zu zeigen, dass das alle Klassen sind, brauchst du nur zeigen, dass jedes w ∈ ∑* in einer der 3 Klassen liegt. Im Wesentlichen hast du den richtigen Ansatz auch schon aufgeschrieben: Das leere Wort liegt in [ɛ], jedes Wort das mit a beginnt liegt in [a] und jedes nicht-leere Wort das nicht mit a beginnt liegt in [z]. Du musst nur noch begründen, weshalb das jeweils der Fall ist.

All dies geht prinzipiell "elementar", indem du einfach nur die Definition der Nerode-Relation verwendest.

Super427

Beitragsersteller

15.12.2020, 14:42

danke dir <3

Ähnliche Beiträge

Äquivalenzklassen gemäß Myhill-Nerode genau drei Stück?

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?

...zum Beitrag

Alle Äquivalenzklassen der Nerode-Relation von L bestimmen?

Ich habe eine gegebene Sprache L3, die die zwei Sprachen L1 und L2 vereinigt.

L1 ist hierbei =: {(ab)^i mit i ≥ 0} und

L2 ist =: {(aab)^i mit i ≥ 0}

Von der Sprache L3, also L1 ∪ L2, soll ich nun alle Äquivalenzklassen der Nerode-Relation bestimmen. Die akzeptierten Wörter dieser Sprache sind also alle Wörter, die eine Abfolge von ab darstellen [ab], alle Wörter, die eine Abfolge [aab] darstellen und das leere Wort e. Der Rest sind illegale Eingaben, die der Automat nicht akzeptieren kann. Womit ich jetzt ein Problem habe ist, dass bei der Nerode Relation gelten soll: Index(RL) >= Anzahl der Zustaende des Äquivalenzklassenautomats. Muss ich jetzt noch einen zeichnen oder kann ich die Aufgabe auch so lösen?

...zum Beitrag

Pumping Lemma für reguläre Sprachen anwenden?

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!

...zum Beitrag

Pumping Lemma reguläre Sprache?

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

...zum Beitrag

Äquivalenzklassen gleich?

Wenn a ein Element der Äquivalenzklasse [x] ist und auch von [y], wieso muss dann [x]=[y] sein?

...zum Beitrag

Wie kann man das zeigen / beweisen Theoretische Informatik?

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 ?

...zum Beitrag

Findet ihr, dass theoretische Informatik schwer ist?

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?

...zum Beitrag

Bei Djkstra mit negativen Kantengewichten positive Konstante addieren?

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

...zum Beitrag

Theoretische Informatik Äquivalenzklassen?

Nach Satz von Myhill-Nerode

(a) L = {a(b^k)c | k ∈ No} No sind die natürlichen Zahlen mit 0

Warum gibt es hier genau 3 Äquivalenzklassen? Der Suffix Z ist einmal epsi, c und ac.
Soweit ok.

Warum schaut man sich nicht als Suffix z. B. bc, oder bbc, oder bbbc an?

...zum Beitrag

reguläre Sprachen epsilon als eigene Äquivalenzklasse?

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!

...zum Beitrag

Informatik Studium HS Matheanteil?

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?

...zum Beitrag

Was sind die Äquivalenzklassen?

Wie finde ich bei folgender Aufgaben die Äquivalenzklassen heraus und was sind die regulären Ausdrücke dieser?

...zum Beitrag

Java short und char binär dargestellt?

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?

...zum Beitrag

Äquivalenzklassen denkfehler?

Ich glaube ich habe was Äquivalenzklassen angeht einen Denkfehler, im Bild sieht man was die Äquivalenzklasse sein soll, bei dem Wort Äquivalenz kommen mir allerdings sofort Äquivalenzrelationen in den sinn welche Relationen sind die gleichzeitig reflexiv, symmetrisch und transitiv sind. Hier wird aber gesagt dass die Äquivalenzklasse von X bedeutet dass y in X liegt sodass y mit x in relation steht. Das heißt rein theoretisch schließt man nicht aus dass die Relation zb asymmetrisch sein darf, zudem frage ich mich warum y in X und nicht x in X deklariert wird? Ich bin leider etwas unbegabt in Mathe also verzeiht bitte wenn ich klinge wie der letzte Vollhorst

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen