Mathematical Foundation of Computer Science

DHARM 224 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (For the acceptance of the string 0011) Since, at state E return string is ...

DHARM REGULAR EXPRESSIONS 225 (^0) D E 1 A B C 1 0 1 0 0 F 1 0, 1 0, 1 Fig. 9.7 Since automaton shown in Fig. 9.7 fulfills the d ...

DHARM 226 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE from A, 1 from P and 1 from Q must terminate to state Ø. Thus we get the a ...

DHARM REGULAR EXPRESSIONS 227 b a a b b a a a b 4 2 3 8 1 7 5 6 Fig. 9.11 For example, consider a state diagram shown in Fig. 9. ...

DHARM 228 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Consideration of paths are shown in Fig. 9.12, where following possibiliti ...

DHARM REGULAR EXPRESSIONS 229 Example 9.6. Construct the regular expression for the DFA shown in Fig. 9.13. 1 1 2 0 1 0 Fig. 9.1 ...

DHARM 230 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE State Language Regular Transition Expression from 1 → 1 1 R 11 Choice in b ...

DHARM REGULAR EXPRESSIONS 231 9.5 Construction of Regular Expression from DFA................................................... ...

DHARM 232 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Example 9.7. Convert the following DFA to regular expression. 1 4 2 3 1 0 ...

DHARM REGULAR EXPRESSIONS 233 l The regular expression for the incoming arc from state 2 to 3 on symbol 0 is 0 and the regular e ...

DHARM 234 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE This section introduces other forms of finite automatons, which operates o ...

DHARM REGULAR EXPRESSIONS 235 B C a, b b A a a b M Fig. 9.25 Now if we put another symbol on each transition arc provided that i ...

DHARM 236 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE which is again the partial mapping of a state (∈ Q) with an input symbol ( ...

DHARM REGULAR EXPRESSIONS 237 The Melay machine shown in Fig. 9.29 is the 1’s complement machine where Me = ({q 0 }, {0, 1}, {0, ...

DHARM 238 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Now assume that these carry positions represent three different states suc ...

DHARM REGULAR EXPRESSIONS 239 sequence of transitions between states is responsible for generating the output. For example, a fi ...

DHARM 240 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Assume that states r 0 , r 1 and r 2 are represented by symbol 0, 1 and 2 ...

DHARM REGULAR EXPRESSIONS 241 From starting state r 0 , if input number is 0 then it returns the number 0((0) 2 mod 3 = 0) Other ...

DHARM 242 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 9.7.1 Equivalent Machine Construction (From Moore machine-to-Melay Machine ...

DHARM REGULAR EXPRESSIONS 243 Hence, the state diagram of equivalent Melay machine is constructed and which is shown below in Fi ...