logo资料库

An Introduction to FORMAL LANGUAGES and AUTOMATA.pdf

发布时间：2022-06-14 发布人：admin 分类：说明书 资料大小：0.95M 资料格式：pdf 举报 版权申诉
第1页 / 共74页
第2页 / 共74页
第3页 / 共74页
第4页 / 共74页
第5页 / 共74页
第6页 / 共74页
第7页 / 共74页
第8页 / 共74页
资料共74页，剩余部分请下载后查看
    46070_TTLX_L nzIM.qxd 1/28/11 9:43 AM Page 1
    46070_TTLX_L nzIM.qxd 1/28/11 9:43 AM Page 2 World Headquarters Jones & Bartlett Learning 40 Tall Pine Drive Sudbury, MA 01776 978-443-5000 info@jblearning.com www.jblearning.com Jones & Bartlett Learning Canada 6339 Ormindale Way Mississauga, Ontario L5V 1J2 Canada Jones & Bartlett Learning International Barb House, Barb Mews London W6 7PA United Kingdom Jones & Bartlett Learning books and products are available through most bookstores and online booksellers. To contact Jones & Bartlett Learning directly, call 800-832-0034, fax 978-443-8000, or visit our website, www.jblearning.com. Substantial discounts on bulk quantities of Jones & Bartlett Learning publications are available to corporations, professional associations, and other qualified organizations. For details and specific discount information, contact the special sales department at Jones & Bartlett Learning via the above contact information or send an email to specialsales@jblearning.com. Copyright © 2012 by Jones & Bartlett Learning, LLC All rights reserved. No part of the material protected by this copyright may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner. Production Credits Publisher: Cathleen Sether Senior Acquisitions Editor: Timothy Anderson Senior Editorial Assistant: Stephanie Sguigna Production Director: Amy Rose Senior Marketing Manager: Andrea DeFronzo Composition: Northeast Compositors, Inc. Title Page Design: Kristin E. Parker 6048 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
    ✐ ✐ “46070˙PREF˙LinzIM” — 2011/1/28 — 13:30 — page iii — #1 ✐ ✐ Preface T he aim of this manual is to provide assistance to instructors using my book An Introduction to Formal Languages and Automata, Fifth Edition. Since this text was organized on the principle of learning by problem solving, much of my advice relates to the exercises at the end of each section. It is my contention that this abstract and often difficult subject matter can be made interesting and enjoyable to the average undergraduate stu- dent, if mathematical formalism is downplayed and problem solving is made the focus. This means that students learn the material and strengthen their mathematical skills primarily by doing problems. Now this may seem rather obvious; all textbooks contain exercises that are routinely assigned to test and improve the students’ understanding, but what I have in mind goes a little deeper. I consider exercises not just a supplement to the lectures, but that to a large extent, the lectures should be a preparation for the exercises. This implies that one needs to emphasize those issues that will help the stu- dent to solve challenging problems, with the basic ideas presented as simply iii ✐ ✐ ✐ ✐
    ✐ ✐ “46070˙PREF˙LinzIM” — 2011/1/28 — 13:30 — page iv — #2 ✐ ✐ iv Preface as possible with many illustrative examples. Lengthy proofs, unnecessary detail, or excessive mathematical rigor have no place in this approach. This is not to say that correct arguments are irrelevant, but rather that they should be made in connection with specific, concrete examples. Therefore, homework has to be tightly integrated into the lectures and each exercise should have a specific pedagogical purpose. Assignments need to be com- posed as carefully and thoughtfully as the lectures. This is a difficult task, but in my experience, the success of a course depends critically on how well this is done. There are several types of exercises, each with a particular purpose and flavor. Some of them are straightforward drill exercises. Any student with a basic understanding should be able to handle them. They are not always very interesting, but they test the student’s grasp of the material, uncover possible misunderstandings, and give everyone the satisfaction of being able to do something. A second type of exercise in the manual, I call “fill-in-the-details.” These are usually omitted parts of proofs or examples whose broad outlines are sketched in the text. Most of them are not overly difficult since all the non-obvious points have been spelled out. For mathematically well-trained students these exercises tend to be simple, but for those not in this cat- egory (e.g., many computer science undergraduates) they may be a little more difficult and are likely to be unpopular. They are useful primarily in sharpening mathematical reasoning and formalizing skills. The prevalent and most satisfying type of exercise involves both an understanding of the material and an ability to carry it a step further. These exercises are a little like puzzles whose solution involves inventiveness, ranging from the fairly easy to the very challenging. Some of the more difficult ones require tricks that are not easy to discover, so an occasional hint may be in order. I have identified some of the harder problems with a star, but this classification is highly subjective and may not be shared by others. The best way to judge the difficulty of any problem is to look at the discussion of the solution. Finally, there are some exercises that take the student beyond the scope of this course, to do some additional reading or implement a method on the computer. These are normally quite time consuming and are suitable only for extra-credit assignments. These exercises are identified by a double star. For the actual solutions, I have done what I think is most helpful. When a problem has a simple and concise answer, I give it. But there are many cases where the solution is lengthy and uninformative. I often omit the details on these, because I think it is easier to make up one’s own answer than to check someone else’s. In difficult problems I outline a possible approach, giving varying degrees of detail that I see necessary for following ✐ ✐ ✐ ✐
    ✐ ✐ “46070˙PREF˙LinzIM” — 2011/1/28 — 13:30 — page v — #3 ✐ ✐ Preface v the argument. There are also some quite general and open-ended problems where no particular answer can be given. In these instances, I simply tell you why I think that such an exercise is useful. Peter Linz ✐ ✐ ✐ ✐
    ✐ ✐ “46070˙PREF˙LinzIM” — 2011/1/28 — 13:30 — page vi — #4 ✐ ✐ ✐ ✐ ✐ ✐
    ✐ ✐ “46070˙TOCX˙LinzIM” — 2011/1/28 — 13:31 — page vii — #1 ✐ ✐ Contents 1 Introduction to the Theory of Computation 1.1 Mathematical Preliminaries and Notation . . . . . . . . . . Three Basic Concepts . . . . . . . . . . . . . . . . . . . . . 1.2 1.3 Some Applications . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 4 2 Finite Automata 2.1 2.2 2.3 2.4 Deterministic Finite Accepters . . . . . . . . . . . . . . . . Nondeterministic Finite Accepters . . . . . . . . . . . . . . Equivalence of Deterministic and Nondeterministic Finite Accepters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Reduction of the Number of States in Finite Automata . . 11 5 5 8 3 Regular Languages and Grammars 11 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . 11 Connection Between Regular Expressions and Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Regular Grammars . . . . . . . . . . . . . . . . . . . . . . . 16 3.1 3.2 3.3 4 Properties of Regular Languages Closure Properties of Regular Languages Elementary Questions about Regular Languages Identifying Nonregular Languages 17 . . . . . . . . . . 17 . . . . . . 21 . . . . . . . . . . . . . . 22 4.1 4.2 4.3 vii ✐ ✐ ✐ ✐
    ✐ ✐ “46070˙TOCX˙LinzIM” — 2011/1/28 — 13:31 — page viii — #2 ✐ ✐ viii Contents 5 Context-Free Languages 25 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . 25 Parsing and Ambiguity . . . . . . . . . . . . . . . . . . . . 28 Context-Free Grammars and Programming Languages . . . 29 5.1 5.2 5.3 6 Simplification of Context-Free Grammars and Normal Forms 6.1 Methods for Transforming Grammars 6.2 6.3 29 . . . . . . . . . . . . 30 Two Important Normal Forms . . . . . . . . . . . . . . . . 32 A Membership Algorithm for Context-Free Grammars . . . 33 7 Pushdown Automata 33 Nondeterministic Pushdown Automata . . . . . . . . . . . . 33 Pushdown Automata and Context-Free Languages . . . . . 36 Deterministic Pushdown Automata and Deterministic Context-Free Languages . . . . . . . . . . . . . . . . . . . . 38 Grammars for Deterministic Context-Free Languages . . . 39 7.1 7.2 7.3 7.4 8 Properties of Context-Free Languages Two Pumping Lemmas Closure Properties and Decision Algorithms for Context- Free Languages . . . . . . . . . . . . . . . . . . . . . . . . . 43 40 . . . . . . . . . . . . . . . . . . . . 40 8.1 8.2 9 Turing Machines 45 . . . . . . . . . . . . . . . . 45 The Standard Turing Machine Combining Turing Machines for Complicated Tasks . . . . 47 Turing’s Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 47 9.1 9.2 9.3 10 Other Models of Turing Machines 47 10.1 Minor Variations on the Turing Machine Theme . . . . . . 47 10.2 Turing Machines with More Complex Storage . . . . . . . . 48 10.3 Nondeterministic Turing Machines . . . . . . . . . . . . . . 50 10.4 A Universal Turing Machine . . . . . . . . . . . . . . . . . 50 10.5 Linear Bounded Automata . . . . . . . . . . . . . . . . . . 50 51 11 A Hierarchy of Formal Languages and Automata 11.1 Recursive and Recursively Enumerable Languages . . . . . 51 11.2 Unrestricted Grammars . . . . . . . . . . . . . . . . . . . . 53 11.3 Context-Sensitive Grammars and Languages . . . . . . . . 54 11.4 The Chomsky Hierarchy . . . . . . . . . . . . . . . . . . . . 55 ✐ ✐ ✐ ✐
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料