Mathematical Foundation of Computer Science

DHARM 324 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (∵ X 1 ⇒ X 2 B is the defined prodn. Here α 2 is A and β 2 is B so | a 2 b ...

DHARM NON-REGULAR GRAMMARS 325 Induction Hypothesis Assume that fact is true for all ranks ≤ r – 1. Then examine, for node rank ...

DHARM 326 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Then, xi,j and Vi,j are as follows, Case I. for the substring of length on ...

DHARM NON-REGULAR GRAMMARS 327 Now CYK algorithm starts with CNF grammar of G. So, convert the grammar G into CNF that is, (+) X ...

DHARM 328 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE So, V1,2 = V1,1 * V2,1 (take the values from column one that are earlier f ...

DHARM NON-REGULAR GRAMMARS 329 or V1,2 * V3,2 = {S} * {S} = {SS} we find nothing. or V1,3 * V4,1 = {B} * {A, X} and find nothing ...

DHARM 330 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE But for the case of CFLs there is no answer of this question. Why? Because ...

DHARM NON-REGULAR GRAMMARS 331 11.2 Construct the grammar for the given language and identify the types of language. (i)L = {an ...

DHARM 332 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (iii)S → 0S0/1S1/∈ A → 0B1/1B0 B → 0B/1B/∈ (iv)S → abSb/a/aAb, A → bS/aAAb ...

12.1 Introduction............................................................................................................... ...

12.1INTRODUCTION We have discussed so far comperatively small and simple classes of languages which are regular languages and co ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 335 A cell contains no input symbol and no tape symbol certainly contain ...

DHARM N-COM\CMS12-1.PM5 336 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Note: It is always remember that 1.Machine crashes if δ ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 337 This situation is shown in Fig. 12.3. X 1 ............ XK XK+2 ..... ...

DHARM N-COM\CMS12-1.PM5 338 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE a b a b q a bb p X ()a ()b Fig. 12.6 As usual a state is ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 339 •δ(q 1 , B) = (q 2 , B, L) // find the last b •δ(q 2 , b) = (q 3 , B ...

DHARM N-COM\CMS12-1.PM5 340 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE replace starting symbol a by X, then reaches to the fir ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 341 The first symbol a is replaced by X (we count one a); skip all a’s ...

DHARM N-COM\CMS12-1.PM5 342 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Example 12.3. Construct the Turing machine for the langu ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 343 That is, to shift the complete string β one cell right and to push a ...