مقدمه ای بر نظریه زبان ها و ماشین ها (پیتر لینز) به زبان اصلی با ضمیمه حل تمرین های انتخابی
قدمه ای بر نظریه زبانها و ماشینها، ویرایش سوم، پیتر لینز (زبان اصلی) با ضمیمه حل تمرین های انتخابی
نویسنده: پیتر لینز
دانشگاه کالیفرنیا در دیویس
کتاب مقدمه ای بر نظریه زبانها و ماشینها، پیتر لینز در تمامی دنیا به عنوان یکی از مهمترین مرجع های درس نظریه زبان ها و ماشین ها و همچنین مسابقات ACM (ای سی ام) به شمار می آید و بسیار با ارزش است.
درباره کتاب به زبان نویسنده(پیتر لینز)
این کتاب به منظور بحث های مقدماتی زبان ها، اتوماتاها، محاسبات و موضوعات مربوطه، تالیف شده است. این موضوعات در بر گیرنده بخش اصلی از آنچه که به عنوان نظریه محاسبات معرفی شده، نیز می باشد.
آموزش این مبحث مهم در حال حاضر در برنامه درسی علوم کامپیوتر به صورت استاندارد قرار گرفته است و اغلب تدریس آن در اوایل برنامه آموزشی قرار دارد.
پیش نیازهای اساسی برای این کتاب، آگاهی از برخی از زبان های برنامه نویسی سطح بالاتر (معمولا C، C + + یا جاوا) و آشنایی با اصول ساختار داده ها، الگوریتم و البته ریاضیات گسسته که شامل نظریه مجموعه ها، توابع، روابط، منطق، و عناصر استدلال ریاضی است. در این کتاب و مبحث معرفی و توضیح دوره آموزشی علوم کامپیوتر مقدماتی استاندارد و طبیعی است.
این کتاب در ضمیمه خود، از هر فصل تعدادی تمرین را انتخاب کرده و آنها را به طور کامل حل کرده است.
An Introduction to Formal Languages and Automata Third Edition
Peter Linz
University of California at Davis
This book is designed for an introductory course on formal languages, automata, computability, and related matters. These topics form a major part of what is known as the theory of computation. A course on this subject matter is now standard in the computer science curriculum and is often taught fairly early in the program. Hence, the prospective audience for this book consists primarily of sophomores and juniors majoring in computer science or computer engineering.
Prerequisites for the material in this book are knowledge of some higher-level programming languages (commonly C, C++, or Java) and familiarity with the fundamentals of data structures and algorithms. A course in discrete mathematics that includes set theory, functions, relations, logic, and elements of mathematical reasoning is essential. Such a course is part of the standard introductory computer science curriculum.
The Study of the theory of computation has several purposes, most importantly (1) to familiarize students with the foundations and principles of computer science, (2) to teach material that is useful in subsequent courses, and (3) to strengthen student's ability to carry out formal and rigorous mathematical arguments. The presentation I have chosen for this favors the first two purposes, although I would argue that it also serves the third. To present ideas clearly and to give students insight into the material, the text stresses intuitive motivation and illustration of ideas through examples. When there is choice, I prefer arguments that are easily grasped to those that are concise and elegant but difficult in concept. I state definitions and theorems precisely and give the motivation for proofs, but often leave out the routine and tedious details... .
لینک دانلود و فهرست کامل این کتاب در ادامه مطلب ...
- مقدمات ریاضی و نشانه گذاری
- سه ایده اساسی
- برخی از برنامه های کاربردی
فصل 2 ماشین های متناهی
- ماشین های قطعی متناهی پذیرنده
- ماشین های غیر قطعی متناهی پذیرنده
- هم ارزی از قطعی و غیر قطعی پذیرنده متناهی
- کاهش تعداد از حالت ها در ماشین های متناهی
فصل 3 زبان های منظم و گرامرهای منظم
- مجموعه های منظم
- ارتباط بین عبارات منظم و زبان های منظم
- گرامرهای منظم
فصل 4 خواص زبانهای منظم
- خواص و بستن زبانهای منظم
- سوالات ابتدایی در مورد زبانهای منظم
- شناسایی زبان های غیرمنظم
فصل 5 زبان های مستقل از متن
- گرامرهای مستقل از متن
- تجزیه و ابهام
- گرامرهای مستقل از متن و برنامه نویسی
فصل 6 ساده سازی گرامرهای مستقل از متن و شکل های نرمال
- روشهایی برای تبدیل گرامر
- دو فرم نرمال با اهمیت (گریباخ و چامسکی)
- الگوریتم تبدیل گرامرهای مستقل از متن
فصل 7 ماشین های پشته ای
- ماشینها پشته ای غیرقطعی
- ماشین های پشته ای و زبان مستقل از متن
- ماشینها پشته ای قطعی و مستقل از متن زبان قطعی
- گرامرها برای زبان های مستقل از متن قطعی
فصل 8 ویژگی های زبانهای مستقل از متن
- دو لم پمپاژ
- بسته بودن ویژگی ها و الگوریتم تصمیم گیری برای زبان های مستقل از متن
فصل 9 ماشین تورینگ
- ماشین تورینگ استاندارد
- ترکیب ماشین های تورینگ برای انجام کارهای پیچیده
- پایان نامه فصل تورینگ
فصل 10 دیگر مدل های ماشین تورینگ
- تغییرات جزیی در ظاهر ماشین تورینگ
- ماشین تورینگ با ذخیره سازی پیچیده تر
- ماشین تورینگ غیرقطعی
- ماشین تورینگ جهانی
- ماشین های خطی محدود
فصل 11 سلسله مراتب زبانها و ماشینها
- زبان بازگشتی و بازگشتی شمارش پذیر
- گرامرهای بدون محدود
- زبان ها و گرامرهای حساس به متن
- سلسله مراتب چامسکی
فصل 12 محدودیت الگوریتم های محاسبات
- برخی از مشکلات که با ماشین های تورینگ قابل حل نیست
- مشکلات تصمیم ناپذیر زبانهای بازگشتی شمارش پذیر
- ارسال مکاتبات و پیگیری مشکلات
- مشکلات تصمیم ناپذیر برای زبانهای مستقل از متن
فصل 13 دیگر مدل های محاسبات
- توابع بازگشتی
- سیستم ارسال
- بازنویسی سیستم
فصل 14 مقدمه ای بر پیچیدگی محاسباتی
- بهره وری از محاسبات
- ماشین تورینگ و پیچیدگی
- خانواده زبان و کلاسهای پیچیدگی
- کلاس های پیچیدگی P و NP
پاسخ تمرین های انتخاب شده
Chapter 1 introduction to the Theory of Computation
Mathematical Preliminaries and Notation
Three Basic Concepts
Some Applications
Chapter 2 Finite Automata
Deterministic Finite Accepters
Nondeterministic Finite Accepters
Equivalence of Deterministic and Nondeterministic Finite Accepters
Reduction of the Number of States in Finite Automata
Chapter 3 Regular Languages and Regular Grammars
3.1 Regular Expressions
3.2 Connection Between Regular Expressions and Regular Languages
3.3 Regular Grammars
Chapter 4 Properties of Regular Languages
4.1 Closure Properties of Regular Languages
4.2 Elementary Questions about Regular Languages
4.3 Identifying No regular Languages
Chapter 5 Context-Free Languages
5.1 Context-Free Grammars
5.2 Parsing and Ambiguity
5.3 Context-Free Grammars and Programming
Chapter 6 Simplification of Context-Flee Grammars
6.1 Methods for Transforming Grammars
6.2 Two Important Normal Forms
*6.3 A Membership Algorithm for Context--Free Grammars
Chapter 7 Pushdown Automata
7.1 Nondeterministic Pushdown Automata
7.2 Pushdown Automata and Context-Free Languages
7.3 Deterministic Pushdown Automata and Deterministic: Context Free Languages
*7.4 Grammar for Deterministic Context-Free: Languages
Chapter 8 Properties of Context-Flee Languages
8.1 Two Pumping Lemmas
8.2 Closure Properties and Decision Algorithms for Context-Free Languages
Chapter 9 Turing Machines
9.1 The Standard Turing Machine
9.2 Combining Turing Machines for Complicated Tasks
9.3 Turing's Thesis
Chapter 10 Other Models of Turing Machines
10.1 Minor Variations on the Turing Machine: Theme
10.2 Turing Machines with More Complex Storage
10.3 Nondeterministic Turing Machines
10.4 A Universal Turing Machine
10.5 Linear Bounded Automata
Chapter 11 A Hierarchy of Formal Languages and Automata
11.1 Recursive and Recursively Enumerable Languages
11.2 Unrestricted Grammars
11.3 Context-Sensitive Grammars Languages
11.4 The Chomsky Hierarchy
Chapter 12 Limits of Algorithmic Computation
12.1 Some Problems That Cannot Be Solved By Turing
12.2Un decidable Problems for Recursively Enumerable Languages
12.3 The Post Correspondence Problem
12.4 2Un decidable Problems for Context-Free Languages
Chapter 13 Other Models of Computation
13.1 Recursive Functions
13.2 Post Systems
13.3 Rewriting systems
Chapter 14 An Introduction to Computational Complexity
14.1 Efficiency of Computation
14.2 Turing Machines and Complexity
14.3 Language Families and Complexity Classes
14.4 The Complexity Classes P and NP
این کتاب در 410 صفحه برای شما عزیزان قرار گرفت.
حجم فایل: 24.57 مگابایت
پسورد فایل: www.pupuol.com
منبع: پوپول
نمی توان برگشت و آغاز خوبی داشت، اما می توان شروع کرد و پایان خوبی داشت.