CS402 Official Handouts

Table of contents:

Lecture N0. 1.................................................................................................................... 3

Alphabets...................................................................................................................... 3 Strings.......................................................................................................................... 3

Lecture N0. 2.................................................................................................................... 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 Regular languages....................................................................................................... 65 Complement of a language .......................................................................................... 66 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

Last Updated: December 20, 2011

[Please see Errata if you have copy of handouts printed before this date]

Lecture N0. 1

Chapter 2

Summary

Introduction to the course title, Formal and In-formal languages, Alphabets, Strings, Null string, Words, Valid and In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { an bn}, { an bn an }, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME.

What does automata mean?

It is the plural of automaton, and it means “something that works automatically”

There are two types of languages

Formal Languages (Syntactic languages) Informal Languages (Semantic languages)

Alphabets

A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by Σ ( Greek letter sigma).

Example Σ = {a,b} Σ = {0,1} (important as this is the language which the computer understands.) Σ = {i,j,k}

Note Certain version of language ALGOL has 113 letters. Σ (alphabet) includes letters, digits and a variety of operators including sequential operators such as GOTO and IF

Strings

Concatenation of finite number of letters from the alphabet is called a string.

Example If Σ = {a,b} then a, abab, aaabb, ababababababababab

Note

Empty string or null string Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ or (Capital Greek letter Lambda) Λ, is called an empty string or null string. The capital lambda will mostly be used to denote the empty string, in further discussion.

Words

Words are strings belonging to some language.

Example If Σ= {x} then a language L can be defined as L={xn : n=1,2,3,…..} or L={x,xx,xxx,….} Here x,xx,… are the words of L

Note