I-TI04-HOME

  1. Einführung

  2. Formale Sprachen - Grundbegriffe

  3. Abzählbare und aufzählbare Sprachen

  4. Testfragen und Übungsaufgaben


I-TI04 Theoretische Informatik WS04
VL4: Automaten - formalisiert 2

 
    Achtung : Skript gibt den mündlichen Vortrag nur teilweise wieder !!!
                        

AUTHOR: Gerd Döben-Henisch
DATE OF FIRST GENERATION: March-29, 2004
DATE OF LAST CHANGE: Nov-24, 2004
EMAIL: doeben_at_fb2.fh-frankfurt.de



1. Einführung

Nachdem nun eine erste Formalisierung einer Turingmaschine vorliegt, sollen jetzt die Begriffe akzeptierte Sprache, Entscheidungsverfahren, entscheidbare Sprache , und entscheidbar eingeführt werden. Diese Begriffe setzen aber Begriffe aus dem Bereich der formalen Sprachen voraus. Daher hier jetzt die wichtigsten Begriffe aus dem Bereich der formalen Sprachen.


START



2. Formale Sprachen - Grundbegriffe


(Für eine sehr gute Einführung in das Thema formale Sprachen siehe z.B. [G.ROZENBERG/ A.SALOMAA 1997:Bd.1:Kap.1])

Formale Sprachen repräsentieren Systeme von Ausdrücken, die aus einfachen Grundelementen (Zeichen, Symbolen, Buchstaben) gebildet werden. Um eine formale Sprache L zu definieren, muss man im wesentlichen festlegen, welche Kombinationen von Grundelementen (:= das Alphabet) erlaubt sein sollen. Eine Möglichkeit, um solch eine Beschreibung realisieren zu können, besteht in der Angabe einer formalen Grammatik G für eine Sprache L, so dass gilt L(G) ist die Sprache, die von G entweder erzeugt oder akzeptiert wird. Formale Grammatiken kann man nämlich dazu benutzen, um korrekte Ausdrücke der Sprache L zu erzeugen/ generieren/ synthetisieren, oder aber um von einem vorgelegten Ausdruck w sagen zu können, ob er zur Menge L(G) gehört; dies nennt man dann den Ausdruck w parsen/ analysieren/ erkennen/ akzeptieren.

