CIT 342: FORMAL LANGUAGES AND AUTOMATA THEORY

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 units or the assigned readings,you have difficulty with the self-tests or exercises,you have a question or problem with an assignment, with your tutor‘scomments on an assignment or with the grading of an assignment.You should try your best to attend the tutorials. This is the only chance to have faceto face contact with your tutor and to ask questions which are answered instantly. Youcan raise any problem encountered in the course of your study. To gain the maximumbenefit from course tutorials, prepare a question list before attending them. You willlearn a lot from participating in discussions actively.SummaryFormal Languages and Automata Theory introduces you to the concepts associatedlanguages, computation and machines. It uses mathematical structure, and certain axiomatic rules(formal grammar) to describe translation of programs written in computer languages. The notionsand methods of formal language are analogous to those used in number theory and in logic. This review broughtin latest developments in computer technology such as the recognition neurons in artificial intelligence androbotic programming.The content of the course material was planned and written to ensure thatyou acquire the proper knowledge and skills, which you will find useful in a later course(CIT 445: Principles and Techniques of Compilers) in you fourth year and also for theappropriate situations later in life. Real-life situations have been created to enable youidentify with and create some of your own. The essence is to help you in acquiringthe necessary knowledge and competence by equipping you with the necessary tools toaccomplish this.We hope that by the end of this course you would have acquired the required

knowledge to view computation, machines, and programming languages in a newway.We wish you success with the course and hope that you will find it both interestingand useful.

Module 1: General ConceptsUnit 1: Alphabets, Strings, and ivesMain Content3.1Alphabets3.2String3.2.1 Formal Theory3.2.2 Strings and Sets of Strings3.2.3 Alphabet of a string3.2.4 String substitution3.2.5 Concatenation and Substrings3.2.6 String length3.2.7 Character String 6.0Tutor-Marked Assignment7.0 References/Further Reading1.0INTRODUCTIONThe ability to represent information is crucial to communicating and processinginformation. Human societies created spoken languages to communicate on a basiclevel, and developed writing to reach a more sophisticated level.The English language, for instance, in its spoken form relies on some finite set ofbasic sounds as a set of primitives. The words are defined in term of finite sequencesof such sounds. Sentences are derived from finite sequences of words. Conversationsare achieved from finite sequences of sentences, and so forth.Written English uses some finite set of symbols as a set of primitives. The words aredefined by finite sequences of symbols. Sentences are derived from finite sequencesof words. Paragraphs are obtained from finite sequences of sentences, and so forth.Similar approaches have been developed also for representing elements of other sets.For instance, the natural number can be represented by finite sequences of decimaldigits.Computations, like natural languages, are expected to deal with information in itsmost general form. Consequently, computations function as manipulators of integers,14

CIT 342Formal Languages and Automata Theorygraphs, programs, and many other kinds of entities. However, in reality computationsonly manipulate strings of symbols that represent the objects. The subsequentdiscussions in this course necessitate the following definitions.In this introductory unit of this course, you will be taken through some of thesedefinitions.Now let us go through your study objectives for this unit.2.0OBJECTIVESAt the end of this unit, you should be able to:o define alphabet, words and stringso state the basic relation relationship among these termso state and describe the various operations that can be carried out on thisstructureso describe how they can be represented3.0MAIN CONTENT3.1AlphabetsIn computer science and formal language, an alphabet or vocabulary is a finite set ofsymbols or letters, e.g. characters or digits. The most common alphabet is {0,1}, thebinary alphabet. A finite string is a finite sequence of letters from an alphabet; forinstance a binary string is a string drawn from the alphabet {0,1}. An infinitesequence of letters may be constructed from elements of an alphabet as well.Given an alphabet Σ, we write Σ* to denote the set of all finite strings over thealphabet Σ. Here, the * denotes the Kleene star operator. We write(or occasionally,or Σω) to denote the set of all infinite sequences over the alphabet Σ.For example, if we use the binary alphabet {0,1}, the strings (ε, 0, 1, 00, 01, 10, 11,000, etc.) would all be in the Kleene closure of the alphabet (where ε represents theempty string)Please note that alphabets are important in the use of formal languages, automata andsemi-automata. In most cases, for defining instances of automata, such asdeterministic finite automata (DFAs), it is required to specify an alphabet from whichthe input strings for the automaton are built.3.2StringIn formal languages, which are used in mathematical logic and theoretical computerscience, a string is a finite sequence of symbols that are chosen from a set or alphabet.

