Dr. rer. pol. Peter Sander, Prof. Dr. rer. nat. Wolffried's Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte PDF

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

ISBN-10: 3322848736

ISBN-13: 9783322848734

ISBN-10: 351912937X

ISBN-13: 9783519129370

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

Best german_5 books

Read e-book online Schulungsprogramm Gefahrguttransport: Stück- und PDF

Das Schulungsprogramm Gefahrguttransport des Springer-Verlags zeichnet sich durch die besondere didaktische Darstellung aus. Es ist damit das erste Programm, das den Bedürfnissen der Zielgruppe Kraftfahrer durch die Formulierung der schwierigen Materie entgegenkommt. Die Inhalte sind als "Merksätze" zusammengefaßt.

New PDF release: Relationale Datenbanksysteme: Eine praktische Einführung

Dieses Buch ist eine praktische Einf? hrung in den Entwurf und die Programmierung von relationalen Datenbanksystemen, wie sie heute vor allem in betrieblichen Bereichen eingesetzt werden. Es vermittelt detaillierte Kenntnisse der Sprache SQL, die als usual f? r den Zugriff auf diese Systeme etabliert ist.

Additional info for Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte Informatik IV

Example text

H. Automaten, die lediglich ein Wort akzeptieren konnen, aber keine Ausgabe produzieren, auch Akzeptoren. 6 (s. 10) und sehen uns die Konfigurationen an, die der Automat beim Akzeptieren des Wortes "abbabb" durchlliuft: (so, abbabb) ~A (SO, bbabb) ~A (S1o babb) ~A (S2, abb) ~A (so, bb) ~A (SI, b) ~A (S2, A) . 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) .

Als Losung erhhlt man, daB die Ausgabe -, G, -, -, -, WO erfolgt und daB der Automat dabei - beginnend beim Zustand 0 - nacheinander die Zustiinde 2,0,2,3, -0, 0 • durchHiuft. Wenn wir die beiden Beispiele vergleiehen, stellen wir fest, daB der Zigarettenautomat aufgrund der vielen internen Zustande und Eingabemoglichkeiten komplizierter ist als die Mausefalle. Es zeigt sieh, daB man mit wachsender Anzahl der Ein- und Ausgabezeichen und vor allen Dingen der internen Zustiinde mehr Sachverhalte modellieren kann.

Wir beginnen unsere Betrachtungen mit einem Beispiel. 14) Beispiel: Wir wollen uns die Sprache L = {anb n In E IN} iiber dem Alphabet E = {a, b} ansehen. h. alle Worter, die mit einer endlichen Folge von a's beginnen und dann mit genauso vielen b's enden? 15 beginnt, wo die kurzen Pfeile auf einen Zustand fiihren, von denen aus kein Endzustand erreicht werden kann, so erkennt man sofort die Schwierigkeit, das Problem fiir allgemeines n zu lOsen. 14 Das Zustandsdiagramm ist fiir n ~ 4 richtig. Es sollte aber fiir alle natiirlichen Zahlen aufgestellt werden.

Download PDF sample

Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte Informatik IV by Dr. rer. pol. Peter Sander, Prof. Dr. rer. nat. Wolffried Stucky, Prof. Dr. rer. nat. Rudolf Herschel (auth.), W. Stucky (eds.)


by David
4.3

Rated 4.21 of 5 – based on 9 votes

Categories: German 5