Mathematical Foundation of Computer Science

DHARM 244 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE l Start state of Moore machine is defined as [r 0 , b], where r 0 is the s ...

DHARM REGULAR EXPRESSIONS 245 Table I State Input symbol 0 C 0 1 0 1 0 1 0 1 C 1 C 2 And the transition function (δe) is shown i ...

DHARM 246 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Table III State Input symbol 0 [C , 0] 0 1 [C , 1] 0 [C , 0] 1 [C , 1] 1 [ ...

DHARM REGULAR EXPRESSIONS 247 Sol. Construct the output function (λe) table I for the given Moore machine. Table I State Input s ...

DHARM 248 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Hence, we prepare a transition function table III for Moore machine. Table ...

DHARM REGULAR EXPRESSIONS 249 9.2 Write regular expressions for each of the following languages over the alphabet {a, b}. (i) Al ...

DHARM 250 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 0 0, 1 0, 1 0, 1 0, 1 1 ()e 0, 1 0, 1 0, 1 1 0 0 1 ()f 0 0 0 0 0 1 1 1 1 0 ...

DHARM REGULAR EXPRESSIONS 251 (^11) ()j 0 0 1 (^100) 1 0 1 0 1 0, 1 0 ()k Fig. 9.46 9.8 Comment on the property of the given Mel ...

THIS PAGE IS BLANK ...

10.1 Introduction............................................................................................................... ...

10 Regular and Nonregular Languages 254 10.1INTRODUCTION From exploring the knowledge of the previous chapters, for checking the ...

DHARM REGULAR AND NONREGULAR LANGUAGES 255 followed by substring w then we always locate a middle substring v (in between of len ...

DHARM 256 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Therefore string v can be pumped as many as you can such that the resultin ...

DHARM REGULAR AND NONREGULAR LANGUAGES 257 Remaining (n – 1) set of n number of 0’s are in w. For the base case of pumping lemma ...

DHARM 258 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE ⇒ (2n + m) < | u. v^2. w | < (2n + m) + n ; [to make equal, number o ...

DHARM REGULAR AND NONREGULAR LANGUAGES 259 Let regular language is defined over set of symbols Σ, then complement of L returns a ...

DHARM 260 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE L(M′) = L (∈∈∈∈∈ + 0. 1) = {∈∈∈∈∈, 0, 01, 011, .....} and, L(M) = L [(1 + ...

DHARM REGULAR AND NONREGULAR LANGUAGES 261 Example 10.5. Two DFAs M 1 and M 2 are shown in Fig 10.6. Construct the machine that ...

DHARM 262 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE {A, P} 0 {A, Q} {A, R} 0 {B, P} {B, Q} {B, R} 0 0, 1 0 1 (^11) 1 0 1 Fig. ...

DHARM REGULAR AND NONREGULAR LANGUAGES 263 Lemma 10.2. Let r is a regular expression and it generates the language L. Assume reg ...