dixita.kagathara@darshan.ac.in

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

1

Topics to be covered

• Regular expressions & Regular languages
• Finite Automata
• Union, Intersection and Complement of Regular Languages
• Non-Deterministic Finite Automata
• Conversion from NFA to FA
• ^ - Non-Deterministic Finite Automata
• Conversion of NFA-^ to FA
• Kleene’s Theorem Part – I
• Finite Automata with Output (Moore machine, Mealy machine)
• Minimization of FA
• Moore machine & Mealy machine
• Pumping Lemma – Regular and Non Regular Languages

​

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

2

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

2

Regular Expression

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

3

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

3

Regular expression

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

4

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

4

Regular expression

L = Zero or More Occurrences of a =

​

*

a*

a

aaa

aa

aaaa

aaaaa…..

Infinite …..

𝜖

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

5

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

5

Regular expression

L = One or More Occurrences of a =

​

+

a⁺

a

aaa

aa

aaaa

aaaaa…..

Infinite …..

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

6

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

6

Precedence and associativity of operators

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

7

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

7

Regular expression examples

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

8

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

8

Regular expression examples

7. 0 or more occurrence of either a or b or both

​

• 1 or more occurrence of either a or b or both

​

• Binary no. ends with 0

​

• Binary no. ends with 1

​

• Binary no. starts and ends with 1

​

• String starts and ends with same character

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

9

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

9

Regular expression examples

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

10

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

10

Regular expression examples

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

11

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

11

Regular expression examples

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

12

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

12

Regular expression examples

31. All string begins or ends with 00 or 11

​

• Language of all string containing both 11 and 00 as substring

​

​

• String ending with 1 and not contain 00

​

• Language of C identifier

​

​

​

​

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

13

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

13

Finite Automata

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

14

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

14

Finite Automata

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

15

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

15

Example: Finite Automata

1

0

1

0

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

16

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

16

Applications of FA

• Lexical analysis phase of a compiler.
• Design of digital circuit.
• String matching.
• Communication Protocol for information exchange.

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

17

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

17

FA Examples

• The string with next to last symbol as 0.

0

1

0

1

0

1

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

18

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

18

FA Examples

• The strings ending with 10.

1

0

1

0

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

19

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

19

FA Examples

• The string with number of 0’s and number of 1’s are odd

odd 0�even 1

even 1�even 0

odd 1�even 0

odd 0�odd 1

0

0

0

0

1

1

1

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

20

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

20

FA Examples

• The string ending in 10 or 11

A

B

C

D

1

1

0

1

0

0

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

21

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

21

FA Examples

• The string corresponding to Regular expression {00}*{11}*

B

C

A

E

1

0

D

1

1

1

0

0

0

0,1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

22

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

22

FA Examples

• (a+b)*baaa

A

C

E

B

a

D

a

a

a

a

b

b

b

b

b

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

23

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

23

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

24

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

24

c

b

a

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

25

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

25

Y

X

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

26

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

26

Acceptance by FA

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

27

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

27

Union, Intersection & Complement of Languages

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

28

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

28

Example

0

1

1

0,1

0

0

1

1

0

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

29

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

29

0

1

BQ

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

30

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

30

0

1

0

1

0

1

0

1

BQ

CQ

AR

CR

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

31

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

31

0

1

0

1

0

1

0

1

0

1

0

1

BQ

CQ

AR

CR

CP

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

32

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

32

Removing Unconnected States

0

1

0

1

0

1

0

1

0

1

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

33

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

33

0

1

0

1

0

1

0

1

0

1

0

1

As per theorem stated earlier, the states which consists A or B or R will be Accepting states in the resultant FA.

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

34

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

34

0

1

0

1

0

1

0

1

0

1

0

1

Therefore, as per theorem stated earlier, the states which consists (A and R) and (B and R) will be Accepting states in the resultant FA.

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

35

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

35

0

1

0

1

0

1

0

1

0

1

0

1

Therefore, as per theorem stated earlier, the states which consists A or B but should not contain R with them will be Accepting states in the resultant FA.

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

36

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

36

Exercise

