By Dr. rer. pol. Peter Sander, Prof. Dr. rer. nat. Wolffried Stucky, Prof. Dr. rer. nat. Rudolf Herschel (auth.), W. Stucky (eds.)

Der Begriff der formalen Sprache ist grundlegend für viele Bereiche der angewandten und theoretischen Informatik, sei es im Bereich der Programmiersprachen, im Compilerbau oder auch in Datenmanipulations- und Abfragesprachen oder Datenbanktechnologie. Ausgehend von motivierenden Beispielen werden die klassischen analysierenden und erzeugenden Systeme formaler Sprachen untersucht: Der Hierarchie der Automaten, von endlichen Automaten über Kellerautomaten bis hin zu Turing-Maschinen, wird die Hierarchie der Chomsky-Grammatiken gegenübergestellt, wobei die einzelnen Sprachklassen diskutiert und klar gegeneinander abgegrenzt werden. Schließlich erfolgt die Darstellung grundlegender Begriffe wie "Algorithmus", "Berechenbarkeit", Entscheidbarkeit", and so on. Die Bedeutung dieser Begriffe für die Informatik im allgemeinen und für die Theorie formaler Sprachen im speziellen wird herausgearbeitet. Ziel des Bandes ist es, auf leicht verständliche und dennoch präzise Weise eine Einführung in diese wichtigen Gebiete der Informatik zu geben. Insbesondere soll beim Leser ein Verständnis für viele methodischen Grundlagen - etwa für die Konzepte von Programmiersprachen - entwickelt werden. Das Buch ist im Rahmen des http://medoc.informatik.tu-muenchen.de/deutsch/medoc.html>MeDoc-Projektes in die elektronische Informatik-Bibliothek aufgenommen worden und steht über das Projekt http://InterDoc.OFFIS.Uni-Oldenburg.de>InterDoc weiterhin zur Verfügung.

Show description

Read or Download Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte Informatik IV PDF

Similar german_5 books

Antennen und Strahlungsfelder: Elektromagnetische Wellen auf Leitungen, im Freiraum und ihre Abstrahlung

Dieses Buch gibt eine systematische Einf? hrung in die Begriffswelt elektromagnetischer Strahlungsfelder. Die Antennentechnik wird von den feldtheoretischen Grundlagen bis zu praktischen Designvorschl? gen verst? ndlich dargestellt. Neben den grundlegenden mathematischen Methoden wird gro? er Wert auf die physikalische Interpretation und Visualisierung der erhaltenen Ergebnisse mittels Computersimulationen gelegt.

Das Sintflutprinzip: Ein Mathematik-Roman

Mit dem Sintflutprinzip erschafft der Kultbuch-Autor Gunter Dueck ein neues style: Das ernste Thema der mathematischen Optimierung von Wirtschaftsprozessen wird als kunterbunter Cocktail von Dichtung und Optimierungswahrheit, von administration und Industriepraxis eingeschenkt. Das Buch kommt praktisch ohne Formeln aus, weil in einer romanhaften Rahmenhandlung kleine Wesen unaufhörlich vor einer Sintflut fliehen und damit gezwungen werden, dem Leser vorzuführen, wie guy in der Höhe "besser" wird.

Moderne Physik: Sieben Vorträge über Materie und Strahlung

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer ebook files mit Publikationen, die seit den Anfängen des Verlags von 1842 erschienen sind. Der Verlag stellt mit diesem Archiv Quellen für die historische wie auch die disziplingeschichtliche Forschung zur Verfügung, die jeweils im historischen Kontext betrachtet werden müssen.

Additional info for Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte Informatik IV

Sample text

Dazu unterscheiden wir wieder die beiden Moglichkeiten, die wir schon im letzten Abschnitt (informal) fiir Automaten mit Ausgabe betrachtet haben: Die ZustandstaJel beschreibt die Uberfiihrungsfunktion 0 : S x E ~ S in Form einer Matrix. Die Spalten werden mitje einem Eingabezeichen ej (i = 1, ... ,r), die Zeilen mit je einem Zustand Sj (j = 0, ... ,n) iiberschrieben. Die Zuordnung (Sj, ej) f-? Sk wird durch den Eintrag Sk in der i-ten Spalten und der j-ten Zeile der Matrix wiedergegeben (s. 8).

010 11000 ---t 110 10 11 0), (b) solange eine 0 ausgibt, bis erstmalig die Zeichenkette 10 1 im Eingabewort erkannt wird. B. 0 10110 ---t 000 Ill)! 3. 21 in eine gleichwertige Moore-Maschine urn! 4. Konstruieren Sie eine Mealy-Maschine, die die Multiplikation von zwei Binarzahlen mit beschriinkter Stellenzahl durchfUhren kann! Nehmen Sie an, daB die Zahlen aus maximal 2 Stellen bestehen. 5. Beweisen Sie, daB es zu jeder Mealy-Maschine eine gleichwertige MooreMaschine gibt und umgekehrt! 25 aus!

Dieses Wort gehOrt also zur Sprache des Automaten, weil der Zustand S2 in der letzten Konfiguration ein Endzustand ist. Dagegen gelangt der Automat beim Verarbeiten des Wortes "baba" nieht in einen Endzustand: • (so, baba) ~A (SI, aba) ~A (so, ba) ~A (SI, a) ~ (SO, A) . 11) Beispiel: Bisher sind wir in unseren Beispielen immer von einem gegebenen Automaten ausgegangen und haben versucht, die Sprache des Automaten zu erkennen. Jetzt wollen wir umgekehrt vorgehen und uns die Frage stellen, wie ein Automat aussehen kann, der eine fest vorgegebene Sprache hat.

Download PDF sample

Rated 4.96 of 5 – based on 38 votes