K5 Buch für die Informatik PDF

Preview

Summary

Download K5 Buch für die Informatik PDF

Description

Die theoretische Informatik beschäftigt sich mit der Fundierung des Algorithmusbegriffs, untersucht die Leistungsfähigkeit von Algorithmen und erforscht die prinzipiellen Grenzen des Computers beim Lösen von Problemen.

440

Theoretische Informatik

5.1

I

Linguistik: Sprachwissenschaft

Formale Sprachen und Automaten

5.1.1 Formale, natürliche und Programmiersprachen Die Theorie der formalen Sprachen und die Automatentheorie nehmen in der theoretischen Informatik breiten Raum ein. Dabei werden die Einsichten vermittelt, die zum Verständnis von Anwendungen in verschiedenen anderen Gebieten erforderlich sind. Dies gilt beispielsweise für die Linguistik, den Compilerbau und die künstliche Intelligenz. Die Wortwahl formale Sprache unterstreicht die Abgrenzung sowohl zu den natürlichen als auch zu den Programmiersprachen. In formalen Sprachen spielt die Semantik, d. h. die Bedeutung der Sätze einer Sprache, keine Rolle. In der Programmiersprache Turbo Pascal bedeutet for i:= 1 to 5 do writeln('Hallo'); dass das Wort Hallo am Bildschirm 5-mal untereinander geschrieben wird. Das for-to-do-Sprachelement hat die Bedeutung eines Zyklus. Die darin enthaltene Wertzuweisung folgt der Semantik von :=. Für die Definition der Semantik von Programmiersprachen sind verschiedene Zugänge entwickelt worden, die hier jedoch nicht betrachtet werden.

I

5.1.2 Syntax und Ableitungsbaum Die Theorie der formalen Sprachen befasst sich ausschließlich mit dem syntaktischen Aspekt. Die Syntax einer Sprache ist die Lehre vom Satzbau. Sie umfasst sämtliche grammatikalische Regeln, deren Anwendungen zu korrekt gebauten Sätzen führen. Auch natürliche und Programmiersprachen besitzen eine Syntax. Für englische Sätze gilt die SPO-Regel, die die Reihenfolge Subjekt – Prädikat – Objekt vorschreibt. Das Beispiel führt zu der Frage, wie grammatikalische oder syntaktische Regeln anzuwenden sind. Dafür gibt es zwei Herangehensweisen: 1. Erzeugung (Synthese) eines Satzes 2. Erkennung (Analyse) eines Satzes Der Satz „She loves soccer players.“ ist syntaktisch korrekt, denn die Analyse gemäß der SPO-Regel verläuft positiv:

Formale Sprachen und Automaten

She

loves

soccer players

Subjekt

Prädikat

Objekt

.

Satz Ein „Konstrukteur“ dieses Satzes geht umgekehrt vor: Satz

Subjekt

Prädikat

Objekt

She

loves

soccer players

.

Die für die Analyse bzw. Synthese eines Satzes verwendete Darstellung heißt Baum. Sogenannte Ableitungsbäume entstehen aber nur dann, wenn sämtliche Regeln eine spezielle Form besitzen (b Abschnitte 5.1.3 und 5.1.7: kontextfreie Grammatik). Die Satzbauregel für englische Sätze lautet in Kurzform Lies: „Ein SATZ ist definiert als eine Folge aus SUBJEKT, PRÄDIKAT, OBJEKT und einem anschließenden Punkt.“ Diese eine Regel genügt noch nicht, denn sie gibt keine Auskunft darüber, wofür SUBJEKT, PRÄDIKAT und OBJEKT stehen. Dies legen die folgenden Regeln fest:

Damit können insgesamt 18 Sätze gebildet werden, wobei ein Satz wie „She kicked soccer players.“ daran erinnert, dass die Semantik wirklich keine Rolle spielt.

5.1.3 Formale Grammatik Offensichtlich gelingt es immer dann (wenigstens) einen Ableitungsbaum für einen gegebenen Satz anzugeben, wenn in jeder Regel auf der linken Seite genau eine zu erklärende syntaktische Einheit steht. Syntak-

