0 Daumen
1,3k Aufrufe

Ich verstehe nicht wie man Nerode Äquivalenzklassen bildet. Ich denke es soweit verstanden zu haben, das die Klasse alle Wörter beinhaltet, die gleich enden.

Als konkretes Beispiel hatte ich gestern in einer Altklausur den regulären Ausdruck:

(01|010|000)*

wir sollten Vertreter der nerode äquivalenzklasse nennen.

Die Lösung lautet

0, 00 und 000

YouTube Videos haben mir leider auch nicht weitergeholfen. Drum bin ich hier. Eigentlich ist das hier ja ein Mathe Forum, denke aber das die beiden Fächer nah beisammen liegen.

Wäre nett wenn jemand einfach den Lösungsweg erklärt, denke dann kann ich das auch auf andere Aufgaben übertragen

MfG und schönes Wochenende

Avatar von

1 Antwort

+1 Daumen

> ... das die Klasse alle Wörter beinhaltet, die gleich enden.

Nein.

Beispiel 1: Die Wörter babba und abbba enden beide auf bba. Trotzdem kann nicht entschieden werden ob die zwei Wörter Nerode-äquivalent sind. Grund ist, dass keine Sprache angegeben wurde, bezüglich der die Nerode-äquivalent betrachtet werden soll.

Beispiel 2: Nehmen wir mal die Sprache L= der Wörter, die aus gleich vielen a wie b bestehen. Bezüglich dieser Sprache sind die Wörter aus Beispiel 1 Nerode-äquivalent weil sie durch die gleichen Suffixe zu Wörtern aus L= ergänzt werden können (nämlich die Suffixe in denen ein a mehr vorkommt als b vorkommen). Bitte beachte dabei, dass trotz der Nerode-Äquivalenz beider Wörter weder babba, noch  abbba zu L= gehören.

Beispiel 3: Nehmen wir mal die Sprache L2b der Wörter, in denen nicht mehr als 2 b hintereinander vorkommen. Bezüglich dieser Sprache sind die Wörter aus Beispiel 1 nicht Nerode-äquivalent weil babba durch das leere Wort zu einem Wort aus L2b ergänzt werden kann, abbba aber nicht.

> (01|010|000)* wir sollten Vertreter der nerode äquivalenzklasse nennen. Die Lösung lautet 0, 00 und 000

Die Lösung  ist falsch. Jeder dieser Vetreter kann zu einem Wort aus (01|010|000)* ergänzt werden. 1 kann nicht zu einem Wort aus (01|010|000)* ergänzt werden. Also ist 1 in keiner der angegebenen Äquivalenzklassen.

Avatar von 107 k 🚀

Vielen Dank für die ausführliche Antwort. Habe es nun verstanden. 

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community