Formal Languages Automata Thery.pdf

ntg

1. FORMAL LANGUAGES AND AUTOMATA THEORY Page 1



DIGITAL NOTES
ON
FORMAL LANGUAGES AND AUTOMATA
THEORY



B.TECH II YEAR - II SEM
(2017-18)






DEPARTMENT OF INFORMATION TECHNOLOGY


MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, INDIA.

2. FORMAL LANGUAGES AND AUTOMATA THEORY Page 2






MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY

DEPARTMENT OF INFORMATION TECHNOLOGY

II Year B.Tech IT – II Sem L T /P/D C
4 -/-/- 3
(R15A0506)FORMAL LANGUAGES AND AUTOMATA THEORY

Objectives:
 To teach the student to identify different formal language classes and their
relationships
 To teach the student the theoretical foundation for designing compilers.
 To teach the student to use the ability of applying logical skills.
 Teach the student to prove or disprove theorems in automata theory using its
properties
 To teach the student the techniques for information processing.
 Understand the theory behind engineering applications.

UNIT I:
Fundamentals: Strings, Alphabet, Language, Operations, Finite state machine, definitions,
finite automaton model, acceptance of strings, and languages, FA, transition diagrams and
Language recognizers.

Finite Automata: Deterministic finite automaton, Non deterministic finite automaton and
NFA with Є transitions - Significance, acceptance of languages. Conversions and
Equivalence : Equivalence between NFA with and without Є transitions, NFA to DFA
conversion, minimization of FSM, equivalence between two FSMs, Finite Automata with
output- Moore and Melay machines.
UNIT II:
Regular Languages: Regular sets, regular expressions, identity rules, Conversion finite
Automata for a given regular expressions, Conversion of Finite Automata to Regular
expressions. Pumping lemma of regular sets, closure properties of regular sets (proofs not
required).


UNIT III:
Grammar Formalism: Regular grammars-right linear and left linear grammars, equivalence
between regular linear grammar and FA, inter conversion, Context free grammar, derivation
trees, sentential forms. Right most and leftmost derivation of strings.

Context Free Grammars: Ambiguity in context free grammars. Minimisation of Context
Free Grammars. Chomsky normal form, Greibach normal form, Pumping Lemma for Context
Free Languages. Enumeration of properties of CFL (proofs omitted).
UNIT IV:

3. FORMAL LANGUAGES AND AUTOMATA THEORY Page 3


Push Down Automata: Push down automata, definition, model, acceptance of CFL,
Acceptance by final state and acceptance by empty state and its equivalence. Equivalence of
CFL and PDA, interconversion. (Proofs not required). Introduction to DCFL and DPDA.
LINEAR BOUNDED AUTOMATA(LBA):LBA,context sensitive grammars ,CS languages




UNIT V:
Turing Machine: Turing Machine, definition, model, design of TM, Computable functions,
recursively enumerable languages. Church’s hypothesis, counter machine, types of Turing
machines (proofs not required).

Computability Theory: Chomsky hierarchy of languages, linear bounded automata and
context sensitive language, LR(0) grammar, decidability of, problems, Universal Turing
Machine, undecidability of posts. Correspondence problem, Turing reducibility, Definition of
P and NP problems, NP complete and NP hard problems.

TEXT BOOKS:
1. “Introduction to Automata Theory Languages and Computation”. Hopcroft H.E. and
Ullman J. D. Pearson Education.
2. Introduction to Theory of Computation - Sipser 2nd edition Thomson

REFERENCE BOOKS:
1. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
2. Introduction to languages and the Theory of Computation ,John C Martin, TMH
3. “Elements of Theory of Computation”, Lewis H.P. & Papadimition C.H. Pearson /PHI.
4. Theory of Computer Science and Automata languages and computation -Mishra and
Chandrashekaran, 2nd edition, PHI.
5. Theory of Computation, By K.V.N. Sunitha and N.Kalyani

Course Outcomes:
Student will have the ability to
 Apply knowledge in designing or enhancing compilers.
 Design grammars and automata (recognizers) for different language classes.
 Apply knowledge in developing tools for language processing or text processing.

4. FORMAL LANGUAGES AND AUTOMATA THEORY Page 4




MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY

DEPARTMENT OF INFORMATION TECHNOLOGY



INDEX

S. No

Unit
Topic Page no
1






I
Strings, Alphabet, Language, Operations 6-9
2 Finite state machine, 10-15
3 Finite Automata: DFA,NFA,With Є transitions 16-21
4 Conversions and Equivalence : 22-27
5
NFA to DFA conversion, minimization of FSM,
equivalence between two FSMs
28-32
6 Finite Automata with output 46-52
7
II





Regular Languages: Conversion, Pumping lemma of
regular sets
53-58
8 Pumping lemma of regular sets 59-64
9 FA:RLG,LLG, Sentential forms 65-72
10


III

Context Free Grammars:CNF,GNF 73-93
11
Pumping Lemma for Context Free Languages.
Enumeration of properties of CFL
94-107
12

