Mathematical Foundation of Computer Science
DHARM 204 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Example 8.2. Construct a DFA from given NFA (as shown in Fig. 8.7) q 0 Î q ...
DHARM EQUIVALENCE OF NFA AND DFA 205 δ({q 1 , q 2 }, 1) = ∈-closure [δ({q 1 , q 2 }, 1)] = ∈-closure [δ(q 1 , 1) ∪ δ(q 2 , 1)] = ...
DHARM 206 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Example 8.3. Construct an equivalent DFA for given NFA with ∈-moves (Fig. ...
DHARM EQUIVALENCE OF NFA AND DFA 207 δ({A, B, C,D}, 0) = ∈-closure [δ({A,B,C,D}, 0)] = ∈-closure [δ(A, 0) ∪ δ(B, 0) ∪ δ(C, 0) ∪ ...
DHARM 208 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 1 ABCD 0 BD CD F D ABD 0 0 1 0 1 (^10) 1, 0 1 Fig. 8.14 Note. The nature o ...
DHARM EQUIVALENCE OF NFA AND DFA 209 (iii) State 0 Î 1 q 0 q 1 q 2 q 3 {}q 2 {}q 1 {}q 0 {}q2ss FFF {}q 3 {}q 1 {}q 2 (c) {}q 3 ...
THIS PAGE IS BLANK ...
REGULAR EXPRESSIONS 9.1 Introduction to Regular Expressions..................................................................... ...
9 Regular Expressions 212 9.1 INTRODUCTION TO REGULAR EXPRESSIONS In the previous chapter we have studied that the power of a fi ...
DHARM REGULAR EXPRESSIONS 213 language L(r 1 ) ∪ L(r 2 ). This property of regular expression is known as ‘addition property of ...
DHARM 214 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (a)( 0 + 1 ) is a regular expression, which generates the language {0, 1}. ...
DHARM REGULAR EXPRESSIONS 215 (0 + 1)*. 0 or 0. (0 + 1)* ⇒ (0 + 1)*. 0. (0 + 1)* where, L[( 0 + 1 )*. 0. ( 0 + 1 )*] = {0, 00, 0 ...
DHARM 216 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 9.3 Equivalence of Regular Expression and Finite Automata................. ...
DHARM REGULAR EXPRESSIONS 217 (Provided that N∈ has only one final state and there is no outgoing arc from the final state) Proo ...
DHARM 218 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE q p All transitions between states that accepts the language L( )r 1 NÎ 1 ...
DHARM REGULAR EXPRESSIONS 219 Case 2 (Concatenation operation) Construct the automaton N∈ for the language L(r) where, L(r) = L( ...
DHARM 220 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE l and δ∈ will be defined as, δ∈(q, ∈) = {q 1 } or δ∈(q, ∈) = {p} and, δ∈(p ...
DHARM REGULAR EXPRESSIONS 221 Therefore, DFA converges to Regular Expression. There relationship is pictured in Fig. 9.5. DFA NF ...
DHARM 222 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Î Î Î Î Î Î a a b Î Î Î b N΢² Î Step 4. Do the concatenation construction ...
DHARM REGULAR EXPRESSIONS 223 9.3.2 Construction of DFA from Regular Expression................................................ ...
«
7
8
9
10
11
12
13
14
15
16
»
Free download pdf