Operations on Regular Languages — Transcript

Full transcript

1. 0:05hello everyone welcome to the next
2. 0:06lecture in theory of computation and in
3. 0:08this lecture we will be discussing about
4. 0:11some of the operations on regular
5. 0:13languages all right so let's get started
6. 0:16okay so here are the operations that we
7. 0:18are going to discuss Union concatenation
8. 0:20and star so let's start with Union so
9. 0:23the formal definition of union is given
10. 0:25here a union B is equal to X such that X
11. 0:28belongs to a or X belongs to B so this
12. 0:32Union operation is exactly the same like
13. 0:34you perform your union operation on sets
14. 0:37so suppose you have two language sets
15. 0:39namely A and B then the union of A and B
16. 0:42would actually mean anything X such that
17. 0:46X could either belong to the set a or it
18. 0:50could belong to the set B so it
19. 0:52basically means everything from A and B
20. 0:55okay that is Union and coming to the
21. 0:57next one that is
22. 0:58concatenation a concatenation b
23. 1:00concatenation is denoted by the small
24. 1:02circle and is equal it is equal to XY
25. 1:06such that X belongs to a and Y belongs
26. 1:09to B this basically means that joining
27. 1:12two symbols together when you join two
28. 1:16or more strings or symbols together that
29. 1:18is what we mean by concatenation so
30. 1:21suppose you
31. 1:22have X which is an element of a and Y
32. 1:26which is an element of B and you join
33. 1:28them together like this X y that is
34. 1:30known as
35. 1:32concatenation and uh the next one is
36. 1:35star so star operation unlike Union and
37. 1:38conation in Star operation we have only
38. 1:40one set so performing the star operation
39. 1:44on set a means X1 X2 X3 up to XK such
40. 1:49that K greater than or equal to zero and
41. 1:53each X of I belongs to a so don't worry
42. 1:57about this long definition it only means
43. 1:59that you you
44. 2:00take as many symbols that you want from
45. 2:04your set a and you just join them
46. 2:06together in any way you like that is
47. 2:09what you mean by star so all these three
48. 2:12will become more clear when we take an
49. 2:14example that we are going to do below
50. 2:16that will make it even clearer all right
51. 2:19so let's take an example so here I'm
52. 2:22taking an example where I have two sets
53. 2:25A and B where a is equal to a set where
54. 2:29I have the
55. 2:32elements PQ and
56. 2:35R and then I have another set called B
57. 2:39which also has two elements T and
58. 2:44UV so we have these two sets and let's
59. 2:47perform Union concatenation and star on
60. 2:48these two sets so first of all let's
61. 2:51perform Union a union B what would this
62. 2:57be so a un b as we saw in the definition
63. 3:01X such that X belongs to a or X belongs
64. 3:03to B so basically it means everything
65. 3:05from A and B just put all these elements
66. 3:08together from A and B so from a we have
67. 3:13PQ and R and from B you have t and UV T
68. 3:19and UV so this is the union operation
69. 3:23everything from set a and set B put
70. 3:25together that is the union operation and
71. 3:28coming to the next one we have the
72. 3:30concatenation concatenation of A and B
73. 3:33so what is the concatenation of A and B
74. 3:36so as I told you concatenation means
75. 3:38joining two or more symbols or strings
76. 3:41together so here in a we have PQ and R
77. 3:44and in B we have t and UV so I should
78. 3:47join XY such that X belongs to a and Y
79. 3:50belongs to B that means one element from
80. 3:52a and another element from B should be
81. 3:54joined so how can I perform the joining
82. 3:56I could join PQ and T
83. 4:00PQ and T I have joined them together
84. 4:03that means I have concatenated it then
85. 4:06in the same way I can join PQ and
86. 4:09UV PQ UV and in the same way I can join
87. 4:13R and T R and T and then I can also join
88. 4:18R and UV R and UV so here we have
89. 4:23performed the concatenation of A and B
90. 4:25where the first element is from a second
91. 4:27is from B and we have joined them
92. 4:29together so that is a
93. 4:31concatenation and coming to
94. 4:33the last one which is star operation a
95. 4:38star so what is a star so as I told you
96. 4:41in Star operation there is only one set
97. 4:43involved so a star means I can take as
98. 4:47many symbols from that set and I can
99. 4:50join them together in any way I like so
100. 4:53I'm dealing with a a star so in a star
101. 4:57what are the elements that I can have so
102. 5:00I would first write Epsilon Epsilon as I
103. 5:03already told you in the first lecture it
104. 5:04means the empty string so empty string
105. 5:06also is a part of a star all right and
106. 5:09the second one would be PQ just by
107. 5:11itself I can write it and R just by
108. 5:16itself all right now let me join PQ andr
109. 5:19I can join PQ andr right I can also put
110. 5:23R first and then PQ R and then
111. 5:28PQ or I could put I could join PQ with
112. 5:31itself PQ PQ or I could join r with
113. 5:35itself like this r r or I could join PQ
114. 5:38three times PQ PQ
115. 5:41and PQ or I could even oh sorry there
116. 5:45should be no comma over here this is PQ
117. 5:50PQ
118. 5:52and
119. 5:53PQ means I'm joining it together and I
120. 5:56can also join R three times r r r and it
121. 6:00goes on this actually will be an
122. 6:01infinite set it could have infinite
123. 6:03number of elements so that is how we
124. 6:05perform Union concatenation and star all
125. 6:08right so I hope this was clear now there
126. 6:11are two important theorems that you need
127. 6:13to
128. 6:14remember which I will be discussing now
129. 6:17all right so here are the two theorems
130. 6:19the first theorem says that the class of
131. 6:21regular languages is closed under Union
132. 6:24so what does this mean this means that
133. 6:27if you have two regular languages let's
134. 6:29say suppose A and B are two regular
135. 6:31languages and if you perform the union
136. 6:33of A and B you perform the union of A
137. 6:36and B which are regular languages then
138. 6:38the union of A and B is also a regular
139. 6:41language that means the union of two
140. 6:43regular languages is also a regular
141. 6:45language that is what it means and then
142. 6:47the second theorem says that the class
143. 6:49of regular languages is closed under
144. 6:51concatenation in the same way if you
145. 6:53have two languages A and B which are
146. 6:56regular and if you perform the
147. 6:58concatenation of them then then the
148. 6:59concatenation of those two languages
149. 7:01will also be regular the concatenation
150. 7:03of two regular languages will also be a
151. 7:06regular language so that is the meaning
152. 7:09of these two theorems so I'll not be
153. 7:12doing the proof of these two theorems
154. 7:14and if you won the proof you can leave a
155. 7:17comment in the comment section below so
156. 7:18I will be discussing it in a later
157. 7:20lecture so I hope this we clear to you
158. 7:25about the operations that we perform on
159. 7:27regular languages which are Union SK
160. 7:29nation and star so thank you for
161. 7:31watching and see you in the next
162. 7:37[Music]
163. 7:43video