Sprachen erkennen Zusatzmodul Z1

Wörter erkennen

Eine Turingmaschine kann auch entscheiden, ob ein Wort zu einer Sprache gehört. Hier gilt: Die Maschine bekommt das Wort auf das Band und räumt es ab. Ist das Wort gültig, soll am Ende das Band leer sein, sonst bleibt etwas stehen. Erweitere dafür das Bandalphabet der Maschine um die Zeichen, die du brauchst, zum Beispiel a und b.

Die Sprache aⁿbⁿ (gleich viele a und b) kann ein endlicher Automat nicht erkennen, ein Kellerautomat schon. Die Turingmaschine kann beides, denn sie kann auf dem Band beliebig weit zählen.

aⁿbⁿ
Aufgabe 1: Erstelle eine Maschine für die Sprache aus beliebig vielen a, gefolgt von genauso vielen b (aⁿbⁿ, auch das leere Wort). Bei einem gültigen Wort ist das Band am Ende leer, sonst nicht. Der Kopf startet unter dem rechtesten Zeichen.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

aⁿbⁿ mit Antwort
Aufgabe 2: Dieselbe Sprache aⁿbⁿ, aber mit einer eindeutigen Antwort: Am Ende soll nur ein einzelnes Zeichen auf dem Band stehen, eine 1 bei gültigem und eine 0 bei ungültigem Wort. Der Kopf steht darunter.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

Palindrome
Aufgabe 3: Erstelle eine Maschine, die erkennt, ob eine Folge aus 0 und 1 ein Palindrom ist, also vorwärts und rückwärts gleich gelesen wird (1001 und 1101011 sind Palindrome). Bei einem Palindrom ist das Band am Ende leer, sonst nicht.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

gleich viele 0 und 1
Aufgabe 4: Erstelle eine Maschine, die erkennt, ob auf dem Band gleich viele 0 und 1 stehen (in beliebiger Reihenfolge). Bei gleich vielen ist das Band am Ende leer, sonst nicht.

Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.

← Vorheriger Abschnitt Nächster Abschnitt →