(„ist definiert als“) wird oft auch das Zeichen ::= benutzt.

441

442

Theoretische Informatik

tische Einheiten werden in der Theorie formaler Sprachen Nichtterminale genannt. Für sie besteht Erklärungspflicht, d. h., jedes Nichtterminal muss die linke Seite wenigstens einer Regel bilden. Nichtterminale kommen im Satz selbst nicht vor. Sie haben lediglich eine metasprachliche Aufgabe, indem sie helfen, die Struktur von Sätzen der zu definierenden Sprache exakt zu beschreiben. Im Gegensatz dazu sind Terminale die wirklichen lexikalischen Bausteine eines Satzes. Sie werden an der entsprechenden Stelle platziert und mit anderen Terminalen verbunden. Seien N die Menge der Nichtterminale und T die Menge der Terminale, dann gilt für obiges Beispiel: N = {SATZ, SUBJEKT, PRÄDIKAT, OBJEKT } und T = {She, He, loves, kicked, likes, soccer_players, swimming, the_ball,.}. Es ist üblich, für Nichtterminale große Buchstaben zu schreiben, während die Schreibweise von Terminalen nicht beeinflussbar ist, da sie mit der Aufgabenstellung vorgegeben ist. Bei Programmiersprachen wird dies vom „Design der Sprache“ vorgeschrieben. In den folgenden Beispielen werden meist Kleinbuchstaben als Terminalsymbole benutzt. Im letzten Beispiel spielt das Nichtterminal SATZ eine besondere Rolle. Es bildet in jedem Falle die Wurzel des Ableitungsbaumes und heißt deshalb Axiom, Satz-, Spitzen- oder Startsymbol s. Eine Satzerzeugung beginnt also stets beim Spitzensymbol und endet, wenn sämtliche Nichtterminale durch Terminale ersetzt worden sind. Anstelle der Baumform gibt es noch folgende Schreibweise: Achtung! Der Ableitungspfeil „geht unmittelbar verwechselt werden mit dem Definitionssymbol in den grammatikalischen

liebig vielen Nichtterminalen und beliebig vielen Terminalen – auch gemischt und in beliebiger Reihenfolge – bestehen. Da die Ableitung eines Satzes – manchmal auch Herleitung genannt – ein aus s abgeleiteter Satz. Der Satz „He likes swimming.“ ist aus s=SATZ ableitbar, denn

Die vorangegangenen Betrachtungen münden nun in die Definitionen einiger abstrakter Begriffe. Eine formale Grammatik G = (N, T, P, s) ist ein 4-Tupel, wobei die verwendeten Symbole die folgenden Bedeutungen besitzen: – N eine endliche Menge von Nichtterminalen; b auch Definition einer formalen Grammatik im Abschnitt 3.1.4

– P eine endliche Menge von Regeln oder Produktionen der Form Nichtterminal besteht; und schließlich

Formale Sprachen und Automaten

Der amerikanische Informatiker Noam Chomsky (geb. 1928) hat formale Grammatiken erstmals ab 1956 verwendet. Um diese Leistung zu würdigen, werden formale Grammatiken (dieser Art) auch Chomsky-Grammatiken genannt. Sei G1 = (N1, T1, P1, s1) eine formale Grammatik, mit N1 = {GZAHL, ZIFFER, GZ }, T1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},

B

Mit dieser formalen Grammatik können alle geraden Zahlen (als Wörter) erzeugt bzw. erkannt werden.

s1 = GZAHL. senkrechten Striche gestatten eine Kurzschreibweise für die zehn Regeln Die im Beispiel eingeführte Schreibweise inklusive der Verkürzungen für alternative Regeln geht auf BaCkus zurück und wird Backus-Normalform oder Backus-Naur-Form, kurz BNF, genannt. Kommen noch weitere Verkürzungen zum Einsatz, spricht man von einer erweiterten BNF, kurz: EBNF. Für die Syntaxdefinition von Programmiersprachen werden auch gern Syntaxgraphen (Syntaxdiagramme) benutzt.

