Mathematical Foundation of Computer Science

DHARM 184 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE = k∪= i 1 δ(,)pk a = { r 1 , r 2 , r 3 , ............, rj}‡ Abstract view ...

DHARM INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 185 Then we check the behavior of N over the string 101101, from the startin ...

DHARM 186 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Therefore, the only acceptable path from starting state q 0 is shown by da ...

DHARM INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 187 (iii) PPQ QPQQ (^01) State Input SymbolInputSymbol PQ P Q 7.4 Construct ...

DHARM 188 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE P ()d Q R U 1 (^01) S 00 1 T 0 1, 0 1 P ()e Q R U 1 (^01) S 00 1 T 0 1, 0 ...

DHARM INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 189 E 1 S A 1 C F H 1 1 1 0 0 0 0 D B G 0 0 1 0 1 0 1 Fig. 7.25 ...

THIS PAGE IS BLANK ...

EQUIVALENCE OF NFA AND DFA 8.1 Relationship between NFA & DFA............................................................... ...

8.1 RELATIONSHIP BETWEEN NFA AND DFA Now we will discuss the relationship between finite automatons DFA & NFA and simultane- ...

DHARM EQUIVALENCE OF NFA AND DFA 193 Now we shall prove that the theorem is true for string length (n + 1), hence through induct ...

DHARM 194 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE I. Since, QD ⊆ P (Q) or power set of Q where Q = {q 0 , q 1 , q 2 , q 3 }, ...

DHARM EQUIVALENCE OF NFA AND DFA 195 Hence, we obtain the following transition Table (TT) for all possible states of DFA. States ...

DHARM 196 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE · From state {q 0 , q 2 } next reachable states are {q 0 , q 1 , q 3 } and ...

DHARM EQUIVALENCE OF NFA AND DFA 197 Sol. Let DFA be M, where M = {QD, Σ, δD, {q0D}, FD}. Now determine the tuples of M from kno ...

DHARM 198 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE · Reachable states from {q 2 } are : {q 3 } and {q 0 } that was earlier vi ...

DHARM EQUIVALENCE OF NFA AND DFA 199 q p Î So it shows a spontaneous transition of state from state q to state p known as ∈-tran ...

DHARM 200 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE For example, consider the NFA with ∈-moves shown in Fig. 8.7 so we can fin ...

DHARM EQUIVALENCE OF NFA AND DFA 201 Similarly we can compute δ$(q 0 , 1) as, δ$ ∈(q 0 , 1) = δ$ ∈(q 0 , ∈. 1) = δ∈($δ∈(q 0 , ∈) ...

DHARM 202 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE The definition of transition functions δ for NFA (over each symbol of Σ) c ...

DHARM EQUIVALENCE OF NFA AND DFA 203 And the transition diagram for NFA is shown in Fig. 8.10. 0, 1 q 0 1, 2 q 1 q 2 0, 1, 2 2 0 ...