DESKTOP

# Algorithms for Compiler Design: EXAMPLES OF FINITE AUTOMATA CONSTRUCTION

7/24/2010 7:58:40 PM
##### 2.7 EXAMPLES OF FINITE AUTOMATA CONSTRUCTION EXAMPLE 1 Construct a finite automata accepting the set of all strings of zeros and ones, with at most one pair of consecutive zeros and at most one pair of consecutive ones. A transition diagram of the finite automata accepting the set of all strings of zeros and ones, with at most one pair of consecutive zeros and at most one pair of consecutive ones is shown in Figure 1. EXAMPLE 2 Construct a finite automata that will accept strings of zeros and ones that contain even numbers of zeros and odd numbers of ones. A transition diagram of the finite automata that accepts the set of all strings of zeros and ones that contains even numbers of zeros and odd numbers of ones is shown in Figure 2. EXAMPLE 3 Construct a finite automata that will accept a string of zeros and ones that contains an odd number of zeros and an even number of ones. A transition diagram of finite automata accepting the set of all strings of zeros and ones that contains an odd number of zeros and an even number of ones is shown in Figure 3. EXAMPLE 4 Construct the finite automata for accepting strings of zeros and ones that contain equal numbers of zeros and ones, and no prefix of the string should contain two more zeros than ones or two more ones than zeros. A transition diagram of the finite automata that will accept the set of all strings of zeros and ones, contain equal numbers of zeros and ones, and contain no string prefixes of two more zeros than ones or two more ones than zeros is shown in Figure 4. EXAMPLE 5 Construct a finite automata for accepting all possible strings of zeros and ones that do not contain 101 as a substring. Figure 5 shows a transition diagram of the finite automata that accepts the strings containing 101 as a substring. A DFA equivalent to this NFA will be: � 0 1 {A} {A} {A, B} {A, B} {A, C} {A, B} {A, C} {A} {A, B, D} {A, B, D}* {A, C, D} {A, B, D} {A, C, D}* {A, D} {A, B, D} {A, C, D}* {A, D} {A, B, D} Let us identify the states of this DFA using the names given below: {A} q0 {A, B} q1 {A, C} q2 {A, B, D} q3 {A, C, D} q4 {A, D} q5 The transition diagram of this automata is shown in Figure 6. The complement of the automata in Figure 6 is shown in Figure 7. After minimization, we get the DFA shown in Figure 8, because states q3, q4, and q5 are nondistinguishable states. Hence, they get combined, and this combination becomes a dead state and, can be eliminated. EXAMPLE 6 Construct a finite automata that will accept those strings of decimal digits that are divisible by three (see Figure 9). EXAMPLE 7 Construct a finite automata that accepts all possible strings of zeros and ones that do not contain 011 as a substring. Figure 10 shows a transition diagram of the automata that accepts the strings containing 101 as a substring. A DFA equivalent to this NFA will be: � 0 1 {A} {A, B} {A} {A, B} {A, B} {A, C} {A, C} {A, B} {A, D} {A, D}* {A, B, D} {A, D} {A, B, D}* {A, B, D} {A, C, D} {A, C, D}* {A, B, D} {A, D} Let us identify the states of this DFA using the names given below: {A} q0 {A, B} q1 {A, C} q2 {A, D} q3 {A, B, D} q4 {A, C, D} q5 The transition diagram of this automata is shown in Figure 11. The complement of automata shown in Figure 11 is illustrated in Figure 12. After minimization, we get the DFA shown in Figure 13, because the states q3, q4, and q5 are nondistinguishable states. Hence, they get combined, and this combination becomes a dead state that can be eliminated. EXAMPLE 8 Construct a finite automata that will accept those strings of a binary number that are divisible by three. The transition diagram of this automata is shown in Figure 14. var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>");
 Other

 Top 10
 REVIEW
- First look: Apple Watch

- 3 Tips for Maintaining Your Cell Phone Battery (part 1)

- 3 Tips for Maintaining Your Cell Phone Battery (part 2)