B

B

Syntaxgraphen für obige Grammatik G1: GZahl

Ziffer

GZ

0 1 GZ

…

Zahl

9 Zahl

GZ Ziffer

2 4

Ziffer

Zahl

6 8

5.1.4 Zeichen, Alphabet, Verkettung, Zeichenkette Die Operation Verkettung legt fest, wie einzelne Zeichen zu einer Zeichenkette verbunden werden. Die Zeichen stammen aus einem Alphabet. Ein Alphabet ist eine beliebige endliche nichtleere Menge, deren Elemente Zeichen oder Symbole genannt werden.

Terminale werden als Kreise bzw. Ovale, Nichtterminale werden als Rechtecke dargestellt.

443

444

Theoretische Informatik

Die folgenden Mengen A3 = { sin, cos, tan, cot, int, sqrt } sind Alphabete, wobei insbesondere die Elemente in A3 als (atomare) Symbole, die nicht etwa aus mehreren Buchstabensymbolen zusammengesetzt wurden, anzusehen sind. B1 = {0, 1, 1, 2} und B2 = { } = Ø sind keine Alphabete, da B1 gegen die Mengendefinition verstößt und B2 gegen die Alphabetdefinition, wonach die Grundmenge mindestens ein Zeichen enthalten muss. Das Symbol für den Verkettungsoperator ist ○, sprich: Kringel. Ähnlich, wie der Punkt für den Multiplikationsoperator in der Mathematik, wird ○ manchmal weggelassen. Es entstehen Zeichenketten.

Die Verkettung ○, oder Konkatenation von z1 und z2, kurz: z1 ○ z2 = k, ist eine zweistellige Operation für Zeichen aus einem Alphabet A, wobei k = z1z2 durch Hintereinanderschreiben von z1 und z2 entsteht. k ist eine Zeichenkette, die zum besseren Erkennen in Hoch-

Um ganze Sätze bilden zu können, muss die Verkettung für Zeichen auf die Verkettung von Zeichenketten verallgemeinert werden. Die Verkettung ○, mit k1 ○ k2 = k, ist eine zweistellige Operation für Zeichenketten über einem Alphabet A, wobei k = k 1k2 durch Hintereinanderschreiben von k1 und k2 entsteht. Das Ergebnis k ist eine Zeichenkette. Verkettung von Zeichenketten: “hallo“ ○ “otto“ = “hallootto“ “hallo“ ○ “ otto“ = “hallo otto“ “hallo“ ○ “ “ ○ “otto“ = “hallo otto“ “hallo“ ○ ““ ○ “otto“ = “hallootto“ Im Beispiel kommt die leere Zeichenkette ““ vor. Sie wird auch das leere Wort genannt und mit ε bezeichnet. Dies geschieht analog zur leeren Menge { }, für die im Allgemeinen Ø geschrieben wird. Sei k eine Zeichenkette. Dann gilt: 1. k ○ ε = ε ○ k = k, 2. k ○ k ○ k ○ … ○ k = kn, n ≥ 0 n-mal 3. k0 = ε kn = k ○ kn – 1 = kn – 1 ○ k, n > 0

Formale Sprachen und Automaten

Die rekursive Definition von kn unter 3. in obiger Definition enthält die Gleichheit k ○ kn – 1 = kn – 1 ○ k. Dies gilt natürlich nur für ein und dieselbe Zeichenkette k.

Falsch wäre k1 ○ k2 = k2 ○ k1, denn ○ ist nicht kommutativ.

5.1.5 Länge einer Zeichenkette, Wort und Wortmenge Unter der Länge einer Zeichenkette k versteht man die Anzahl aller Zeichen von k. Dabei wird jedes Vorkommen eines bestimmten Alphabetzeichens in der betrachteten Zeichenkette extra gezählt. “abba“ und “haus“ haben beide die Länge 4. Die Länge einer Zeichenkette k = z1z2z3 … zp, kurz: |k| = p, ist gleich der Anzahl der Zeichen, die k enthält. Es ist nicht gefordert, dass die vorkommenden Zeichen paarweise verschieden sind. Für k = ε gilt |k| = 0.

