Inhaltsverzeichnis
Wie zeigt man dass eine Menge abzählbar ist?
Eine Abzählung einer Menge A ist eine Bijektion N → A, also eine Folge a0,a1,a2,…, in der jedes Element von A genau einmal auftritt. Eine Menge A heißt 1. abzählbar unendlich, falls sie eine Abzählung besitzt, also |A| = |N| gilt; 2. abzählbar, falls sie endlich oder abzählbar unendlich ist; 3.
Wann ist eine Menge abzählbar unendlich?
Eine Menge M heißt abzählbar unendlich, wenn sie zur Menge N der natürlichen Zahlen gleichmächtig ist. Alle anderen unendlichen Mengen sollen überabzählbar unendlich heißen. Für die Mächtigkeit der Menge der natürlichen Zahlen wird die Kardinalzahl ℵ0 eingeführt (Sprich: Aleph).
Ist das leere Wort eine Sprache?
Die Mengen L1 = {ε,a} oder L2 = {aa,aaaa,aaaaaa} sind formale Sprachen, da sie (echte) Teilmengen von Σ∗ sind. Die leere Sprache ist die leere Menge, notiert als {} oder ∅. Die Sprache, welche nur die leere Zeichenkette umfasst, wird als {ε} notiert. Die leere Sprache {} und die Sprache {ε} sind nicht dasselbe.
Sind alle endlichen Sprachen regulär?
Alle endlichen Sprachen sind regulär. Nicht alle unendlichen Sprachen sind regulär. Es gibt also Sprachen, die nicht durch einen RA repräsentiert werden können und die nicht von einem DEA/NDEA akzeptiert werden.
Sind abzählbare Mengen abgeschlossen?
Jede endliche Menge ist abgeschlossen, und auch die Mengen ℕ und ℤ sind abgeschlossen. Während den offenen Mengen also nur die Mächtigkeiten 0 und „überabzählbar“ zukommen, können die abgeschlossenen Mengen also endlich, abzählbar unendlich oder überabzählbar sein.
Ist das leere Wort ein Palindrom?
Merkmale. Die Länge des leeren Wortes ist stets 0. Diese Eigenschaft folgt direkt aus der Definition. Das leere Wort ist identisch mit seiner Spiegelung und damit ein Palindrom.
Wann ist eine formale Sprache regulär?
Eine Sprache ist regulär, wenn: die Sprache von einer regulären Grammatik erzeugt wird; endliche Automaten sie akzeptieren; und die Sprache durch einen regulären Ausdruck dargestellt werden kann.
Wann ist eine Sprache nicht regulär?
Regelmäßiger kann eine Sprache kaum aufgebaut sein, aber es gibt keinen regulären Ausdruck, der die Sprache L beschreibt. Jedes Wort der Sprache enthält genauso viele a’s wie b’s, und dies lässt sich mit einem regulären Ausdruck nicht ausdrücken.
Wie bestimmt man die Mächtigkeit einer Menge?
Falls zwei Mengen M und N gleich viele Elemente besitzen, wenn also ∣ M ∣ = ∣ N ∣ \left|M\right|=\left|N\right| ∣M∣=∣N∣ gilt, dann nennt man die Mengen gleichmächtig. Falls M unendlich viele Elemente hat, ist die Mächtigkeit unendlich ∞.
Wann ist eine Menge Gleichmächtig?
Zwei endliche Mengen sind zueinander gleichmächtig, wenn sie die gleiche Anzahl von Elementen besitzen. Durch paarweise Zuordnung der Elemente können auch Mengen mit unendlich vielen Elementen nach ihrer Mächtigkeit verglichen werden.