Theoritsche Informatik an der Technische Hochschule Köln

Genau 2 Wahrheitswerte: wahr und falsch

Darstellung der Wahrheitswerte:
• falsch        ⇔       f         ⇔ 0
• wahr          ⇔       w       ⇔ 1

Nach George Boole (1815 – 1864)

Zusammenfassung bestimmter, wohlunterschiedener Objekte unserer Anschauung oder unseres Denkens zu einem Ganzen.

• Ein Palindrom ist ein Wort, das vorwärts und rückwärts gelesen gleich ist
• Beispiele für Palindrome über {a,b}: aa, aba, abba, abbba, abaaba, bb, …

Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die mathematische Verwendung. Eine formale Sprache besteht aus einer bestimmten Menge von Symbolketten (im Allgemeinen Zeichenketten) („Wörter“ der Sprache), die aus einem Zeichen-/Symbolvorrat („Alphabet“, Grundsymbole) zusammengesetzt werden können. Anwendung finden formale Sprachen in der Linguistik, der Logik und der theoretischen Informatik.

Formale Sprachen eignen sich zur (mathematisch) präzisen Beschreibung des Umgangs mit Zeichenketten. So können zum Beispiel Datenformate oder ganze Programmiersprachen spezifiziert werden. Zusammen mit einer formalen Semantik erhalten die definierten Zeichenketten eine (mathematische) Bedeutung. Bei einer Programmiersprache kann damit einer Programmieranweisung (als Teil der formalen Sprache) ein eindeutiges Maschinenverhalten (als Teil der Semantik) zugeordnet werden.

Formale Grammatiken sind mathematische Modelle von Grammatiken, die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau zum einen angewendet, um eindeutig festzulegen, ob ein Wort Element einer Sprache ist und zum anderen, um Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.

• V = Variablenalphabet (auch: „Nichtterminale (Symbole)“),
• Σ= Terminalalphabet (auch: „Terminale (Symbole)“) mit V ∩ Σ= ∅,
• P = Produktionsregeln, mit Relation P ⊆ ((V∪Σ)*\Σ*) × (V∪Σ)*,
• S = Startsymbol (auch: „Startvariable“): S ∈ V.
• V, Σ, P seien dabei endliche Mengen

Eine Menge von Zeichenketten nennen wir auch (formale) Sprache.

Weil viele Aussagen der theoretischen Informatik mit dem
Prinzip der vollständigen Induktion beweisbar sind 

eulersch (oder Eulergraph), wenn er zusammenhängend ist und
einen Eulerkreis besitzt

Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie, ist ein Begriff aus der Theoretischen Informatik. Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben.

Karl Steinbuch, Karl Steinbuch war ein deutscher Kybernetiker, Nachrichtentechniker, Informationstheoretiker und Autor der Neuen Rechten

Karl Steinbuch