Satz: Seien k1 und k2 , mit |k1| = n und |k2| = m, Zeichenketten. Dann gilt |k1 ○ k2| = n + m. Beweis: k1 = x1x2 … xn, k2 = y1y2 … ym k1 ○ k2 = x1x2 … xn y1y2 … ym = z1z2 … znzn + 1zn + 2 … zn + m |k1k2| = n + m Zeichenketten, die über einem Alphabet A gebildet werden, nennt man Wörter über A. Durch Verkettung können unendlich viele Wörter über einem gegebenen Alphabet erzeugt werden. Dies gilt auch dann, wenn das Alphabet aus nur einem einzigen Zeichen besteht. Sei A = {a, b} ein Alphabet. Dann gehören sämtliche Wörter – der Länge 0, nämlich ε, – der Länge 1, nämlich “a“, “b“, – der Länge 2, nämlich “aa“, “ab“, “ba“, “bb“, – usw. in die Menge der Wörter über A, kurz: Wortmenge über A. Offensichtlich können über A rn verschiedene Wörter der Länge n erzeugt werden, wenn das Alphabet A genau r Elemente besitzt. Die Menge aller Wörter über einem Alphabet heißt Wortmenge A*, ∞

Σ Ai i=0

A* ist stets eine unendliche Menge. Die angegebene Zerlegung von A* in Teilmengen Ai lässt erahnen, wie man sämtliche Wörter aus A* längenlexikographisch anordnen kann. Auf diese Weise kann man die Elemente aus A* durchnummerieren. Mengen, bei denen das gelingt, heißen abzählbar unendlich.

445

446

Theoretische Informatik

Die Definition verwendet Ai für die Menge aller Wörter über A, deren Länge gleich i ist. Ai bedeutet also, dass i-mal je ein beliebiges Element aus A genommen und an die jeweils aktuelle Zeichenkette angehangen wird. Das gleiche Resultat ergibt sich für i > 0 durch Ai – 1 ○ A. Es macht offenbar Sinn, die Verkettungsoperation auf Mengen anzuwenden. Für zwei Mengen M1 und M2 gilt

Seien M1 = {“ab“, “cd“, “a“} und M2 = {ε, “x“, “xy“}, so ist M1 ○ M2 = {“ab“, “cd“, “a“, “abx“, “cdx“, “ax“, “abxy“, “cdxy“, “axy“}. Die Analogie zum kartesischen Produkt zweier Mengen ist offensichtlich. Ferner gelten M ○ Ø = Ø ○ M = Ø und M ○ {ε} = {ε} ○ M = M für beliebige Mengen M. Ist eine der beiden Mengen leer, so ergibt sich die leere Menge. Enthält eine der Mengen nur das leere Wort, so ergibt sich die andere Menge. Mit Mk wird die Verkettung M ○ M ○ … ○ M bezeichnet. k-mal M Für die Wortmenge A* über einem Alphabet A kann kein begrenzendes k angegeben werden, denn die erzeugbaren Wörter können beliebig lang sein. Hierfür wurde der oben schon verwendete Stern-Operator eingeführt.

I kleeNe-Stern (sprich: Klini-stern) nach stepheN Cole kleeNe (1909 – 1994)

Der kleeNe-Stern ist eine einstellige Operation für Mengen M, mit

Aus der Definition ist unmittelbar erkennbar, dass 1. das leere Wort zu M* gehört und 2. M* eine unendliche Menge ist. Da die Verkettung weiter oben sowohl für Zeichen als auch für Zeichenketten definiert wurde, spielt es keine Rolle, ob M ein Alphabet oder eine Menge von Wörtern ist. Auf der Basis der eingeführten Grundbegriffe kann nun der Begriff „formale Sprache“ definiert werden.

5.1.6 Formale Sprache