1

0

0

0,1

1

1

0

0

1

1

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

37

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

37

Nondeterministic Finite Automata (NFA)

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

38

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

38

1

0

1

1

1

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

39

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

39

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

40

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

40

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

41

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

41

Acceptance by NFA

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

42

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

42

1

0, 1

0, 1

0, 1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

43

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

43

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

44

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

44

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

45

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

45

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

46

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

46

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

47

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

47

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

48

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

48

NFA to FA using subset construction method

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

49

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

49

Example 1: Conversion from NFA to FA

1

3

4

2

b

a

a

b

b

a

NFA

Transition Table

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

50

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

50

Example 1: Conversion from NFA to FA

1

3,4

b

2,3

4

b

a

a

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

51

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

51

Example 1: Conversion from NFA to FA

1

3

3,4

b

2,3

4

b

b

b

a

a

a

a

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

52

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

52

Example 2: Conversion from NFA to FA

1

0, 1

0, 1

0, 1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

53

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

53

Example 2: Conversion from NFA to FA

0

1

0

1

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

54

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

54

Example 2: Conversion from NFA to FA

0

1

0

1

0

1

0

1

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

55

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

55

Example 2: Conversion from NFA to FA

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

56

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

56

Example 2: Conversion from NFA to FA

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

• As now no new states are obtained, the process stops and we need to define the accepting states.
• To define accepting states, the states which contain the accepting states of NFA will be accepting states of final FA.

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

57

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

57

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

58

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

58

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

59

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

59

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

60

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

60

^

^

^

^

^

0

0

0

0

0

1

1

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

61

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

61

^

^

^

^

^

0

0

0

0

0

1

1

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

62

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

62

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

63

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

63

^

^

^

^

^

0

0

0

0

0

1

1

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

64

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

64

^

^

^

^

^

0

0

0

0

0

1

1

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

65

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

65

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

66

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

66

NFA-^ to FA

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

67

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

67

NFA

FA

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

68

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

68

A

B

D

C

^

0

^

0

0

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

69

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

69

Conversion from NFA- ^ to FA

Step 1: To convert NFA - ^ to NFA

A

D

0

B

C

0

0

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

70

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

70

A

D

0

B

C

0

0

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

71

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

71

Conversion from NFA- ^ to FA

A

D

0

B

C

0

0

0

0

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

72

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

72

Conversion from NFA- ^ to FA

A

D

0

B

C

0

0

0

0

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

73

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

73

Conversion from NFA- ^ to FA

A

D

0

B

C

0

0

0

0

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

74

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

74

A

D

0

B

C

0

0

0

0

0

1

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

75

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

75

Conversion from NFA- ^ to FA

A

D

0

B

C

0

0

0

0

0

1

1

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

76

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

76

Conversion from NFA- ^ to FA

A

D

0

B

C

0

0

0

0

0

1

1

0

Resulting NFA

Accepting State

=

