Press "Enter" to skip to content

New PDF release: Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte

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 forth. 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

New PDF release: Weiterentwicklung von Verfahren zur Aufnahme von Fließkurven

Die vorliegende Arbeit entstand während meiner Tätigkeit als wissenschaftlicher Mitarbeiter am Institut für Umformtechnik (IfU) der Universität Stuttgart. Herrn Prof. Dr. -Ing. habil. Klaus Pöhlandt danke ich herzlich für die Betreuung der Arbeit, für das mir entgegengebrachte Vertrauen, seine großzügige Förderung sowie die wertvollen Diskussionen und Anregungen.

Download PDF by Francesco Giacomo Tricomi, Friedrich Kasch: Vorlesungen über Orthogonalreihen

Wahrend m dem inform uber tngonometrische Reihen das Haupt mteresse auf der Konvergenzfrage hegt, werden in dem Teil uber Ortho gonalpolynome mehr die mdlvlduellen Eigenschaften derselben in den Vordergrund gestellt und auch zwel Paragraphen uber dIe allgemeinen Kugelfunktionen hmzugefugt. Ich erlaube mir, den Leser auf meine einheltliche Behandlung der sog.

Fastperiodische Funktionen by W. Maak (auth.) PDF

Das vorliegende Buch handelt von den fastperiodischen Funktionen auf Gruppen. Die Theorie dieser Funktionen erfaßt als Spezialfälle unter anderem die Fourierreihen periodischer Funktionen, die eigent­ lichen von H. BOHR geschaffenen fastperiodischen Funktionen und die Kugelfunktionen. Im Grunde ist die Theorie der fastperiodischen Funk­ tionen auf Gruppen nichts anderes als die Darstellungstheorie beliebiger, additionally vor allem auch unendlicher Gruppen.

Extra resources for Automaten Sprachen Berechenbarkeit: Grundkurs Angewandte Informatik IV

Sample text

Ek'und z =ek+i' ... em'. Dann gilt offenbar: w =xyz, Ixyl =k:::; n, Iyl =k - j ~ 1. h. es gilt: 'iii E INo: xyi z E L(EA). 16: Durchlaufene Zustande beim Akzeptieren des Wortes w = xyz Somit sind alle Behauptungen des Satzes bewiesen. h. beliebig verlangem laBt. 14) zuriickkommen. 16) Beispiel: Wir betrachten noch einmal das erste Beispiel dieses Abschnitts (s. 6). 10 angedeutete Automat akzeptiert alle W orte tiber dem Alphabet E = {a, b}, die auf b b enden. h. mehr Zeiehen als Zustande) besteht, etwa das Wort "bbabb".

27) Satz: Zu jeder Mealy-Maschine gibt es eine gleiehwertige MooreMaschine und umgekehrt. • Den Beweis dieses Satzes iiberlassen wir dem Leser (s. 25 auftreten. Wir wollen jetzt die Grenze der Leistungsfahigkeit von endlichen Maschinen betrachten. Bei endlichen Automaten ohne Ausgabe wurden diese Grenzen durch das Pumping-Lemma dokumentiert. Hier lassen sieh Abbildungen zwischen Eingabe- und Ausgabewortem angeben, die nieht durch eine endliche Maschine realisierbar sind. Einen Einblick gibt der folgende Satz, des sen Beweis wir wiederum dem Leser iiberlassen (s.

Das fUr jedes Zustandspaar (Sh Sj). oder umgekehrt. (mit i :f; j) einen Eintrag vorsieht: S1 S2 S3 S4 ... Sn S1 SO S2 s3 ... Sn-1 Es wird nun jedes Kastchen zu einem Paar (Sh Sj) mit einem Kreuz markiert. fUr das si - Sj nicht gelten kann. Zum SchluB. wenn sich durch das Verfahren keine Anderung mehr ergibt. geben die nichtmarkierten Kastchen genau die aquivalenten Zustiinde an. 43) AIgorithmus: INPUT: (Feststellung der aquivalenten Zustiinde eines endlichen Automaten ohne Ausgabe) vereinfachter endlicher Automat EA = (E, S, D, so, F) ohne Ausgabe; OUTPUT: alle Paare (s, s') aquivalenter Zustiinde; BEGIN (* Bestimmung von "-" *) k :=0; (1) FOR EACH Paar (s, s') S x S mit s:f; S' DO (2) IF s E F, s' E S - F OR s' E F, s E S - F (3) E THEN markiere (s, s') END (* IF *) END (* FOR *); (* jetzt gilt: (s, s') unmarkiert ¢:> s _0 s' *) REPEAT k:=k+ 1; (4) 64 2 Automaten FOR EACH unmarkiertes Paar (s, s') IF 3 e E E S X S mit s:;; s' DO E: (8(s, e), 8(s', e» ist markiert (5) THEN markiere (s, s') END (* IF *) END (* FOR *); (* jetzt gilt: (s, s') unmarkiert <=> s.!

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 Thomas
4.1

Rated 4.76 of 5 – based on 3 votes