A* Ls

L7 L6

Eine formale Sprache L über einem Alphabet A ist eine beliebige Teilmenge der Wortmenge A*. Die Elemente von L heißen Sätze (im Compilerbau) bzw. Wörter (in der Theorie der formalen Sprachen). Es ist sofort klar, dass L1 = Ø (leere Sprache) und L2 = A* (Allsprache) zulässige Sprachen über A sind. Beide erweisen sich jedoch als praktisch weitgehend uninteressant, denn wozu braucht man eine Sprache, die keinen einzigen Satz enthält, oder eine, die hinsichtlich der Satzbildung keinerlei Regeln vorgibt?

Formale Sprachen und Automaten

Formale Grammatiken G sorgen dafür, dass die von ihnen erzeugbaren Sprachen L(G) im Allgemeinen gerade „zwischen“ Ø und A* liegen, d. h., Die von einer Grammatik G erzeugbare Sprache ist L(G) = {w | s d. h., jedes Wort w, das aus dem Spitzensymbol s über beliebig viele Schritte abgeleitet werden kann, gehört zu dieser Sprache. Die Länge der Ableitung spielt keine Rolle. Die auf Seite 445 angegebene Grammatik G1 beschreibt die Menge / Sprache der geraden Zahlen. T ergibt sich direkt aus A. Beispielsweise gehört die Zahl, genauer: das Zahlwort, “38“ zu L(G1), denn Wenn es sich um Grammatiken handelt, deren Regeln auf der linken Seite aus genau einem Nichtterminal bestehen, spielt es keine Rolle, in welcher Reihenfolge die Nichtterminale in den Satzformen der Ableitung ersetzt werden. Sogar simultane Ersetzungen sind denkbar. Üblicherweise werden Linksableitungen verwendet, d. h., das am weitesten links stehende Nichtterminal wird zuerst ersetzt. Trotz dieser Verabredung kann es vorkommen, dass mehrere (echt) verschiedene Ableitungen für ein und dasselbe Wort aus L(G) existieren. Solche Grammatiken und die dazugehörigen Sprachen sind mehrdeutig. Die Grammatik ist mehrdeutig, denn das Wort “acb“ lässt sich auf verschiedene Weise aus S linksableiten: S

1

4

2

S

3

S

a

B c

A b

a

b c

Es entstehen unterschiedliche Ableitungsbäume. Mehrdeutige Grammatiken sind höchst unerwünscht. Sie erschweren die Prozesse, die bei der Übersetzung von Programmiersprachen stattfinden, erheblich und können zu Fehlern führen. Leider kann i. Allg. weder das Aufspüren der Mehrdeutigkeit für Grammatiken noch deren Umformung in eindeutige Grammatiken, die die gleiche Sprache beschreiben, automatisch erledigt werden. Dies bleibt im Wesentlichen „Handarbeit“.

5.1.7 Chomsky-Hierarchie Formale Grammatiken und die damit verbundenen Sprachen werden klassifiziert. Klassifizierungsmerkmal ist die Regelgestalt.

Die Fälle L(G) = Ø und L(G) = A* sind praktisch bedeutungslos

447

448

Theoretische Informatik

Eine formale Grammatik G = (N, T, P, s) heißt

– vom Typ 1 oder kontextsensitiv, wenn gegenüber Typ 0 für jede

I Hinweis zu formalen Grammatiken des Typs 3:

– vom Typ 2 oder kontextfrei, wenn gegenüber Typ 1 für jede Regel einschränkend gilt, dass alle linken Regelseiten genau aus einem – vom Typ 3 oder regulär, wenn gegenüber Typ 2 für jede Regel Die von den Grammatiktypen erzeugbaren Sprachen heißen dementsprechend.

möglich. Die Formen dürfen jedoch nicht vermischt werden.

I

Die durch Grammatiken vom Typ i erzeugbaren Sprachklassen +i (Menge von Sprachen des Typs i ) bilden eine Hierachie, d. h., sie stehen in nebenstehend skizzierter Beziehung: Neben den Grammatiken gibt es für jede Sprachklasse ein spezielles Automatenmodell und individuelle Beschreibungstechniken. Damit gelingt es, konkrete Sprachen, die im Allgemeinen unendliche Mengen sind, zu definieren. Dies ist nicht zu verwechseln mit der im Folgenden genannten viel allgemeineren Fragestellung für Sprachklassen:

+0 +1 +2 +3

L(G)?“, wenn w ein beliebiges Wort aus A* und G eine beliebige Grammatik des betrachteten Typs sind. Eine Frage oder ein Problem heißt entscheidbar, wenn es entweder mit ja (wahr/true) oder mit nein (falsch/false) beantwortet wird. Manche Problemstellungen müssen erst in eine entsprechende Entscheidungsform gebracht werden. Satz: Das Wortproblem ist für Typ-1- und damit auch für Typ-2- und Typ-3-Sprachen entscheidbar, jedoch nicht für Typ-0-Sprachen. Beweis: w = z1z2z3 … zn sei ein beliebiges zu untersuchendes Wort aus A*. Vom Spitzensymbol s ausgehend werden durch Anwendung sämtlicher passender Regeln alle möglichen Satzformen gebildet (Simultanableitung). Mit den so gebildeten Satzformen fährt man ebenso fort,

Formale Sprachen und Automaten

bis deren Längen mit der von w übereinstimmen. Es gibt nur endlich chenketten, die ausschließlich aus Terminalen bestehen. Kommt w daDas beschriebene Verfahren kann auf Typ-0-Grammatiken, wegen fehlender Längenmonotonie, im Allgemeinen nicht angewandt werden. Es ist nämlich möglich, dass das betrachtete Wort aus einer Satzform, die länger ist als w, ableitbar ist. Eine Begrenzung des „Suchraumes“ ist daher unmöglich.

wendig und zeitraubend. Für praktische Anwendungen ist es unbrauchbar. Im Gebiet „Compilerbau“ werden daher wesentlich effizientere Entscheidungsverfahren eingesetzt.

5.1.8 Reguläre Ausdrücke Typ-3-Sprachen können außerdem durch reguläre Ausdrücke beschrieben werden. (Auf Hochkommata wird im Folgenden verzichtet.) Reguläre Sprachen finden beispielsweise Anwendung bei – Variablennamen (Bezeichner) in vielen Programmiersprachen: Ein Bezeichner (identifier) ist eine beliebige Zeichenkette über einem bestimmten Alphabet, die mit einem Buchstaben beginnen muss. – Zahlen als Folge von Ziffern, z. B. 8364, (Problem: Unterdrückung von Vornullen). Komplexere Anwendungen regulärer Ausdrücke finden sich in Texteditoren. Dabei werden Muster, wie a*(b+c)d+ , nach denen man den Text durchsucht, vorgegeben.

nennt sie auch reguläre Menge. Reguläre Ausdrücke sind wie folgend induktiv definiert: 1. Ø ist ein regulärer Ausdruck, und es gilt L(Ø) = Ø .

lärer Ausdruck, und es gilt L(a) = {a}.

Nur die nach 1. bis 4. definierten Ausdrücke sind reguläre Ausdrücke.

Beispiele für reguläre Ausdrücke

Der Norton Commander unter DOS verwendet folgende Muster, um bestimmte Dateinamen zu finden: test?.doc, *.bat, [abc]*.*, [a-e]*.* [^adt]*.*

449

450

Theoretische Informatik

= {a, bc} L(β) = {ac, bc} L(γ) = {b, ab, a2b, a3b, … } Um die Ausdrücke lesbar zu halten, wird folgende Klammersparregel nicht entfallen, wenn die Priorität von op2 größer ist als die von op1. Die Reihenfolge der Operatoren mit aufsteigender Priorität lautet: +, · , *. Dies erinnert an das Zahlenrechnen mit + (Addition), · (Multiplikation) und n (Potenzieren), aber nicht alle Eigenschaften sind übertragbar. Es kann ...