Es folgen jetzt eine Reihe von Begriffen, die benötigt werden, um über formale Sprachen sprechen zu können.

  1. Alphabet [A]: das Alphabet bildet die endliche Menge der Grundelemente einer Sprache L. Sei A solch ein Alphabet. Wenn x A dann heisst x gewöhnlich ein Buchstabe ('letter') oder Symbol ('symbol') oder Zeichen ('sign'). Vielfach wird statt dem Buchstaben 'A' zur Abkürzung für Alphabet auch der Buchstabe 'V' (engl. 'vocabulary') oder Σ benutzt:
    ALPHABET(A) gdw A ist eine endliche Menge.


  2. Die Operation der Verkettung '^' (auch '+' oder Juxtaposition) kann man definieren als die Vereinigung von zwei endlichen Folgen, wobei die Indizes des "nachfolgenden" Tupels um die Länge des vorausgehenden Tupels "verschoben" werden. Seien a und b zwei Elemente aus A, dann schreibt man für die Konkatenation 'a^b' oder auch 'a+b' oder einfach 'ab'.


  3. Wort über A: Die Aneinanderfügung ('Verkettung', 'Konkatenation') von Zeichen aus A ergibt eine Zeichenkette ('string') über A bzw. ein Wort ('word') über A. Mengentheoretisch kann man ein Wort über A auffassen als eine endliche Folge auf der Menge A --Abkürzung: FSON(w,A)--, z.B. 'aaa' := <a1,a2,a3, >, 'abb' := <a1,b2,b3, >. Sofern es nicht zu Mehrdeutigkeiten führt, wird im folgenden immer die Kurzschreibweise für Worte benutzt, ohne die Indizes:

    WORD(w,A) gdw FSON(w,A)

    z.B. WORD(<a1,b2,b3, >,{a,b}) oder kurz: WORD('abb',{a,b})


  4. Länge eines Wortes w |w|: Die Länge eines Wortes w über dem Alphabet A wird mit |w| bezeichnet.


  5. Leeres Wort [ε]: Es gibt genau ein Wort der Länge 0, das ist das leere Wort 'ε' (in der Literatur auch als kleines Lambda (λ)). Das leere Wort ε entsteht aus einem Alphabet A indem man ein Tupel bildet, das keine Werte enthält, also ε = <Ø>.

  6. A*: Die Menge A* der Wörter über dem Alphabet A kann man induktiv wie folgt definieren:

    1. A C A*

    2. x,y ∈ A* ==> x^y &isin A*

    3. Nur (i) und (ii) gelten.

    (Für eine Alternative siehe weiter unten)

  7. Menge der nichtleeren Wörter über A [A+]: A+ = A* \ {ε}

  8. Sprache, formale Sprache: Jede Teilmenge von A* wird als Sprache oder formale Sprache bezeichnet.

    LANGUAGE(L) gdw (E:A)( ALPHABET(A) & L C A* ).

  9. Man kann die vorausgehenden einzelnen Feststellungen auch in einer mathematischen Struktur zusammenfassen, die Halbgruppe mit neutralem Element oder Monoid genannt wird:

    Halbgruppe mit neutralem Element (Monoid) <A*, ^ >: Mittels der Menge A* und der Operation Konkatenation '^' lässt sich jetzt eine Struktur <A*, ^ > als Halbgruppe mit neutralem Element (Monoid) definieren, die folgende Eigenschaften haben soll:

    Für alle x,y A* soll gelten:

    1. x ^ y = xy in A* (Abgeschlossenheit)

    2. (x ^ y ) ^ z = x ^ ( y ^ z ) = xyz (Assoziativität)

    3. ε ^ x = x ^ ε = x (Neutrales Element)

    Damit kann man vereinbaren: wenn w, u1,u2, v Worte über einem Alphabet A sind, dann gilt:

    1. wn = ww ...w (n-mal) (eine n-fache Konkatenation)

    2. speziell gelte w0 = ε.

    3. |w| := Länge eines Wortes; Anzahl der Zeichen in dem Wort w, wobei jedes Zeichen sooft gezählt wird, wie es vorkommt; mit den zusätzlichen Eigenschaften:

    4. |ε| = 0

    5. |u1,u2| = |u1| + |u2|

    6. |wn| = n * |w|

    7. v ist ein Teilwort von w wenn w = u1vu2. Wenn u1 = ε dann ist v ein Präfix, ist u2 = ε dann ist v ein Suffix. Jedes Wort w ist trivialerweise Teilwort, Präfix und Suffix von sich selbst; ebenso gilt dies für das leere Wort ε.


    8. Seien A,B Teilmengen von ALPH* mit ALPH als einem Alphabet, dann sind A und B Sprachen. folgende Begriffe werden benötigt:

      1. A B = { x | x A oder x B }

      2. A B = { x | x A & x B }

      3. c(A) (auch Querstrich über A) = ALPH* - A

      4. AB = { xy | x A & y B }

      5. A0 = {ε}

      6. A1 = A

      7. An+1 = AAn

      8. AiAj=(Ai)+j

      9. A* = U (∀n n ∈ Nat & n ≥ 0) An

      10. A+ = U (∀n n ∈ Nat & n ≥ 1) An



    Beispiele für Alphabete:

    1. A = {|} unärer Strichcode zur elementaren Darstellung natürlicher Zahlen


    2. A = {0,1} zur Darstellung von Binärzahlen


    3. A = {0,1,...9} zur Darstellung von ganzen Dezimalzahlen


    4. A = {a,b,...,z,A,B, ...,Z} zur Darstellung von Wörtern aus Gross- und Kleinbuchstaben


    5. A = ASCII (übernommen von Stefan Lenz).

      ASCII-Code

      Der ASCII-Code ist eine standardisierte Zeichen-Definition für den Datenaustausch zwischen Informatik-Systemen. ASCII bedeutet American Standard Code for Information Interchange. Es ist sozusagen «der kleinste gemeinsame Nenner» aller Informatik-Systeme. ASCII wurde 1968 mit der Intention oder Absicht entwickelt, Datenübertragungen zwischen divergierenden Hardware- und Softwaresystemen zu standardisieren.

      Standard ASCII-Code

      Alle Zeichen im Bereich von 0 bis 127 gehören zum Standard ASCII-Zeichensatz. Dieser Standardzeichensatz von 0 bis 127  ist in der IT-Welt stark normiert. Die Zeichen werden aus einem 1 Byte dargestellt, das heisst es sind maximal 256 Zeichen möglich, auf PC-Systemen kommt der erweiterte ASCII-Zeichensatz (0 bis 255) zum Einsatz.

      Die ASCII-Zeichen 0 bis 32 werden als Steuerzeichen bzw. Formatierungszeichen für Ein- und Ausgabegeräte verwendet.

      Erweiterter ASCII-Code

      Jeder Satz von Zeichen, der den ASCII-Werten zwischen dezimal 128 und 255 (hexadezimal 80 bis FF) zugeordnet ist. Die Zuordnung spezifischer Zeichen zu den erweiterten ASCII-Codes variieren zwischen Computern und zwischen Programmen, Schriften oder grafischen Zeichensätzen. Erweitertes ASCII erhöht auch die möglichen Funktionen, da sich mit den 128 zusätzlichen Zeichen z. B. Akzentbuchstaben, Umlaute, grafische Zeichen und spezielle Symbole darstellen lassen.


    6. A = EBCDIC (übernommen von ASCII-EBDIC).

      EBCDIC

      Der Enhanced Binary Coded Decimal Interchange Code (gesprochen: eb-sih-dik) ist die von IBM für Mainframes benutzte proprietäre Zeichenkodierung. Es ist ein 8-bit-Code, so dass 256 Steuerzeichen, Ziffern, Buchstaben und Sonderzeichen binär dargestellt werden können. Erstmals eingesetzt wurde er auf Lochkarten (engl.: punched card) in den 60er Jahren des vorigen Jahrhunderts. Für die Internationalisierung wurden mehrere verschiedene Code-Tabellen herausgegeben, nur in der so genannten International Reference Version (IRV) sind alle Zeichen des ISO/IEC 646, der die Zeichen des 7-bits--ASCII standardisiert, enthalten. Der ursprüngliche BCD-Code beschränkte sich durch die Verwendung von 4 bits auf die Darstellung des Zahlenbereiches von 0 bis 15.




    START



    3. Abzählbaren und aufzählbare Sprachen


    Abzählbar ist eine Menge M, wenn man ihre Elemente entsprechend einer Ordnung wie im Beispiel der natürlichen Zahlen Nat anordnen kann: 0-tes Element, erstes Element, ... Man kann also vereinbaren:


    ABZÄHLBAR(m) gdw (E:f)( f: Nat ---> m & SURJEKTIV(f) )


    ÜBERABZÄHLBAR(m) gdw ¬ABZÄHLBAR(m)


    Alle endlichen Mengen sind mit dieser Definition trivialerweise abzählbar. Wie verhält es sich mit unendlichen Mengen?


    In der Mengenlehre unterscheidet man grundsätzlich zwischen abzählbar unendlichen und überabzählbar unendlichen Mengen.


    Kardinalität: Sei x eine Menge, dann wird durch |x| die Kardinalität der Menge (x die Anzahl der Elemente) repräsentiert.


    Zwei Mengen x1 und x2 haben die gleiche Kardinalität, wenn es eine 1-zu-1-Abbildung zwischen x1 und x2 gibt.


    Seien x, y endliche Mengen und sei x C y; dann gilt |x| ≤ |y|.


    Abzählbar unendliche Menge: Als Prototyp für eine abzählbar unendliche Menge ('countably infinite') dient die Menge der natürlichen Zahlen Nat. Mengen mit der gleichen Kardinalität wie die natürlichen Zahlen Nat gelten ebenfalls als abzählbar unendlich. Es gibt viele Mengen, die gleichmächtig sind mit der Menge Nat, z.B.: die Menge der geraden oder die Menge der ungeraden Zahlen, die Menge der Zweierpotenzen, die Menge der rationalen Zahlen usw.


    Den Aufweis, dass die Menge der rationalen Zahlen abzählbar unendlich ist, führte als erster Georg Cantor mit dem sogenannten ersten Cantorschen Diagonalverfahren.


    Eine Menge M heisst (höchstens) abzählbar ('countable') falls sie endlich ist oder abzählbar unendlich.


    Überabzählbar unendlich: Schon CANTOR entdeckte, dass es im Bereich der unendlichen Mengen Unterschiede bzgl. der Abzählbarkeit gibt. So konnte CANTOR in einem Brief vom 7.Dezember 1873 einem Freund einen Beweis mitteilen, dass die Menge der reellen Zahlen Rel nicht-abzählbar ist, da sie mächtiger ist als die Menge der natürlichen Zahlen; die Menge der rellen Zahlen Rel wird als überabzählbar unendlich bezeichnet. Für den Beweis der Nichtabzählbarkeit der rellen Zahlen genügt es, einen Abschnitt der reellen Zahlen zwischen zwei beliebigen Zahlen [0,1] zu betrachten und zu verabreden, dass alle reellen Zahlen in diesem Intervall als unendliche Dezimalbrüche darzustellen sind. Indirekt angenommen, es gäbe zu diesen Zahlen eine Abzählung, dann könnte man diese Zahlen so anordnen, dass man jeder dieser Zahlen eindeutig eine natürliche Zahl zuordnen könnte. Welche Anordnung man aber auch immer wählen mag, aufgrund der Anordnung generiert man eine relle Zahl, die nicht in der Abzählung vorkommt. Damit ist die Nichtabzählbarkeit bewiesen.


    Unter anderem kann man dann auch beweisen, dass jede Teilmenge von Rel von gleicher Kardinalität ist wie Rel insgesamt.


    Satz: Die Menge aller Wörter A* über einem Alphabet A ist abzählbar (unendlich). Der Beweis ordnet alle Wörter einmal der Länge nach an, und innerhalb der Länge lexikographisch. Dann kann man jedem Element eine natürliche Zahl zuordnen.


    Satz: Jede Teilmenge M' einer abzählbaren Menge M ist abzählbar. Für den Fall, dass M endlich ist, ist der Nachweis trivial. Ist M nicht endlich, dann gibt es zu M eine surjektive Abbildung f: Nat ---> M. Für die Abzählbarkeit von M' benötigt man eine Funktion f': Nat ---> M'. Da M' ene Teilmenge von M ist und M = rn(f) gilt M' C rn(f); dann ist f' = f |\ M'.


    Satz: Da für jede Sprache L zu einem Alphabet A gilt, L C A*, folgt aus den beiden vorausgehenden Sätzen, dass jede Sprache L über dem Alphabet A abzählbar ist.


    Aufzählbar (rekursive aufzählbar, semientscheidbar): eine Menge M ist aufzählbar, falls es eine surjektive Funktion f: Nat ---> M gibt, und f ist eine turingberechenbare Funktion.


    Aufzählung von M: ist die Menge M aufzählbar und ist f die turingberechenbare Funktion zu M, dann ist die Folge <f(0), f(1), ... > eine Aufzählung von M


    Satz: Jede endliche Menge ist aufzählbar. Sei M eine endliche Menge. Eine Turingmaschine m bildet eine Folge von Zahlen '|', '||', ... solange, bis alle Elemente der Menge M abgearbeitet sind.


    Satz: Die Menge aller Wörter A* über einem Alphabet A ist aufzählbar. Eine Turingmaschine m bildet eine Folge von Worten aus A nach der Länge und lexikographisch geordnet.


    Satz: Jede aufzählbare Menge ist auch abzählbar



    START



    4. Testfragen und Übungsaufgaben

    1. Was ist ein Alphabet?

    2. Wie definiert man eine formale Sprache?

    3. Was verstehen Sie unter der Mächtigkeit bzw. auch Kardinalität einer Menge M?

    4. Wie verhält sich die Mächtigkeit eines Alphabetes A --also |A| -- zu Mächtigkeit der Menge A* -- also |A*| -- ?

    5. Sei H eine Halbgruppe mit einem freien Element geschrieben: <A*, ^ >. Seien x,y zwei Worte über A*, also x,y A*.Erklären sie, was in diesem Kontext die Begriffe Abgeschlossenheit, Assoziativität und Neutrales Element bedeuten.

    6. Sei v ein Teilwort von w und w = u1vu2. Erklären Sie, was ein Präfix und was ein Suffix ist.

    7. Seien A,B Teilmengen von ALPH mit ALPH ={a,b,c,0,1} und A = {a,b,c} sowie B = {0,1}. Wie lauten die Ergebnisse der folgenden Operationen:

      1. A* ∪ B*

      2. A* B*

      3. c(A*)

      4. c(B*)

      5. A*B*

      6. A*0

      7. A*1

      8. A*n+1

      9. A*iA*j

      10. A+

      11. B*

      12. B+

      13. ALPH*

      14. ALPH+

    8. Was ist der Unterschied zwischen abzählbar unendlich und überabzählbar unendlich?

    9. Geben Sie konkrete Beispiele für abzählbare Mengen und überabzählbare Mengen.

    10. Was ist der Unterschied zwischen abzählbar und aufzählbar?

    11. Konstruieren Sie eine Turingmaschine, die die Menge der natürlichen Zahlen in Binärdarstellung aufzählt.


    START