IV
Equivalence of CFL and PDA, inter conversion Push
Down Automata, LBA,CSL
108-112
13


V
Turing Machine: Church’s hypothesis, counter
machine, types of Turing machines
113-115
14
LR(0) grammar, decidability of, problems,UTM,P
and NP Problems
116-122

5. FORMAL LANGUAGES AND AUTOMATA THEORY Page 5


MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY

DEPARTMENT OF INFORMATION TECHNOLOGY
















































UNIT-1

6. FORMAL LANGUAGES AND AUTOMATA THEORY Page 6

7. FORMAL LANGUAGES AND AUTOMATA THEORY Page 7

8. FORMAL LANGUAGES AND AUTOMATA THEORY Page 8

9. FORMAL LANGUAGES AND AUTOMATA THEORY Page 9

10. FORMAL LANGUAGES AND AUTOMATA THEORY Page 10

11. FORMAL LANGUAGES AND AUTOMATA THEORY Page 11

12. FORMAL LANGUAGES AND AUTOMATA THEORY Page 12

13. FORMAL LANGUAGES AND AUTOMATA THEORY Page 13

14. FORMAL LANGUAGES AND AUTOMATA THEORY Page 14

15. FORMAL LANGUAGES AND AUTOMATA THEORY Page 15

16. FORMAL LANGUAGES AND AUTOMATA THEORY Page 16

17. FORMAL LANGUAGES AND AUTOMATA THEORY Page 17

18. FORMAL LANGUAGES AND AUTOMATA THEORY Page 18

19. FORMAL LANGUAGES AND AUTOMATA THEORY Page 19

20. FORMAL LANGUAGES AND AUTOMATA THEORY Page 20

21. FORMAL LANGUAGES AND AUTOMATA THEORY Page 21

22. FORMAL LANGUAGES AND AUTOMATA THEORY Page 22

23. FORMAL LANGUAGES AND AUTOMATA THEORY Page 23

24. FORMAL LANGUAGES AND AUTOMATA THEORY Page 24

25. FORMAL LANGUAGES AND AUTOMATA THEORY Page 25

26. FORMAL LANGUAGES AND AUTOMATA THEORY Page 26

27. FORMAL LANGUAGES AND AUTOMATA THEORY Page 27

28. FORMAL LANGUAGES AND AUTOMATA THEORY Page 28

Unit-II

29. FORMAL LANGUAGES AND AUTOMATA THEORY Page 29

30. FORMAL LANGUAGES AND AUTOMATA THEORY Page 30

31. FORMAL LANGUAGES AND AUTOMATA THEORY Page 31

32. FORMAL LANGUAGES AND AUTOMATA THEORY Page 32

33. FORMAL LANGUAGES AND AUTOMATA THEORY Page 33

34. FORMAL LANGUAGES AND AUTOMATA THEORY Page 34

35. FORMAL LANGUAGES AND AUTOMATA THEORY Page 35

36. FORMAL LANGUAGES AND AUTOMATA THEORY Page 36

37. FORMAL LANGUAGES AND AUTOMATA THEORY Page 37

38. FORMAL LANGUAGES AND AUTOMATA THEORY Page 38

39. FORMAL LANGUAGES AND AUTOMATA THEORY Page 39

40. FORMAL LANGUAGES AND AUTOMATA THEORY Page 40

41. FORMAL LANGUAGES AND AUTOMATA THEORY Page 41

42. FORMAL LANGUAGES AND AUTOMATA THEORY Page 42

UNIT-3

43. FORMAL LANGUAGES AND AUTOMATA THEORY Page 43

44. FORMAL LANGUAGES AND AUTOMATA THEORY Page 44

45. FORMAL LANGUAGES AND AUTOMATA THEORY Page 45

46. FORMAL LANGUAGES AND AUTOMATA THEORY Page 46

47. FORMAL LANGUAGES AND AUTOMATA THEORY Page 47

48. FORMAL LANGUAGES AND AUTOMATA THEORY Page 48




UNIT-3

49. FORMAL LANGUAGES AND AUTOMATA THEORY Page 49

50. FORMAL LANGUAGES AND AUTOMATA THEORY Page 50

51. FORMAL LANGUAGES AND AUTOMATA THEORY Page 51

52. FORMAL LANGUAGES AND AUTOMATA THEORY Page 52

53. FORMAL LANGUAGES AND AUTOMATA THEORY Page 53

54. FORMAL LANGUAGES AND AUTOMATA THEORY Page 54

55. FORMAL LANGUAGES AND AUTOMATA THEORY Page 55

56. FORMAL LANGUAGES AND AUTOMATA THEORY Page 56

57. FORMAL LANGUAGES AND AUTOMATA THEORY Page 57

58. FORMAL LANGUAGES AND AUTOMATA THEORY Page 58

59. FORMAL LANGUAGES AND AUTOMATA THEORY Page 59

60. FORMAL LANGUAGES AND AUTOMATA THEORY Page 60

