CS402 Final Term Mega File by Gumnaam Helpers

الحمدہللا گمنام ہیلپرز ان تمام کتابوں میں مدد کرتے ہیں جن کے لنکس نیچے

دیئے گ

ئۓ ہیں

لیٰذا ہم سے صرف انہی کتابوں کی مدد کا سوال کیا جائے جن کے لنکس نیچے موجود ہیں

Groups Join Krty hi Description Read krna na bhoolyn · GumNaaM_Helpers · Mega File for FinaL TerM · All Files in ONE FILE · (Handouts_waqar_moaz_junaid_vu toper_orange monkey) · جزاک ہللا خیرا و احسن الجزاء · …Paid Service Available for LMS Activities…

Only for those students who are so busy in office or work or job that they can’t

watch their LMS due to their Busyness

Table of contents:

Lecture N0. 1.................................................................................................................... 3 What does automata mean? .......................................................................................... 3 Introduction to languages.............................................................................................. 3 Alphabets...................................................................................................................... 3 Strings.......................................................................................................................... 3 Defining Languages....................................................................................................... 4 Lecture N0. 2.................................................................................................................... 7 Kleene Star Closure....................................................................................................... 7 Recursive definition of languages................................................................................... 7 Lecture N0. 3.................................................................................................................... 9 Regular Expression ....................................................................................................... 9 Recursive definition of Regular Expression(RE) .............................................................. 9 Method 3 (Regular Expressions)..................................................................................... 9 Lecture N0. 4.................................................................................................................. 10 Equivalent Regular Expressions .................................................................................. 10 Method 4 (Finite Automaton) ....................................................................................... 11 Lecture N0. 5.................................................................................................................. 13 Lecture N0. 6.................................................................................................................. 15 Equivalent FAs............................................................................................................ 15 Lecture N0. 7.................................................................................................................. 17 FA corresponding to finite languages ........................................................................... 17 Method 5 (Transition Graph)........................................................................................ 18 Lecture N0. 8.................................................................................................................. 19 Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b, containing aa, containing aa or bb............................................................................... 19 Lecture N0. 9.................................................................................................................. 21 Generalized Transition Graphs .................................................................................... 23 Lecture N0. 10 ................................................................................................................ 24 Nondeterminism.......................................................................................................... 25 Kleene’s Theorem ........................................................................................................ 25 Lecture N0. 11 ................................................................................................................ 26 Proof(Kleene’s Theorem Part II) .................................................................................... 26 Lecture N0. 12 ................................................................................................................ 30 Kleene’s Theorem Part III............................................................................................. 31 Lecture N0. 13 ................................................................................................................ 34 Lecture N0. 14 ................................................................................................................ 37 Lecture N0. 15 ................................................................................................................ 40 Nondeterministic Finite Automaton (NFA) ................................................................... 40 Converting an FA to an equivalent NFA........................................................................ 41 Lecture N0. 16 ................................................................................................................ 42 NFA with Null String ................................................................................................... 42 Lecture N0. 17 ................................................................................................................ 45 NFA and Kleene’s Theorem .......................................................................................... 45 Lecture N0. 18 ................................................................................................................ 48 NFA corresponding to Concatenation of FAs................................................................. 48 NFA corresponding to the Closure of an FA.................................................................. 50 Lecture N0. 19 ................................................................................................................ 52 Memory required to recognize a language..................................................................... 52 Distinguishable strings and Indistinguishable strings .................................................. 53 Lecture N0. 20 ................................................................................................................ 55 Finite Automaton with output...................................................................................... 55 Moore machine ........................................................................................................... 55 Lecture N0. 21 ................................................................................................................ 57 Mealy machine............................................................................................................ 57 Lecture N0. 22 ................................................................................................................ 60 Equivalent machines................................................................................................... 60 Lecture N0. 23 ................................................................................................................ 63 Lecture N0. 24 ................................................................................................................ 65 Lecture N0. 25 ................................................................................................................ 68 Nonregular languages.................................................................................................. 71 Lecture N0. 26 ................................................................................................................ 72 Pumping Lemma ......................................................................................................... 72 Lecture N0. 27 ................................................................................................................ 75 Pumping Lemma version II .......................................................................................... 75 Lecture N0. 28 ................................................................................................................ 77 Pseudo theorem .......................................................................................................... 78 Lecture N0. 29 ................................................................................................................ 79 Decidability................................................................................................................. 79 Determining whether the two languages are equivalent or not ? ................................... 80 Lecture N0. 30 ................................................................................................................ 83 Lecture N0. 31 ................................................................................................................ 87 Context Free Grammar (CFG) ...................................................................................... 87 CFG terminologies....................................................................................................... 87 Lecture N0. 32 ................................................................................................................ 90 Trees........................................................................................................................... 91 Lecture N0. 33 ................................................................................................................ 93 Polish Notation (o-o-o) ................................................................................................. 94 Lecture N0. 34 ................................................................................................................ 96 Total language tree...................................................................................................... 96 Regular Grammar ....................................................................................................... 97 Lecture N0. 35 ................................................................................................................ 99 Null Production........................................................................................................... 99 Lecture N0. 36 .............................................................................................................. 102 Chomsky Normal Form (CNF) .................................................................................... 102 Lecture N0. 37 .............................................................................................................. 105 A new format for FAs................................................................................................. 105 Lecture N0. 38 .............................................................................................................. 109 Nondeterministic PDA ............................................................................................... 111 Lecture N0. 39 .............................................................................................................. 114 PDA corresponding to CFG ........................................................................................ 114 Lecture N0. 40 .............................................................................................................. 118 Conversion form of PDA............................................................................................. 119 Lecture N0. 41 .............................................................................................................. 121 Lecture N0. 42 .............................................................................................................. 124 Lecture N0. 43 .............................................................................................................. 127 Non-Context-Free language ....................................................................................... 127 Pumping lemma for CFLs .......................................................................................... 128 Lecture N0. 44 .............................................................................................................. 133 Decidablity................................................................................................................ 133 Parsing Techniques ................................................................................................... 136 Lecture N0. 45 .............................................................................................................. 140 Turing machine......................................................................................................... 140