{

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

77

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

77

Conversion from NFA- ^ to FA

Step 2: To convert NFA to FA

A

CD

ABCD

0

BD

0

1

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

78

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

78

Conversion from NFA- ^ to FA

A

CD

0

D

ABCD

0

0

0

0

1

BD

1

FA

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

79

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

79

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

80

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

80

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

81

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

81

Kleene’s Theorem Part-1

Ø

{^}

a

{a}

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

82

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

82

Kleene’s Theorem Part-1

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

83

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

83

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

84

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

84

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

85

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

85

Kleene’s Theorem Part-1

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

86

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

86

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

87

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

87

Kleene’s Theorem Part-1

^

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

88

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

88

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

89

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

89

Kleene’s Theorem Part-1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

90

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

90

Application of Kleene’s Theorem

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

91

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

91

Regular expression to NFA-^

a

a

^

b

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

92

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

92

Regular expression to NFA-^

a

a

^

b

^

^

^

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

93

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

93

Regular expression to NFA-^

0

0

^

1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

94

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

94

Regular expression to NFA-^

0

0

^

1

^

^

0

0

^

1

^

^

^

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

95

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

95

Regular expression to NFA-^

1

0

^

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

96

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

96

Regular expression to NFA-^

1

0

^

^

^

^

0

0

^

1

^

^

^

^

^

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

97

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

97

Exercise (RE to NFA-^)

1. 00
2. 00+1
3. (00+1)*
4. (0+1)*
5. (111)*
6. (10+01)*
7. (0+1)*(11+00)*11
8. (10+110)*(0+1)*1
9. (00+1)*(10)*
10. (a+b)(a+b)*
11. (aab)*b*(a+b)*

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

98

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

98

Finite Automata with Output

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

99

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

99

Finite automata with output

• Finite automata has limited capability of either accepting a string or rejecting a string. Acceptance of string was based on the reachability of a machine from starting state to final state.
• Finite automata with output do not have a final state.
• Machine generates output on every input.
• There are two types of automata with outputs:
• Moore machine
• Mealy machine

​

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

100

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

100

Moore machine & Mealy Machine

FA with Output

Mealy Machine

Moore Machine

X,1

Y,0

b

b

X

Y

b|0

b|0

a

a

a|1

a|1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

101

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

101

Moore Machine

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

102

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

102

Example: Moore Machine

• Design a moore machine for the 1’s compliment of binary number.

A,0

B,1

0

1

1

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

103

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

103

Example: Moore Machine

• Design a moore machine to count occurrence of “ab” as substring.

a

b

a

b

b

a

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

104

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

104

Example: Moore Machine

• Construct a moore machine that takes set of all strings over {0, 1} and produces ‘A’ if i/p ends witg ‘10’ , produces ‘B’ if i/p ends with ’11’ otherwise produces ‘C’.

1

0

0

1

1

0

1

0

10🡪A

11🡪B

Otherwise 🡪C

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

105

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

105

Example: Moore Machine

• Construct a moore machine that takes binary number as an i/p and produces residue modulo ‘3’ as an output.

Input={0,1}

∆={0, 1, 2}

​

​

A,0

B,1

1

1

0

1

C,2

0

0

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

106

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

106

Mealy Machine

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

107

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

107

Example: Mealy Machine

• Design a mealy machine for the 1’s compliment of binary number

A

1/0

0/1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

108

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

108

Example: Mealy Machine

• Design a mealy machine for regular expression (0+1)*(00+11).

q1

q2

q3

1|x

0|x

1|x

0|x

0|y

1|y

00🡪y

11🡪y

Otherwise 🡪x

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

109

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

109

Moore to Mealy Machine Conversion

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

110

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

110

Conversion of Moore into Mealy Machine

Start

a/1

a/1

a/0

b/0

b/1

b/0

Start

a

a

a,b

a

b

b

b

0

0

1

1

Moore machine

Mealy machine

a/1,b/1

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

111

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

111

Mealy to Moore Machine Conversion

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

112

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

112

Conversion of Mealy to Moore machine

0|0

1|1

0|1

1|0

0

1

0

1

1

0

Mealy machine

Moore machine

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

113

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

113

Exercise: Mealy machine to Moore machine

q1

q2

q3

1|x

0|x

1|x

0|x

0|y

1|y

b|0

a|0

a|1

b|1

GTU- May 2016, 7 Marks

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

114

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

114

Minimization of FA

Unit – 2 : Regular languages & FA

Darshan Institute of Engineering & Technology

115

Theory of Computation (2160704)

Darshan Institute of Engineering & Technology

115

Example: Minimize FA

Final state is {6}

And, Non-Final state is {1,2,3,4,5,7}

(6, 1), (6,2), (6, 3), (6, 4), (6, 5), (6, 7) are distinguish pairs.

Consider pair (1,2)

δ(1,a)=2 δ(1,b)=3

δ(2,a)=4 δ(2,b)=5

Consider pair (1,3)

δ(1,a)=2 δ(1,b)=3

δ(3,a)=6 δ(3,b)=7

pair (2,6) is distinguish, so (1,3) is distinguished pair.

Consider pair (1,4)

δ(1,a)=2 δ(1,b)=3

δ(4,a)=4 δ(4,b)=5