Kursthemen

  • 11 B: Formale Sprachen, endliche Automaten und John-von-Neumann-Rechner

  • Mealy-Automat - Automat mit Ausgabe

    • Endliche Automaten mit Ausgabe

      Beginnen wir mit der Suche nach dem Modell für eine universelle Maschine. Modell bedeutet, eine möglichst exakte, allgemeingültige Beschreibung nebst einem Funktionsbild für eine programmierbare Rechenmaschine zu finden. Die grundlegenden Komponenten kennen wir bereits seit Klasse 5/6 als EVA-Prinzip.

      Beginnen wir die Suche mit elementaren Geräten - Computer sind da viel zu komplex. Wie wäre es mit einem Automaten? Reale Automaten sind ebenfalls Maschinen, die sich mit EVA beschreiben lassen. Sie finden sich z. B. in Form von Geldautomaten, Parkscheinautomaten, Getränkeautomaten oder Bonbon-Automaten.

      Reale Automaten lassen sich durch das Modell des endlichen Automaten mit Ausgabe (Mealy-Automat) beschreiben. Das Modell geht auf die 1955 veröffentliche Arbeit "A Method for Synthesizing Sequential Circuits" des US-amerikanischer Mathematiker George H. Mealy zurück.

      Definition des Mealy-Automat

      Ein Mealy-Automat MA = (X, Y, Z, δ, λ, z0) ist ein endlicher Automat mit Ausgabe. Dabei gilt:

        • X ... Eingabealphabet (nichtleere, endliche Menge)
        • Y ... Ausgabealphabet (nichtleere, endliche Menge)
        • Z ... Zustandsmenge (nichtleere, endliche Menge)
        • δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
        • λ ... Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) genau ein Ausgabezeichen zuordnet
        • z0 ∈ Z ist der Anfangszustand
      Aufbau eines Funktionsmodells

      Arbeitsweise
      • Der Automat liest ein Zeichen vom Eingabeband.
      • In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen wechselt der Automat in einen Folgezustand und gibt auf dem Ausgabeband ein Zeichen aus. Anschließend werden beide Bänder um eine Zelle weiter bewegt.
      • Der Vorgang beginnt von vorn, solange noch ungelesene Zeichen auf dem Eingabeband sind.
    • Beispiel: Blumenautomat

      Ein Blumenautomat bietet Blumensträuße für 4 EUR an. Der Kunde wirft 1- oder 2-Euro-Münzen ein und erhält die Blumen. Andere Münzwerte akzeptiert der Automat nicht. Zu viel gezahltes Geld wird nicht erstattet.

      Der Blumenautomat kann als Mealy-Automat MA = (X, Y, Z, δ, λ, q0) modelliert werden mit

      • X = {1_EUR, 2_EUR}
      • Y = {-, Blumen}
      • Z = {q0, q1, q2, q3}
      • δ, λ als Tabelle

        oder als Graph
      • q0

    • Aufgabe zum Mealy-Automat

      Der durch nachfolgenden Graph gegebene Mealy-Automat mit Ausgabe MA = (X, Y, Z, δ , λ , q0) simuliert ein Verschlüsselungsverfahren, das nur mit Ziffern als Eingabezeichen arbeitet.

      .

      1. Geben Sie die Mengen X, Y und Z an.
      2. Verschlüsseln Sie die Zahlenfolge 0 - 8 - 1 - 5 und entschlüsseln Sie die Nachricht 18 - 24 - 12 - 14.
      3. Entwickeln Sie einen Automaten mit Ausgabe, der nach diesem Prinzip verschlüsselte Nachrichten entschlüsselt. Der Automat soll dabei die Eingabe ziffernweise entgegen nehmen, also für obiges Beispiel statt 18 - 24 - 12 - 14 die Form 1 - 8 - 2 - 4 - ...
    • Lösungen zur Aufgabe Mealy-Automat Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösung Klingelton Datei
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösung Kaffeeautomat Datei
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

  • Akzeptor und Sprache

    • Endliche Automaten ohne Ausgabe - Akzeptor

      Ein Safe öffnet sich nur dann, wenn die vierstellige Ziffernkombination korrekt eingegeben wurde. Eine Smartphone lässt sich nur dann bedienen, wenn eine PIN oder der Fingerabdruck korrekt sind. Beide Fälle lassen sich durch einen Automaten beschreiben. Eine Ausgabe nach jedem Schritt ist jedoch nicht mehr erforderlich. Erst am Ende der Eingabe muss entschieden werden, ob diese akzeptiert oder nicht akzeptiert wird. Solche Automaten nennt man Akzeptoren.

      Definition des Akzeptors - Automat ohne Ausgabe

      Ein Akzeptor A = (X, Z, δ, z0, ZE) ist ein endlicher Automat ohne Ausgabe. Dabei gilt:

        • X ... Eingabealphabet (nichtleere, endliche Menge)
        • Z ... Zustandsmenge (nichtleere, endliche Menge)
        • δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
        • z0 ∈ Z ist der Anfangszustand
        • ZE ... Endzustandsmenge (nichtleere, endliche Teilmenge von Z)
      Aufbau eines Funktionsmodells

      Arbeitsweise
      • Der Automat liest ein Zeichen vom Eingabeband.
      • In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen wechselt der Automat in einen Folgezustand. Anschließend wird das Band um eine Zelle weiter bewegt.
      • Der Vorgang beginnt von vorn, solange noch ungelesene Zeichen auf dem Eingabeband sind.
      • Befindet sich der Automat nach Lesen aller Eingabezeichen im Endzustand, so ist die Eingabe akzeptiert.
      Sprache L(A) eines Akzeptors A
      • Die Sprache eines Automaten L(A) ist die Menge aller von ihm akzeptierten Wörter, die man aus dem Eingabealphabet X bilden kann.
      • Die Sprache kann verbal, durch die Angabe eines Musters oder aller Wörter beschrieben werden.
      Beispiel: Safe mit vierstelligem Ziffernschloss

      Ein elektronischer Safe lässt sich nur dann öffnen, wenn die Ziffernkombination 0815 eingegeben wird. Alle anderen Eingaben sperren den Safe dauerhaft.

      Dies lässt sich als Akzeptor A = (X, Z, δ, q0, ZE) modellieren mit

          • X = {0, 1, ..., 9}
          • Z = {q0, q1, q2, q3, q4, q5}
          • δ als Tabelle

            oder als Graph
          • q0
          • ZE = {q4}

      Die Sprache L(A) des Automaten besteht einzig aus dem Wort w = 0815, L(A) = {0815}.

    • Lösungen zu den Aufgaben aus der Zusammenfassung "Akzeptor und Sprache" Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösungen Akzeptor in Anwendungen Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösungen Akzeptor mit ab- bzw. 01-Sprachen Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

  • nur für LK: Kellerautomaten - keine Prüfungsrelevanz im Prüfungsjahr 2023 und 2024

    • Endliche Automaten ohne Ausgabe und mit Kellerspeicher - Kellerautomat

      Im Baumarkt gibt es einen Automaten, der Schrauben und die passenden Anzahl Muttern eintütet. Zuerst wird die gewünschte Anzahl der Schrauben mit Mutter erfasst, dann die Schrauben und anschließend die Muttern in die Tüte gegeben. In eine Sprache übersetzt also: L = {Schrauben Muttern | n > 0}. Können wir einen Akzeptor konstruieren, der diese Sprache erkennt und akzeptiert?

      Ansatz: Für n ≤ 3 liefert der Graph des Akzeptors (ohne Zustandsübergänge in einen Fehlzustand) eine Lösung:

      Eine Erweiterung für größere n scheint auf den ersten Blick problemlos möglich, man muss nur neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht der Definition des Akzeptors. Diese Sprache kann also nicht von einem Akzeptor erkannt werden. Wir benötigen dafür "irgendeinen" Speicher, der sich die Anzahl der Schrauben merken kann.

      Kellerautomat – Kellerspeicher

      Ein sehr simpler Speicher ist der sog. Kellerspeicher (Stapel, Stack). Wie in einem Keller können Objekte oben abgelegt (push) und von oben entnommen (pop) werden. Dabei gilt: das zuletzt abgelegte Objekt muss als erstes wieder entnommen werden. Dieses Prinzip bezeichnet man mit Last in – First out (LIFO).

      Funktionsmodell eines Kellerautomaten

      Der Automat besitzt einen Kellerspeicher zum Ablegen von Objekten. Der Kellerspeicher

      • ist nach oben offen, also unendlich groß,

      • hat das Symbol # zur Anzeige des leeren Kellers.

      Zum Kellerautomaten gehören außerdem eine Steuereinheit und ein Eingabeband, dass die Eingabezeichen enthält, ein nach rechts bewegbarer Lesekopf sowie eine Lampe zur Anzeige des Akzeptierzustandes.

      Arbeitsweise
      1. Initialisierung des Kellerautomaten: Keller ist leer, der Kellerlesekopf steht auf dem Kellerleerzeichen #
      2. Einlesen des Eingabezeichens vom Eingabeband und Entnahme des aktuelle Kellerzeichen
      3. Zustandsübergang und Kelleroperation (push, pop, nop) in Abhängigkeit vom aktuellen Zustand, dem Eingabezeichen und dem Kellerzeichen
      4. Vorrücken des Bandlesekopfs um ein Zeichen
      5. ggf. Wiederholung der Schritte 2 bis 4

      Der Kellerautomat akzeptiert eine Eingabe, wenn das Eingabewort vollständig eingelesen wurde, der aktuelle Zustand eine Endzustand ist und der Inhalt des Kellers leer ist.

      Definition des Kellerautomaten

      Ein deterministischer Kellerautomat KA = (X, Z, Γ, δ, z0, k0, ZE) ist ein endlicher Automat ohne Ausgabe und mit Kellerspeicher. Dabei gilt:

        • X ... Eingabealphabet (nichtleere, endliche Menge)
        • Z ... Zustandsmenge (nichtleere, endliche Menge)
        • Γ ... Kelleralphabet (nichtleere, endliche Menge)
        • δ ... Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit vom jeweils aktuellen (ggf. leerem) Eingabezeichen und Kellerzeichen höchstens eine Kelleroperation und einen Folgezustand zuordnet
        • z0 ∈ Z ist der Anfangszustand
        • k0 ∈ Γ ist das Kellerleerzeichen (#)
        • ZE ... Endzustandsmenge (nichtleere, endliche Teilmenge von Z)

      Bei einem nichtdeterministischer Kellerautomaten müssen die Zustandsübergänge nicht eindeutig sein.

      Beispiel: Kellerautomat für den Schrauben-Muttern-Automaten

      Die akzeptierte Sprache für den Automaten aus dem Eingangsbeispiel ist L = {Schrauben Muttern | n > 0}.

      Dafür lässt sich ein Kellerautomat KA = (X, Z, Γ, δ, z0, k0, ZE) konstruieren:

          • X = {Schraube, Mutter}
          • Z = {q0, q1, q2}
          • Γ = {#, S}
          • δ als Graph
          • q0
          • k0 = #
          • ZE = {q2}

      wobei die Beschriftung eines Übergangs wie folgt aufgebaut ist: (erwünschtes Kellerzeichen, erwünschtes Eingabezeichen): zu realisierende Kelleroperation.

        • Die Kelleroperation S# bedeutet dabei, dass das Zeichen S eingekellert werden soll, die Raute - die beim Lesen aus dem Keller entnommen wurde - jedoch davor wieder zurückgeschrieben werden muss.
        • Die Kelleroperation ε bedeutet dabei, dass kein Zeichen zurückgeschrieben werden muss.
        • Die Kelleroperation # bedeutet dabei, dass die Raute - die beim Lesen aus dem Keller entnommen wurde - wieder zurückgeschrieben werden muss.

      Der Übergang in den Endzustand q2 sieht eigenartig aus, bedeutet aber:
      Wenn der Keller leer ist und kein Zeichen mehr auf dem Band, dann setzte den Keller wieder leer und wechsle und den Endzustand.

      ε hat also eine Mehrfachbedeutung: 

        • als Kelleroperation: nichts zurückschreiben
        • als "virtuelles" Eingabezeichen - nichts vom Band lesen
    • Lösungen Rangierproblem Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösungen Übungszettel Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Determinismus und Nichtdeterminismus

      Die Aufgabe mit den Palindromen ist gar nicht so einfach. Unterscheiden wir nach drei Fällen:

      1. Palindrom mit Trennzeichen
      2. Palindrom ohne Trennzeichen und mit gerader Länge
      3. Palindrom ohne Trennzeichen und mit beliebiger Länge

      Die Aufgabe 1 ist mithilfe eines Kellerautomaten einfach. Das System muss bis zum Trennzeichen alles einkellern und danach - bei Gleichheit der Zeichen auf dem Band und im Keller - auskellern - fertig. Dies ist bestimmt und deterministisch. Für die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen. 

      In Aufgabe 2 haben wir kein Trennzeichen. Wir wissen also nicht, wo die Mitte ist. Wir können die Mitte auch nicht messen oder auf andere Art und Weise berechnen. Um das Palindrom zu erkennen, müssen wir also raten, wo die Mitte ist. Ein Algorithmus oder ein Automat, der eine Lösung rät oder für die gleiche Eingabe bei identischer Startvorgabe verschiedene Lösungen ausgibt, wird nichtdeterministisch genannt. Genau so etwas benötigen wir jetzt. Das System muss alles einkellern und an einer zu ratenden Stelle mit dem Auskellern beginnen. Wenn wir Glück haben, war es die richtige, sonst muss das System eben neu raten. 

      So unsinnig uns der Nichtdeterminismus für Computer auch erscheinen mag, er findet trotzdem seine Anwendung in der Welt der Informatik (Randomisierte Algorithmen, Quicksort). 

    • Lösungen Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

  • Turingmaschine als Akzeptor

    • Einleitungstext für den Grundkurs

      Im Baumarkt gibt es einen Automaten, der Schrauben und die passenden Anzahl Muttern eintütet. Zuerst wird die gewünschte Anzahl der Schrauben mit Mutter erfasst, dann die Schrauben und anschließend die Muttern in die Tüte gegeben. In eine Sprache übersetzt also: L = {Schrauben Muttern | n > 0}. Können wir einen Akzeptor konstruieren, der diese Sprache erkennt und akzeptiert?

      Ansatz: Für n ≤ 3 liefert der Graph des Akzeptors (ohne Zustandsübergänge in einen Fehlzustand) eine Lösung:

      Eine Erweiterung für größere n scheint auf den ersten Blick problemlos möglich, man muss nur neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht der Definition des Akzeptors. Diese Sprache kann also nicht von einem Akzeptor erkannt werden. 

      Einleitungstext für den Leistungskurs

      Unser Baumarkt erweitert sein Leistungsspektrum. Er bietet nun auch Schrauben, Unterlegscheiben und Muttern über den Automaten an (wow!). Die nachfolgende Generation soll zusätzlich auch Sprengringe (was das wohl ist) integrieren. In eine Sprache übersetzt also: L1 = {Schrauben Unterlegscheiben Muttern | n > 0} und L2 = {Schrauben Unterlegscheiben Sprengringn Muttern | n > 0}. Können wir einen Kellerautomat konstruieren, der diese Sprache erkennt und akzeptiert?

      Um es kurz zu machen: es wird uns nicht gelingen. Der Kellerautomat kann zwei Mengen vergleichen, versagt aber bei drei Mengen.

      Mit der Turingmaschine liegt jedoch ein Automatenmodell vor, welches unsere Probleme lösen kann. Die Änderungen im Vergleich zum Akzeptor sind

      • das Band wird beschreibbar und
      • der Lese-/Schreibkopf ist beidseitig bewegbar.

      Alan Turing entwickelte das mathematische Konzept einer universellen Maschine und stellt dies 1936 in der Arbeit "On Computable Numbers, with an Application to the 'Entscheidungsproblem'" vor. Dieser Beitrag gilt als die Geburtsurkunde der Wissenschaft Informatik. Turing selbst war entscheidend in weitere Projekte eingebunden, die heute der Informatik zugeordnet werden. Eine genaue Beschäftigung mit dem Leben und Wirken Turings erfolgt im Unterricht.  

      Bildquelle: gemeinfrei von WikiCommons: https://commons.wikimedia.org/w/index.php?title=File:Alan_Turing_az_1930-as_%C3%A9vekben.jpg&oldid=450320260

      Aufbau eines Funktionsmodells

      Arbeitsweise
      • Der Automat liest ein Zeichen vom Eingabeband.
      • In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen schreibt der Automat ein Zeichen auf das Band, wechselt in einen Folgezustand und bewegt den Lese-/Schreibkopf nach links/rechts oder gar nicht. 
      • Der Vorgang beginnt von vorn, solange noch Verarbeitungsschritte möglich sein.
      • Stoppt der Automat und befindet sich dann im Endzustand, so ist die Eingabe akzeptiert.
      Definition des Akzeptors - Automat ohne Ausgabe

      Eine Turingmaschine TM = (X, Z, Γ, δ, z0, $, ZE) ist ein endlicher Automat ohne Ausgabe. Dabei gilt:

      • X ... Eingabealphabet (nichtleere, endliche Menge)
      • Z ... Zustandsmenge (nichtleere, endliche Menge)
      • Γ ... Bandalphabet (nichtleere, endliche Menge)
      • δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) höchstens eine Ausgabe, eine Kopfbewegung (L, N, R) und einen Folgezustand zuordnet
      • z0 ∈ Z ist der Anfangszustand
      • $ ... Bandvorbelegungszeichen
      • ZE ⊆ Z ... Endzustandsmenge (nichtleere, endliche Menge)
      Beispiel für das Grundkurs-Problem: TM zur Erkennung der Sprache L(A) = {SchraubenMuttern | n > 0}

      TM = (X, Z, Γ, δ, z0, $, ZE) mit

        • X ={Schraube, Mutter}
        • Z = {q0, q1, q2, q3, q4, q5}
        • Γ ={$, Schraube, Mutter}
        • q0 ∈ Z ist der Anfangszustand
        • ZE = {q5}
        • δ als Tabelle 

          oder als Graph
      Beispiel für das Leistungskurs-Problem: TM zur Erkennung der Sprache L(A) = {SchraubenUnterlegscheibenMuttern | n > 0}

      TM = (X, Z, Γ, δ, z0, $, ZE) mit

        • X ={Schraube, Unterlegscheibe, Mutter}
        • Z = {q0, ..., q8}
        • Γ ={$, Schraube, Unterlegscheibe, Mutter}
        • q0 ∈ Z ist der Anfangszustand
        • ZE = {q8}
        • δ als Tabelle 

          oder als Graph
    • Informationen über das Leben und Wirken von Alan Turing (ab Minute 8:50) Externes Tool
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösung zur Aufgabe S. 8 Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösung der Übungsaufgaben zur TM Textseite
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

  • Formale Sprache und Grammatik - eingeschränkte Prüfungsrelevanz im Prüfungsjahr 2023 und 2024

    • Mit dem Akzeptor haben wir nun ein Automatenmodell kennengelernt, das (formale) Sprache erkennen kann. Im Folgenden frischen wir diese Erkenntnisse aus Klasse 10 auf und erweitern sie um eine visuelle Beschreibung für die Erzeugung von Sprache.

      In der Jahrgangsstufe 10 haben wir bereits natürliche und künstliche Sprachen analysiert und verglichen. Mithilfe der Begriffe Zeichen, Zeichenfolge, Wort, Satz, Alphabet, Grammatik, Sprache, Syntax und Semantik waren wir in der Lage, Eigenschaften von Sprache, wie etwa Mehrdeutigkeit, Fehlerfreundlichkeit, Universalität und Flexibilität zu untersuchen. Hilfssysteme natürlicher Sprachen (Esperanto, Klingonisch, Morsen, Blindenschrift) analysierten wir und versuchten uns in PROLOG.

    • Wiederholung der Begriffe aus der Jahrgangsstufe 10 Aufgabe

      Sollten Sie Probleme im Kreuzworträtsel gehabt haben, dann arbeiten Sie die Begriffe mithilfe von Inf-Schule: Sprache als Zeichensystem nach.

    • Sprache

      Schriftliche Sprache definieren wir als Zeichensystem zum Zweck der Kommunikation. Im weitesten Sinn werden neben den so genannten natürlichen Sprachen auch künstliche Sprachen (wie beispielsweise Welthilfssprachen oder Programmiersprachen in der EDV) sowie die Kommunikationsmittel der Tiere dazu gerechnet.

      Elemente einer Sprache

      Die (schriftliche) Sprache besteht aus

      • Zeichen
        kleinstes Element einer Sprache mit/ohne Bedeutung
      • Zeichenfolge
        Aneinanderreihung einzelner Zeichen mit/ohne Bedeutung
      • Alphabet
        Gesamtheit aller Zeichen der Sprache
      • Wort
        Aneinanderreihung einzelner Zeichen (Morphologie) mit einer Bedeutung (Wortsemantik)
      • Satz
        kleinste sprachliche vollständige Einheit mit einer Bedeutung (Satzsemantik), die nach festen Regeln (Syntax) aufgebaut ist
      • Grammatik
        Regelwerk zur Wort- (Morphologie) und Satzbildung (Syntax), Form der systematischen Sprachbeschreibung
      • Semantik
        Bedeutung der Zeichen, Worte und Sätze

      Sprachklassifikation

      Natürliche Sprachen ist die von Menschen gesprochene Sprache, die aus einer historischen Entwicklung entstanden ist. Künstliche Sprachen (Plansprache, Geheimsprache, ...) sind vom Menschen geschaffene Hilfssysteme und dienen der Codierung von Sprache z. B. für einen alternativen Übertragungsweg. 

      Natürliche Sprachen besitzen eine komplizierte Grammatik und eine mehrdeutige Semantik. Dies kann sich über die Hilfssysteme auch auf die künstlichen Sprachen übertragen.

      Formale Sprachen (z. B. Programmiersprachen) vermeiden diese strukturellen und semantischen Uneindeutigkeiten. Sie werden durch eine formale Grammatiken erzeugt. Die Untersuchung formaler Sprachen begann in den 1950er-Jahren durch Noam Chomsky.

    • Die Definition einer formalen Grammatik lässt sich mithilfe von Syntaxdiagrammen visualisieren. Wir kennen diese Syntaxdiagramme bereits von der Sprache SQL, als wir den SELECT-Befehl verwendet haben. Hier der Auszug aus der SQLite-Dokumentation:

  • Turingmaschine als Rechner

    • Die letzten Beispiele haben gezeigt, dass die Turingmaschine in der Lage ist Berechnungen auf Binärzahlen durchzuführen.

      Der Graph der hier gegebenen Turingmaschine teilt die auf dem Band stehende Binärzahl durch 2.

       

      Eine Funktion f heißt Turing-berechenbar, wenn es eine TM gibt, die f wie folgt berechnet:

      • im Startzustand mit dem Eingabewort w beginnend
      • durch definierte Zustandsübergänge in einem Endzustand hält und
      • das Wort v auf das Band geschrieben hat.

      Die Division einer Binärzahl durch 2 ist also Turing-berechenbar. Eine Berechnung ist eine schrittweise, nach bestimmten Regeln durchgeführte Manipulationen der Zeichen auf dem Band. Die Zeichen können Codierungen von Zahlen oder Zeichen darstellen. Damit beschreibt eine Turingmaschine eine Funktion = Programm = Algorithmus, die nach bestimmten Regeln Eingaben auf dem Band in Ausgaben auf das Band abbildet. 

    • Lösungen Verzeichnis
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

    • Church-Turing-These

      Alonzo Church und Alan Turing stellten eine These auf, die von den meisten Informatikern akzeptiert wird: 

      „Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“

      Das Modell der Turingmaschine mathematisiert damit die Begriffe Algorithmus und Berechenbarkeit.

      Ein Algorithmus ist nicht anderes als eine intuitiv berechenbare Funktion und somit eine Turingmaschine. Somit wird aus der "Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, mit der eine Vielzahl gleichartiger Aufgaben gelöst werden können und die Eigenschaften Endlichkeit, Ausführbarkeit, Terminiertheit, Eindeutigkeit und Allgemeingültigkeit hat" das mathematische Modell Turingmaschine, kurz: Programm = Algorithmus = Turingmaschine.


      Verhältnis von berechenbaren Funktionen (Turingmaschinen/Algorithmen) zu definierbaren Funktionen 

      Wie viele Funktionen kann man eigentlich definieren und wie viele davon berechnen? Beide Mengen sind unendlich groß. Lasst uns da mal zuerst über Unendlichkeit reden.


      Man kann mithilfe des systematischen Durchzählens beweisen, dass die Menge der berechenbaren Funktionen - also der Turingmaschinen - abzählbar unendlich groß ist. Die Menge der definierbaren Funktionen ist beweisbar überabzählbar unendlich groß. Damit ergibt sich die Konsequenz, dass es definierbare Funktionen gibt, die nicht berechenbar sind und demzufolge sich nicht mit Hilfe einer Turingmaschine lösen lassen.

      Es gibt definierbare Funktionen, die nicht algorithmisch lösbar sind. 

      Vertiefung: 

      Haben Sie mal ein Beispiel für so eine Funktion? 😀

    • Rechnet er noch, ist er abgestürzt? Was macht er denn? Aufgabe

      Ein Programm (GK: Scratch, LK: Java/Python) sucht magische Quadrate von Typ 3x3 auf eine logische, aber nicht sehr effektive Art. Es probiert einfach alle Varianten aus. 

      1. Schätze spontan die Zeit bis zur Ausgabe einer ersten Lösung für deinen Computer. Probiere erst dann das Programm aus.
      2. Beschreibe die prinzipielle Arbeitsweise des Programms.
      3. GK/Scratch: 
        1. Füge den Baustein "zeige_Variablen" als 3. Block in das Ereignis "Wenn grüne Flagge angeklickt" ein und prüfe den Programmablauf.
        2. Füge an einer geeigneten Stelle des Programms den Block "zeige_Stoppuhr_und_warte" ein, um die Laufzeit bis zum vollständigen Durchlauf abzuschätzen.
      4. LK/Java/Python:
        1. Lasse Dir mithilfe der Systemzeit die Laufzeit für einen Block so ausgeben, dass du daraus auf die Laufzeit des gesamten Programms mathematisch schließen kannst.
      5. Schätze die Laufzeit eines gleichartigen Programms für 4x4-Quadrate.

    • Beispiel für eine nicht berechenbare Funktion - das Halteproblem

      Lothar Collatz stellte 1937 folgendes Problem vor. Endet die Folge

      stets auf 1 für beliebige natürliche Zahlen a0?

      Beispiele:

      • a0 = 23: 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
      • a0 = 49: 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
      • a0 = 75: 75, 226, 113, 340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1

      Aufgabe: Entwickeln Sie unter Verwendung des Struktogramms ein Programm zur Berechnung der Collatz-Folge für beliebige Startwerte. Untersuchen Sie, ob der Algorithmus für verschiedene Startwerte stoppt.

    • Stopp-Tester

      Die entwickelte Software untersucht letztlich stets eine endliche Menge von Eingaben und prüft, ob die Folge auf Eins endet. Bisher hat man dies für alle Zahlen bis 20·258 (lt. Spiegel 2011) positiv beantworten können. Dennoch könnte schon die nächste Zahl das Programm in eine Endlosschleife führen. Sinnvoll wäre ein Programm, mit dessen Hilfe man für jedes beliebige Programm entscheiden kann, ob es mit jeder beliebigen Eingabe nach endlich vielen Schritten abbricht oder nicht?

      Dies dürfte kein Problem sein, da jedes Programm als eine Zeichenkette dargestellt werden kann und damit als Eingabe für das Stopp-Test-Programm dienen kann. Man könnte sogar für Testzwecke das Stopp-Programm selbst als Eingabe nutzen. Die Informatiker nennen dies "Selbstanwendbarkeitsproblem".

      Wie kann so ein Algorithmus aussehen?
      Sicherlich ist ein bestimmter Programmvorbau notwendig. Da jedoch zum Ende des Algorithmus die Ausgabe der Entscheidung ansteht, hat das - verbal beschrieben - Programm sicherlich folgende Gestalt, wobei stopp eine boolesche Variable ist, die vorher berechnet wurde.

      BEGIN
        {...}
        IF (stopp)
        THEN Ausgabe: "Das Programm ist selbststoppend."
        ELSE Ausgabe: "Das Programm ist nicht selbststoppend."
      END.


      Wenn dieses Programm existiert, dann könnte ein Programmierer den Quelltext aber auch ändern und so das Programm SELTSAM erschaffen:

      BEGIN
        {...}
        IF (stopp)
        THEN Ausgabe: "Das Programm ist selbststoppend."
             WHILE (true) DO //nichts
        ELSE Ausgabe: "Das Programm ist nicht selbststoppend."
      END.

      Ist Seltsam selbststoppend oder nicht?

      Angenommen es ist selbststoppend. Startet man nun das Programm SELTSAM und gibt ihm seinen Quelltext als Eingabe, so wird der gleiche Algorithmus abgearbeitet, wie beim Stopp-Test und damit die Variable stopp auf true gesetzt. Das Programm gibt nun aus, dass es selbststoppend ist, bleibt aber dann in der Endlosschleife hängen, ist also nicht selbststoppend. Damit steht es im Widerspruch zur Annahme.

      Angenommen es ist nicht selbststoppend. Auch hier wird das Programm SELTSAM wie oben beschrieben abgearbeitet und die Variable stopp erhält den Wert false. Der Algorithmus gibt nun aus "Das Programm ist nicht selbststoppend", hält aber anschließend. Damit ist aber wieder ein Widerspruch zur Annahme vorhanden.

      Da SELTSAM weder die Eigenschaft "selbststoppend" noch deren logische Negation besitzt, kann es nach den Gesetzen der Logik nicht existieren. Da es formal aus dem ersten Programm entwickelt wurde, kann es aber auch kein Programm Stopp-Tester geben.

      Resümee:

      Es ist nicht möglich von einem beliebigen Programm zu sagen, ob es nach endlich vielen Schritten stoppt oder nicht! Damit wurde (beweisbar) ein Problem gefunden, dass nicht mit Hilfe des Computers gelöst werden kann.

      Vertiefung/Visualisierung: 

       

  • Von-Neumann-Rechner

    • John von NeumannMit der Turingmaschine haben wir nun eine mathematisches Modell für eine universelle Maschine, die in der Lage ist, eine Vielzahl von Problemen durch eine Programmierung zu lösen. Turings Idee in ein reales Gerät zu verwandeln, war dann aber noch eine weitere Herausforderung.

      Im Mai 1941 gelang dies dem Berliner Ingenieur Konrad Zuse mit der Z3, dem ersten funktionsfähigem Digitalrechner der Welt. Kriegsbedingt erfuhr die Welt jedoch nichts von dieser revolutionären Erfindung. In anderen Ländern arbeiteten Forscher ebenfalls an der Entwicklung von "rechnenden Elektronengehirnen".

      John von Neumann erfuhr zufällig von der amerikanischen Entwicklung und erkannte den Nutzen für ein Projekt, in das er involviert war - dem Manhattan-Projekt. Im Nachgang abstrahierte er alle ihm bekannten Entwicklungen und beschrieb 1945 in First Draft of a Report on the EDVAC die bis heute gültige prinzipiellen Architektur eines Computers.

      Bildquelle: WikiCommons (https://commons.wikimedia.org/wiki/File:JohnvonNeumann-LosAlamos.jpg)
      Unless otherwise indicated, this information has been authored by an employee or employees of the Los Alamos National Security, LLC (LANS), operator of the Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396 with the U.S. Department of Energy. The U.S. Government has rights to use, reproduce, and distribute this information. The public may copy and use this information without charge, provided that this Notice and any statement of authorship are reproduced on all copies. Neither the Government nor LANS makes any warranty, express or implied, or assumes any liability or responsibility for the use of this information.

    • Video aus Medienstelle (FWU/Hagemann):

      • Meilensteine der Kommunikation: Zuse, Babbage und der Computer
      • Geschichte der Computer
    • Geschichte der Computer - Abschnitt: Die ersten Computer der Welt Externes Tool
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

    • Exkurs: Vorstellung historischer Hardware

      • Rechnersysteme: Abakus, Addiator, LC 80, Poly 880, Z 1013, Mainboards
      • Speichermedien: Lochkarte/-streifen, Magnetband, Disketten, Festplatten, Exoten
    • Erarbeitung von-Neumann-Architektur Aufgabe

      Erarbeiten Sie unter Verwendung der Lehrbücher Informatik 2 Schöningh S. 234ff. und Oldenbourg S. 88ff. sowie des Arbeitsblattes den Aufbau und die acht Prinzipien der von-Neumann-Architektur.

    • Die von-Neumann-Architektur mit MOPS begreifen

      (in Abhängigkeit vom Wissensstand aus Klasse 10)

    • Die von-Neumann-Architektur mit Johnny begreifen

    • AB Johnny Lösungen Datei
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösung 4_3a-c Datei
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

    • Exkurs für Freaks: Maschinennahe Programmierung am LC80

    • Architekturnachteil und Alternative

    • Von-Neumann-Flaschenhals Aufgabe

      Eine Kritik am von-Neumann-Konzept wurde 1977 von Turing-Award-Preisträger John W. Backus geübt: 

      „Sicherlich muss es auf eine weniger primitive Art möglich sein, große Änderungen auf dem Speicher durchzuführen, als riesige Mengen von Datenwörtern vor und zurück durch den Von-Neumann-Flaschenhals zu schieben. Diese Röhre bildet nicht nur einen wörtlichen Flaschenhals für den Datenverkehr eines Problems [...], es ist ein intellektueller Flaschenhals, der uns an ein Denken „ein Datenwort auf einmal“ gebunden hat, anstatt uns zu ermutigen, in den Begriffen der größeren konzeptuellen Einheiten der vorliegenden Aufgabe zu denken.“

      Ermitteln Sie mithilfe eines der bereits analysierten MOPS- oder Johnny-Programme, was mit dem Begriff "von-Neumann-Flaschenhals" gemeint ist. Recherchieren Sie Möglichkeiten, das Problem des Flaschenhalses zu reduzieren.


    • Der Prozessor fordert während der Abarbeitung des Programms die Programmbefehle aus dem Speicher über den Datenbus an, muss aber auch die zu verarbeitenden Daten vom Speicher holen und wieder im Speicher ablegen. Teilweise müssen Operanden aus dem Speicher in den Prozessor nachgeladen werden. Das Rechenwerk ist also zum Warten verdammt. 

      Wie man damit leicht einsieht, ist das Verbindungssystem zwischen dem Prozessor und dem Speicher ein Engpass, der auch als von-Neumann-Flaschenhals bezeichnet wird.


      Illustration des Flaschenhalses am Polycomputer 880 im Einzelschrittbetrieb.

      Da zusätzlich die Geschwindigkeit der peripheren Elemente (Speicher, I/O-Einheit) heutzutage deutlich kleiner ist als die Verarbeitungsgeschwindigkeit des Prozessors, kommt es immer wieder zu unnötigen Wartezeiten des Prozessors.

      In der Praxis versucht man diesen Effekt abzuschwächen. Eine Möglichkeit ist der Einsatz von Zwischenspeichern (Cache) im Prozessor (L1) oder vor dem Prozessor (L2). Diese können die Daten aus dem Speicher schon vorsorglich einlesen. 

      Die Kritik von Backus zielt aber noch in eine weitere Richtung. Aufgrund der strukturellen Vorgabe kann ein von-Neumann-Rechner stets nur eins nach dem anderen tun. Dies ist aus Backus Sicht eine Einschränkung auch des Denkens.

    • Hardvard-Architektur: Vergleich, Vor- und Nachteile (nur im LK) Link/URL

      Einer der ersten Computer, der Mark I, wurde in Kooperation zwischen IBM und der Harvard-Universität entwickelt und 1944 in Betrieb genommen wurde. Er verwendete eine Rechnerarchitektur die sich von der von-Neumann-Architektur unterscheidet.

      Ermitteln Sie mithilfe der angegebenen Website Gemeinsamkeiten und Unterschiede in der Architektur. Leiten Sie jeweils Vor- und Nachteile ab.


  • Dieser Abschnitt

    Speichern, Rechnen und Vergleichen mit Logikgatter

    • George BoolDass das Binärsystem für Rechenautomaten besonders günstig ist, erkannten Konrad Zuse (Deutschland) und George Stibitz (USA) in den 1930er Jahren. Die Mathematik dafür wurde von George Boole (USA) in der Mitte des 18. Jahrhunderts entwickelt. 

      Versuchen wir nun, Elemente aus dem theoretische Modell der von-Neumann-Architektur mithilfe der (booleschen) Grundbausteine digitaler Systeme - der sog. Logikgatter - zu entwickeln.

      Bildquelle: George Boole, See page for author, Public domain, via Wikimedia Commons

    • Grundlagen Logikgatter entdecken

      (in Abhängigkeit vom Wissensstand aus Klasse 10)

    • Lösungen Verzeichnis
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs
    • Lösungen Verzeichnis
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

    • Elemente der von-Neumann-Architektur mit Logikgatter entwickeln

    • Lösungen Verzeichnis
      Eingeschränkt Nicht verfügbar, es sei denn: Sie sind in Hempel: 11 GK/LK - A Relationale Datenbanksysteme Kurs

    • Probleme beim Rechnen

    • Übungen zu Gattern zur Umsetzung der von-Neumann-Architektur Aufgabe

      Durch das Zusammenschalten von Logikgattern ist es uns gelungen, Elemente der von-Neumann-Architektur hardwarenah zu entwickeln. Schauen wir, ob es vielleicht irgendwo Probleme geben könnte.

      1. Geben Sie die Elemente der von-Neumann-Architektur an, die wir hardwarenah aus Grundgattern entwickeln könnten.
      2. Im Rechenwerk finden Berechnungen und Vergleiche mithilfe des Binärsystems statt.
        1. Informieren Sie sich im Lehrbuch über die Codierung positiver und negativer ganzer Zahlen.
        2. Erläutern Sie die Begriffe Einer- und Zweierkomplement.
        3. Begründen Sie, dass Computer bei der Additionen zweier positiver Zahlen eine negative Zahl erhalten können.
        4. Starten Sie das Java-Programm Zahlen.java im Java-Editor und testen Sie die Funktionalität für die Zahlen 0, 30, -4, 120, -120. Begründen Sie das Verhalten des Programms.
        5. Gruppe A:
          1. Entwickeln Sie in LogicSim je eine Schaltung für die Bildung des Einerkomplements und des Zweierkomplements einer 4-Bit breiten Binärzahl.
          2. Analysieren Sie die Schaltung GruppeA.lsim. Ermitteln Sie, was diese Schaltung leistet.
        6. Gruppe B:
          1. Johnny verfügt über den Befehl TST. Ermitteln Sie, worauf der Test erfolgt.
          2. Entwickeln Sie in LogicSim je eine Schaltung für Testung eines Bits bzw. eines Bytes wie in Johnny. 
          3. Analysieren Sie die Schaltung GruppeB.lsim. Ermitteln Sie, was diese Schaltung leistet.

    • Computer müssen auch negative ganze Zahlen darstellen können. 

      Eine Idee besteht darin, die Bitfolgen der natürlichen Zahl zu negieren (Einerkomplement). Wenn beispielsweise 6d = 0110b gilt, dann wäre im Einerkomplement -6d = 1001b.
      Allerdings gibt es dann zur Zahl 0 eine "negative" Null: 0d = 0000b, -0d = 1111b. Die Null ist aber einmalig, zur ihr darf es kein "Gegenstück" geben.

      Daher verwendet man das sog. Zweierkomplement. Die negierte Binärzahl wird einfach inkrementiert; aus 6d = 0110b wird -6d = 1010b. Addiert man beide Binärzahlen, so erhält man  sinnvollerweise Null.

      Im Zweierkomplement sind alle Binärzahlen, bei denen das höchste Bit den Wert 1 hat, negativ. Mit vier Bit lassen sich nun die Zahlen von -8d = 1111b bis 7d = 0111b bilden. Inkrementiert man die Binärdarstellung von 7d = 0111b, so erhält man 1000b = -8. Der Zahlbereich der ganzen Zahlen ist somit als Zahlenkreis darstellbar. Dies erklärt den Fehler im Java-Programm. Der Programmierer muss also stets auf den Wertebereich des Datentyps achten, um keine fehlerhaften Berechnungen durch Überlauf zu erzeugen.

      Die Abbildung reeller Zahlen auf dem Computer ist defacto unmöglich. Man nutzt ein Hilfskonstrukt, die Gleitkommadarstellung. Diese ist lässt jedoch nur eine endlich und diskret Menge an Zahlen zu, d. h. zwischen zwei Zahlen ist eine Lücke. Die Differenz zu nächst möglichen Gleitkommazahl ist ein Fehler, der sich bei umfangreichen Rechnungen auch sehr schnell summieren und dann zu ernsthaften Konsequenzen führen kann. 

      Zum Ausprobieren: Addiert in Java/Python einfach mal 0.1 und 0.2.