61. FORMAL LANGUAGES AND AUTOMATA THEORY Page 61

62. FORMAL LANGUAGES AND AUTOMATA THEORY Page 62

63. FORMAL LANGUAGES AND AUTOMATA THEORY Page 63



UNIT-4

64. FORMAL LANGUAGES AND AUTOMATA THEORY Page 64

65. FORMAL LANGUAGES AND AUTOMATA THEORY Page 65

66. FORMAL LANGUAGES AND AUTOMATA THEORY Page 66

67. FORMAL LANGUAGES AND AUTOMATA THEORY Page 67

68. FORMAL LANGUAGES AND AUTOMATA THEORY Page 68

69. FORMAL LANGUAGES AND AUTOMATA THEORY Page 69

70. FORMAL LANGUAGES AND AUTOMATA THEORY Page 70

71. FORMAL LANGUAGES AND AUTOMATA THEORY Page 71

72. FORMAL LANGUAGES AND AUTOMATA THEORY Page 72

73. FORMAL LANGUAGES AND AUTOMATA THEORY Page 73

74. FORMAL LANGUAGES AND AUTOMATA THEORY Page 74

75. FORMAL LANGUAGES AND AUTOMATA THEORY Page 75

76. FORMAL LANGUAGES AND AUTOMATA THEORY Page 76



UNIT-5

77. FORMAL LANGUAGES AND AUTOMATA THEORY Page 77

78. FORMAL LANGUAGES AND AUTOMATA THEORY Page 78

79. FORMAL LANGUAGES AND AUTOMATA THEORY Page 79

80. FORMAL LANGUAGES AND AUTOMATA THEORY Page 80

81. FORMAL LANGUAGES AND AUTOMATA THEORY Page 81

82. FORMAL LANGUAGES AND AUTOMATA THEORY Page 82

83. FORMAL LANGUAGES AND AUTOMATA THEORY Page 83

84. FORMAL LANGUAGES AND AUTOMATA THEORY Page 84

85. FORMAL LANGUAGES AND AUTOMATA THEORY Page 85

86. FORMAL LANGUAGES AND AUTOMATA THEORY Page 86

87. FORMAL LANGUAGES AND AUTOMATA THEORY Page 87

88. FORMAL LANGUAGES AND AUTOMATA THEORY Page 88

89. FORMAL LANGUAGES AND AUTOMATA THEORY Page 89

90. FORMAL LANGUAGES AND AUTOMATA THEORY Page 90

91. FORMAL LANGUAGES AND AUTOMATA THEORY Page 91

92. FORMAL LANGUAGES AND AUTOMATA THEORY Page 92

93. FORMAL LANGUAGES AND AUTOMATA THEORY Page 93

94. FORMAL LANGUAGES AND AUTOMATA THEORY Page 94

95. FORMAL LANGUAGES AND AUTOMATA THEORY Page 95

96. FORMAL LANGUAGES AND AUTOMATA THEORY Page 96

97. FORMAL LANGUAGES AND AUTOMATA THEORY Page 97

98. FORMAL LANGUAGES AND AUTOMATA THEORY Page 98

99. FORMAL LANGUAGES AND AUTOMATA THEORY Page 99

100. FORMAL LANGUAGES AND AUTOMATA THEORY Page 100

101. FORMAL LANGUAGES AND AUTOMATA THEORY Page 101

102. FORMAL LANGUAGES AND AUTOMATA THEORY Page 102

103. FORMAL LANGUAGES AND AUTOMATA THEORY Page 103

104. FORMAL LANGUAGES AND AUTOMATA THEORY Page 104

105. FORMAL LANGUAGES AND AUTOMATA THEORY Page 105

106. FORMAL LANGUAGES AND AUTOMATA THEORY Page 106

107. FORMAL LANGUAGES AND AUTOMATA THEORY Page 107

108. FORMAL LANGUAGES AND AUTOMATA THEORY Page 108

109. FORMAL LANGUAGES AND AUTOMATA THEORY Page 109

110. FORMAL LANGUAGES AND AUTOMATA THEORY Page 110

111. FORMAL LANGUAGES AND AUTOMATA THEORY Page 111

112. FORMAL LANGUAGES AND AUTOMATA THEORY Page 112

113. FORMAL LANGUAGES AND AUTOMATA THEORY Page 113

114. FORMAL LANGUAGES AND AUTOMATA THEORY Page 114

115. FORMAL LANGUAGES AND AUTOMATA THEORY Page 115

116. FORMAL LANGUAGES AND AUTOMATA THEORY Page 116

117. FORMAL LANGUAGES AND AUTOMATA THEORY Page 117

118. FORMAL LANGUAGES AND AUTOMATA THEORY Page 118

119. FORMAL LANGUAGES AND AUTOMATA THEORY Page 119

120. FORMAL LANGUAGES AND AUTOMATA THEORY Page 120

121. FORMAL LANGUAGES AND AUTOMATA THEORY Page 121

122. FORMAL LANGUAGES AND AUTOMATA THEORY Page 122