CIT 342Formal Languages and Automata TheoryIn computer programming, a string is, essentially, a sequence of characters. A string isgenerally understood as a data type storing a sequence of data values, usually bytes, inwhich elements usually stand for characters according to a character encoding, whichdifferentiates it from the more general array data type. In this context, the termsbinary string and byte string are used to suggest strings in which the stored datadoes not (necessarily) represent text.A variable declared to have a string data type usually causes storage to be allocated inmemory that is capable of holding some predetermined number of symbols. When astring appears literally in source code, it is known as a string literal and has arepresentation that denotes it as such. Before, we start the lecture, let us have a watch of thisvideo: https://www.youtube.com/watch?v mAmZvn9lKYk3.2.1 Formal TheoryLet Σ be an alphabet, a non-empty finite set. Elements of Σ are called symbols orcharacters. A string (or word) over Σ is any finite sequence of characters from Σ. Forexample, if Σ {0, 1}, then 0101 is a string over Σ.The length of a string is the number of characters in the string (the length of thesequence) and can be any non-negative integer. The empty string is the unique stringover Σ of length 0, and is denoted ε or λ.The set of all strings over Σ of length n is denoted Σn. For example, if Σ {0, 1}, thenΣ2 {00, 01, 10, 11}. Note that Σ0 {ε} for any alphabet Σ.The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*.In terms of Σn,For example, if Σ {0, 1}, Σ* {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, }.Although Σ* itself is countably infinite, all elements of Σ* have finite length.A set of strings over Σ (i.e. any subset of Σ*) is called a formal language over Σ. Forexample, if Σ {0, 1}, the set of strings with an even number of zeros ({ε, 1, 00, 11,001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, }) is a formallanguage over Σ.3.2.2 Strings and Sets of StringsIf V is a set, then V* denotes the set of all finite strings of elements of V{0,1}* {ε, 0, 1, 00, 01,including the empty string which will be denoted by ε. e.g.10, 11, 000, 001,. }

CIT 342Formal Languages and Automata TheoryThe set of all non empty strings of elements of V is denoted by V .Usually, V V* \ {ε}, but when ε V, V V*. e.g.{0,1} {0, 1, 00, 01, 10, 11, 000, 001,.}but{ε, 0, 1} {0,1}* {ε, 0, 1, 00, 01, 10, 11, 000, 001,. }If x V* and y V* then xy will denote their concatenation, that is, the stringconsisting of x followed by y.If x V* then xn xxx.xn-timesn 0We assume x0 ε the empty string.{a}* {ε, a, a2, a3, .an,.} { an: n 0}e.g.{a} {a, a2, a3, .an, .} { an: n 1}Similarly, if X, Y are sets of strings, then their concatenation is also denotedby XY. Of course XY {xy: x X and y Y}.Also, Xn XXX.X n 0. Of course X0 {ε}.n-timese.g.{0, 1} {a, b, c} {0a, 0b, 0c, 1a ,1b, 1c}{0, 1}3 {000, 001, 010, 011, 100, 101, 110, 111}If x is a string, then x denotes the length of x, and this is the number ofindivisible symbols in x. Of course ε 0.Self Assessment Exercise I1. State the differences if any between an alphabet and stringn2. If Σ {0, 1}, what is Σ when n 43) Determine the following sets.(a) {0,1} {ε, a, ba}(b) {b, aa}*4. Let V be a set of strings. Does V V V* ?3.2.3 Alphabet of a stringThe alphabet of a string is a list of all of the letters that occur in a particular string. Ifs is a string, its alphabet is denoted byAlph(s)3.2.4 String substitution

CIT 342Formal Languages an

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