CIT 342 All - Home National Open University Of Nigeria
NATIONAL OPEN UNIVERSITY OF NIGERIASCHOOL OF SCIENCE AND TECHNOLOGYCOURSE CODE: CIT 342COURSE TITLE: Formal Languages and Automata Theory
COURSEGUIDECIT 342Formal Languages and Automata TheoryCourse DeveloperAfolorunso, A. A.National Open University of NigeriaLagos.Course Co-ordinatorAfolorunso, A. A.National Open University of NigeriaLagos.Course EditorProgramme LeaderProf. Kehinde ObidairoNATIONAL OPEN UNIVERSITY OF NIGERIANational Open University of NigeriaHeadquarters14/16 Ahmadu Bello WayVictoria IslandLagosAbuja Annex1
245 Samuel Adesujo Ademulegun StreetCentral Business DistrictOpposite Arewa SuitesAbujae-mail: centralinfo@nou.edu.ngURL: www.nou.edu.ngNational Open University of Nigeria 2011First Printed 2011ISBNAll Rights ReservedPrinted by .ForNational Open University of NigeriaTABLE OF CONTENTSPAGEIntroduction.3What you will learn in this Course.4Course Aims.42
Course Objectives .4Related Courses5Working through this Course.Course Materials.Study Units .Textbooks and References .Assignment File.Presentation Schedule.55-66-91010Assessment.10Tutor Marked Assignments (TMAs) .Examination and Grading.Course Marking Scheme.111112Course Overview 12-13How to Get the Best from This Course .13-155Tutors and Tutorials .Summary .31515
CIT 342Formal Languages and Automata TheoryIntroductionCIT 342 – Formal Languages and Automata Theory is a two (2) credit unit courseof 16 units. The course will cover the important formal languages in the Chomskyhierarchy -- the regular sets, the context-free languages, and the recursivelyenumerable sets -- as well as the formalisms that generate these languages and themachines that recognize them. The course will also introduce the basic concepts ofcomputability and complexity theory by focusing on the question, "What are thefundamental capabilities and limitations of computers?"The concepts covered in this course will be amply illustrated by applications tocurrent programming languages, algorithms, natural language processing, andhardware and software design.Also, in this course we shall investigate whether it is possible at all for a givenlanguage to find out if a given word belongs to it or not, and if it is possible how hardit will be. These constitute the fields of decidability theory and complexity theory,respectively.What we really want to do is to find out which problems can be solved in general, andfor those problems that can be solved, how hard it is to solve them. In order to makethese questions more precise, we encode problems as languages.Although the idea of automaton is quite old (for example a simple pendulum), it wasPost's work, contemporary with Turing, that made possible a general characterizationof machines that has been so helpful in the development of ideas ranging fromcombinational circuits to finite-state languages. Although not as powerful as themachines associated with Chomsky and Turing automata remain a very important toolin the elucidation of the inner workings of machines and provide an excellent startingpoint in understanding the basic ideas underlying contemporary science.It is a course for B. Sc. Computer science major students, and is normally taken in astudent's third year. It should appeal to anyone who is interested in the design andimplementation of programming languages. Anyone who does a substantial amount ofprogramming should find the material valuable.This course is divided into four modules. The first module deals with the generalconcepts of formal languagesThe second module treats, extensively, regular languages and the class of automata,finite state automata, that recognises strings generated by regular grammar.The third module deals with context-free languages and pushdown automataThe fourth module which is the concluding module of the course discusses Turingmachines and the rest of the language classes4
CIT 342Formal Languages and Automata TheoryThis Course Guide gives you a brief overview of the course contents, course duration,and course materials.What you will learn in this courseThe main purpose of this course is to acquaint students with the fact that languagesfall into various classes, according to their complexity. Some languages can beparsed, i.e. interpreted, by a very simple state machine. Others require the humanbrain, or something comparable.Languages also have many representations: machines that recognize them, expressionsthat describe them and grammars that generate them.Thus, we intend to achieve this through the following:Course AimsFirst, students will learn the key techniques in modern compiler construction, gettingprepared for industry demands for compiler engineers.Second, students will understand the rationale of various computational methods andanalysis.The third goal is to build the foundation for students to pursue the research in the areasof automata theory, formal languages, and computational power of machinesCourse ObjectivesCertain objectives have been set out to ensure that the course achieves its aims. Apartfrom the course objectives, every unit of this course has set objectives. In the courseof the study, you will need to confirm, at the end of each unit, if you have met theobjectives set at the beginning of each unit. Upon completing this course you shouldbe able to: Discovering computational thinkingUnderstanding the fundamental models of computation that underlie moderncomputer hardware, software, and programming languages.Discovering that there are problems no computer can solve.Discovering that there are limits as to how fast a computer can solve a problem.Learning the foundations of automata theory, computability theory, andcomplexity theory.Learning about applications of theory to other areas of computer science suchas algorithms, programming languages, compilers, natural language translation,operating systems, and software verification.Related CoursesPrerequisites: CIT 331; Computer Science students onlyWorking through This Course5
CIT 342Formal Languages and Automata TheoryIn order to have a thorough understanding of the course units, you will need to readand understand the contents, practise the steps by designing a compiler of your ownfor a known language, and be committed to learning and implementing yourknowledge.This course is designed to cover approximately seventeen weeks, and it will requireyour devoted attention. You should do the exercises in the Tutor-Marked Assignmentsand submit to your tutors.Course MaterialsThese include:1.Course Guide2.Study Units3.Recommended Texts4.A file for your assignments and for records to monitor your progress.Study UnitsThere are 16 study units in this course:Module 1: General ConceptsUnit 1: Alphabets, Strings, and RepresentationsUnit 2: Formal GrammarsUnit 3: Formal LanguagesUnit 4: Automata TheoryModule 2: Regular LanguagesUnit 1: Finite State AutomataUnit 2: Regular ExpressionsUnit 3: Regular GrammarsUnit 4: Closure Properties of Regular LanguagesUnit 5: The Pumping LemmaModule 3: Context-Free LanguagesUnit 1: Context-Free GrammarsUnit 2: Properties of Context-Free LanguagesUnit 3: Pushdown AutomataUnit 4: CFGs and PDAsModule 4: Turing MachinesUnit 1: Turing Machines and the restUnit 2: Turing Machines and Context-Sensitive GrammarsUnit 3: Unrestricted GrammarsMake use of the course materials, do the exercises to enhance your learning.Textbooks and References6
CIT .20.Formal Languages and Automata TheoryBryant, Randal E.; David, O'Hallaron (2003), Computer Systems: AProgrammer's Perspective (2003 ed.), Upper Saddle River, NJ: PearsonEducationJohn E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory,Languages, and Computation, Addison-Wesley Publishing, ReadingMassachusetts, 1979Chomsky, Noam (1956). "Three Models for the Description of Language". IRETransactions on Information Theory 2 (2): 113–123.Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton.Ginsburg, Seymour (1975). Algebraic and automata theoretic properties offormal languages. North-Holland. pp. 8–9.Harrison, Michael A. (1978). Introduction to Formal Language Theory.Reading, Mass.: Addison-Wesley Publishing Company.Sentential Forms, Context-Free Grammars, David MatuszekGrune, Dick & Jacobs, Ceriel H., Parsing Techniques – A Practical Guide,Ellis Horwood, England, 1990.Earley, Jay, "An Efficient Context-Free Parsing Algorithm," Communicationsof the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.Joshi, Aravind K., et al., "Tree Adjunct Grammars," Journal of ComputerSystems Science, Vol. 10 No. 1, pp. 136-163, 1975.Koster , Cornelis H. A., "Affix Grammars," in ALGOL 68 Implementation,North Holland Publishing Company, Amsterdam, p. 95-109, 1971.Knuth, Donald E., "Semantics of Context-Free Languages," MathematicalSystems Theory, Vol. 2 No. 2, pp. 127-145, 1968.Knuth, Donald E., "Semantics of Context-Free Languages (correction),"Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.Birman, Alexander, The TMG Recognition Schema, Doctoral thesis, PrincetonUniversity, Dept. of Electrical Engineering, February 1970.Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar,"Technical Report CMU-CS-91-196, Carnegie Mellon University ComputerScience, 1991.Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar,"Third International Workshop on Parsing Technologies, 1993. (Revisedversion of above report.)Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm withBacktracking, Master’s thesis, Massachusetts Institute of Technology, Sept.2002.John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction toAutomata Theory, Languages, and Computation (2nd Edition). PearsonEducation.Michael Sipser (1997). Introduction to the Theory of Computation. PWSPublishing.James P. Schmeiser, David T. Barnard (1995). Producing a top-down parseorder with bottom-up parsing. Elsevier North-Holland.7
CIT 342Formal Languages and Automata TheoryAssignments FileThese are of two types: the self-assessment exercises and the Tutor-MarkedAssignments. The self-assessment exercises will enable you monitor yourperformance by yourself, while the Tutor-Marked Assignment is a supervisedassignment. The assignments take a certain percentage of your total score in thiscourse. The Tutor-Marked Assignments will be assessed by your tutor within aspecified period. The examination at the end of this course will aim at determining thelevel of mastery of the subject matter. This course includes sixteen Tutor-MarkedAssignments and each must be done and submitted accordingly. Your best scoreshowever, will be recorded for you. Be sure to send these assignments to your tutorbefore the deadline to avoid loss of marks.Presentation ScheduleThe Presentation Schedule included in your course materials gives you the importantdates for the completion of tutor marked assignments and attending tutorials.Remember, you are required to submit all your assignments by the due date. Youshould guard against lagging behind in your work.AssessmentThere are two aspects to the assessment of the course. First are the tutor markedassignments; second, is a written examination.In tackling the assignments, you are expected to apply information and knowledgeacquired during this course. The assignments must be submitted to your tutor forformal assessment in accordance with the deadlines stated in the Assignment File. Thework you submit to your tutor for assessment will count for 30% of your total coursemark.At the end of the course, you will need to sit for a final three-hour examination. Thiswill also count for 70% of your total course mark.Tutor Marked Assignments (TMAS)There are twenty-two tutor marked assignments in this course. You need to submit allthe assignments. The total marks for the best three (3) assignments will be 30% ofyour total course mark.Assignment questions for the units in this course are contained in the Assignment File.You should be able to complete your assignments from the information and materialscontained in your set textbooks, reading and study units. However, you may wish touse other references to broaden your viewpoint and provide a deeper understanding ofthe subject.8
CIT 342Formal Languages and Automata TheoryWhen you have completed each assignment, send it together with form to your tutor.Make sure that each assignment reaches your tutor on or before the deadline given. If,however, you cannot complete your work on time, contact your tutor before theassignment is done to discuss the possibility of an extension.Examination and GradingThe final examination for the course will carry 70% percentage of the total marksavailable for this course. The examination will cover every aspect of the course, soyou are advised to revise all your corrected assignments before the examination.This course endows you with the status of a teacher and that of a learner. This meansthat you teach yourself and that you learn, as your learning capabilities would allow. Italso means that you are in a better position to determine and to ascertain the what, thehow, and the when of your language learning. No teacher imposes any method oflearning on you.The course units are similarly designed with the introduction following the table ofcontents, then a set of objectives and then the dialogue and so on.The objectives guide you as you go through the units to ascertain your knowledge ofthe required terms and expressions.Course Marking SchemeThis table shows how the actual course marking is broken down.AssessmentAssignment 1- 4Final ExaminationTotalMarksFour assignments, best three marks of the fourcount at 30% of course marks70% of overall course marks100% of course marksTable 1: Course Marking SchemeCourse OverviewUnitTitle of WorkCourse GuideWeeksAssessmentActivity(End of Unit)Week 1Module 1: General Concepts1Unit 1: Alphabets, Strings, and RepresentationsWeek 1Assignment 19
CIT 342Formal Languages and Automata Theory2Unit 2: Formal GrammarsWeek 2Assignment 23Unit 3: Formal LanguagesWeek 2Assignment 34Unit 4: Automata TheoryModule 2: Regular Languages1Unit 1: Finite State AutomataWeek 3Assignment 52Unit 2: Regular ExpressionsWeek 3Assignment 63Unit 3: Regular GrammarsWeek 4Assignment 74Unit 4: Closure PropertiesLanguagesUnit 5: The Pumping Lemma5ofRegular Week 4Module 3: Context-Free Languages1Unit 1: Context-Free GrammarsWeek 5Assignment 82Unit 2: Properties of Context-Free LanguagesWeek 6Assignment 93Unit 3: Pushdown AutomataWeek 7 - 8Assignment 104Unit 4: CFGs and PDAsWeek 8 - 9Assignment 111Module 4: Turing MachinesUnit 1: Turing Machines and the restWeek 12Assignment 13Unit 2: Turing Machines and Context-Sensitive Week 13GrammarsUnit 3: Unrestricted GrammarsWeek 14Assignment 1423RevisionWeek 16ExaminationWeek 17TotalAssignment 1517 weeksHow to get the best from this courseIn distance learning the study units replace the university lecturer. This is one of thegreat advantages of distance learning; you can read and work through speciallydesigned study materials at your own pace, and at a time and place that suit you best.Think of it as reading the lecture instead of listening to a lecturer. In the same waythat a lecturer might set you some reading to do, the study units tell you when to readyour set books or other material. Just as a lecturer might give you an in-class exercise,your study units provide exercises for you to do at appropriate points.Each of the study units follows a common format. The first item is an introduction tothe subject matter of the unit and how a particular unit is integrated with the other10
CIT 342Formal Languages and Automata Theoryunits and the course as a whole. Next is a set of learning objectives. These objectivesenable you know what you should be able to do by the time you have completed theunit. You should use these objectives to guide your study. When you have finishedthe units you must go back and check whether you have achieved the objectives. Ifyou make a habit of doing this you will significantly improve your chances of passingthe course.Remember that your tutor’s job is to assist you. When you need help, don’t hesitate tocall and ask your tutor to provide it.1.Read this Course Guide thoroughly.2.Organize a study schedule. Refer to the ‘Course Overview’ for more details.Note the time you are expected to spend on each unit and how the assignmentsrelate to the units. Whatever method you chose to use, you should decide on itand write in your own dates for working on each unit.3.Once you have created your own study schedule, do everything you can to stickto it. The major reason that students fail is that they lag behind in their coursework.4.Turn to Unit 1 and read the introduction and the objectives for the unit.5.Assemble the study materials. Information about what you need for a unit isgiven in the ‘Overview’ at the beginning of each unit. You will almost alwaysneed both the study unit you are working on and one of your set of books onyour desk at the same time.6.Work through the unit. The content of the unit itself has been arranged toprovide a sequence for you to follow. As you work through the unit you will beinstructed to read sections from your set books or other articles. Use the unit toguide your reading.7.Review the objectives for each study unit to confirm that you have achievedthem. If you feel unsure about any of the objectives, review the study materialor consult your tutor.8.When you are confident that you have achieved a unit’s objectives, you canthen start on the next unit. Proceed unit by unit through the course and try topace your study so that you keep yourself on schedule.9.When you have submitted an assignment to your tutor for marking, do not waitfor its return before starting on the next unit. Keep to your schedule. Whenthe assignment is returned, pay particular attention to your tutor’s comments,both on the tutor-marked assignment form and also written on the assignment.Consult your tutor as soon as possible if you have any questions or problems.11
CIT 34210.Formal Languages and Automata TheoryAfter completing the last unit, review the course and prepare yourself for thefinal examination. Check that you have achieved the unit objectives (listed atthe beginning of each unit) and the course objectives (listed in this CourseGuide).Tutors and TutorialsThere are 8 hours of tutorials provided in support of this course. You will be notifiedof the dates, times and location of these tutorials, together with the name and phonenumber of your tutor, as soon as you are allocated a tutorial group.Your tutor will mark and comment on your assignments, keep a close watch on yourprogress and on any difficulties you might encounter and provide assistance to youduring the course. You must mail or submit your tutor-marked assignments to yourtutor well before the due date (at least two working days are required). They will bemarked by your tutor and returned to you as soon as possible.Do not hesitate to contact your tutor by telephone, or e-mail if you need help. Thefollowing might be circumstances in which you would find help necessary. Contactyour tutor if: you do not understand any part of the study uni
CIT 342 Formal Languages and Automata Theory 4 Introduction CIT 342 – Formal Languages and Automata Theory is a two (2) credit unit course of 16 units. The course will cover the important formal languages in the Chomsky hierarchy -- the regular sets, the context-fre
CIT 145 Perl I CIT 146 Swift I CIT 237 iOS Programming CIT 238 Android Programming CIT 241 PHP II CIT 242 C II Approved Level II Programming Language Courses INF 120 Elementary Programming Course CIT 144 Python I CIT 148 Visual Basic I Approved Level I Programming Language Courses CIT
Wells Fargo Enhanced Stock Market CIT 101 Wells Fargo Factor Enhanced Large Cap Core CIT (formerly, Wells Fargo Factor Enhanced Large Cap Index CIT) 107 Wells Fargo Fundamental Small Cap Growth CIT 123 Wells Fargo Growth CIT 126 Wells Fargo Large Cap Intrinsic Value CIT 129 Wells Fargo Liability Driven Solution CIT I 131
clients. CIT relies upon Corporate Function employees provided by CITBNA and CIT Group (NJ) LLC ("CIT NJ") for centralized corporate and administrative services, including certain members of CIT's executive management team. CIT has entered into a mutual services agreement with CITBNA that allows for the provision and receipt of general .
CIT 342 Formal Languages and Automata Theory Introduction CIT 342 – Formal Languages and Automata Theory is a two (2) credit unit course of 16 units. The course will cover the important formal languages in the Chomsky hierarchy -- the regu
CIT-1, CIT-A, CIT-B, CIT-C, Vouchers - 1 - www.tax.newmexico.gov Contact Information You can contact the Department by mail, email, or phone. New Mexico Taxation and Revenue Department Corporate Income and Franchise Tax P. O. Box 25127 Santa Fe, NM 87504-5127 CIT.TaxReturnHelp@state.nm.us
astm a266/a266m-13 342, 345 astm a333/a333m-13 246, 249 astm a334/a334m-04a (2010) 246, 249 astm a485-14 628 astm a508/a508m-14 343, 346 astm a537/a537m-13 115, 125 astm a541/a541m-05 (2015) 342, 345 1a asme sa-508/sa-508m 342, 345 asme sa-541/sa-541m 342, 345 astm a508/a508m-14 343, 346 astm a541/a541m-05 (2015) 342, 345 1cr12 gb 1220-92 519, 522 gb 3280-92 438, 440 gb 4226-84 519 gb 4237-92 .
Aug 05, 2017 · CIT Linux Lab Manual 2017-08-05 2 CIT Linux Lab Manual Introduction The following manual presents basic information necessary for students utilizing the College of Southern Nevada’s (CSN) Linux Server in conjunction with a variety of CIT, CS, and IS courses. Many of the po
playing field within the internal market, even in exceptional economic circumstances. This White Paper intends to launch a broad discussion with Member States, other European institutions, all stakeholders, including industry, social partners, civil society organisations,
