1
00:00:24,800 --> 00:00:26,150

okay folks  um  here we are again  welcome back  for another episode of theory of  computation this is lecture number three  um  i  am fir i'm going to review how what  we've been doing um we've been looking  at finite automata  and regular languages those are the  languages that the fine automata can  recognize  and we  talked about  non-determinism so we had  non-deterministic finite automata and  deterministic finite automata we showed  that they're equivalent  we looked at the closure properties over  the regular operations union  concatenation and star and showed that  the  regular language is really the class of  regular languages is closed under those  regular operations  and we used the constructions that we  developed in the proof of those closure  properties to show that the  we can give away to convert  regular expressions to finite automata  so that is uh was  a  part way toward our goal  of showing that these regular  expressions and finite automata are  equivalent with respect to the class of  languages they describe namely the  regular languages so regular expressions  of finite autonomic are interchangeable  from the perspective of what kinds of  languages you can do with them  so we're going to finish that off today  so let's take a look at what  our next  topics we're going to be covering  we're going to  reverse  the  construction that we gave last time  which allowed us to convert regular  expressions to finite automata now we're  going to go backwards we're going to  show how to convert finite automata back  to regular expressions  and um that  those two  constructions together uh show us that  the regular expressions finite automata  can be inter interconverted from one  another and they're therefore equivalent  with respect to the kinds of things they  they can do in language  recognition or generation  then we're going to prove that uh we're  going to look at how you prove certain  languages are not regular they're beyond  the capabilities of fine art automata  and finally at the end we're going to  introduce a new model of computation  which is more powerful  than the finite automata and regular  expressions namely the context-free  grammars  those can do  other kinds of languages that the  simpler find at a time but the regular  expressions models can't do um  and i i would also just like to note  that  a lot of what we're doing is a warm up  toward the more powerful models of  computation that we're going to be  looking at later um well in a week or so  which are  more kind of general purpose  computation  but along the way introducing these  models of finite automata in  context-free languages  is  interesting and helpful because many of  those um a number of those models turn  out to be useful in a number of  applications um whether it's from  you know pro linguistics to  uh programming languages um and a  variety of different uh  parts of computer science and other  fields as well use those notions so  they're they're useful notions um  and beyond just uh  in this course um  okay so  um  i just wanted  a couple of administrative things to  touch on uh we are going to have  additional check-ins today um as i  uh mentioned to you we're gonna start  counting participation not correctness  of just participation in the live  check-ins  so um with that let us  move on to today's material um  as i mentioned we're going to be showing  how to convert  finite automata to regular expressions  um and that's going to complete our  equivalence of finite automata and  regular expressions so just to recap  what we did last time  we showed that if you have a regular  expression  um  uh  and it describes some language then that  language is regular  uh so in other words um we have a way of  we gave a way of converting regular  expressions to finite automata as kind  of shown in this diagram  that's what we did last time  now we're going to go the other way um  we're going to show how to convert oh  and just a reminder in case you're just  getting yourself  your memory size your memory uh to work  um maybe it'll help you just to remember  that we actually did an example of that  conversion we looked at this um regular  expression a union a b star and we  actually worked through the process of  converting that oops i need to make  myself smaller so you can see all that  we went through the process of um  converting a union a b star as an  example of that um  of uh  minimus  okay  uh  well  um  we went through the process of actually  doing that conversion and now we're  going to show how to do it the other way  around  all right so  um  so we're going to invert that  and go backwards the other way  um so today's theorem is to show that if  a is regular namely its  uh um  the language of some finite automaton  um then um  uh  you can convert it to a regular  expression which will describe that same  language so basically we're going to  give a conversion from finite automata  to regular expressions okay um  but before we do that we're going to  have to introduce a new concept um so  we're not going to be able to dive right  into that conversion we're going to have  to do introduce a new model first which  is going to facilitate that conversion  and that new model is called it's in yet  another kind of finite automaton called  a generalized  non-deterministic finite automaton or a  generalized nfa or just simply a gnfa  okay so this is yet another variant of  the finite automaton model um  and  conceptually it's very sim simple it's  similar to the nfas i'll give you here's  a picture of a  gnfa  named  g1 very similar to the nfas but if you  look at it for a second you'll see that  the  transitions have more complicated labels  for the anaphase who are only allowing  just single symbols or the empty string  to appear on the labels now i'm actually  allowing you to put full regular  expressions on the labels  for the automaton  now we have to understand how  a gnfa process as  its input and the way it works is  um not complicated to understand  um  when you're getting an input string  feeding when the when a gnfa is  processing an input string it starts at  the start state just like you would  imagine  but now to go along a transition instead  of reading just a single symbol or the  empty string as a as in the case for the  nondeterministic machine  um  it actually gets to read a whole string  at one step kind of at one byte  it can read an entire string um and go  along that transition um  uh  arrow provided that  trunk of the input that it read  is in the regular expression  that that  uh  transition uh  has as its label  so for example  um  this you can go from q1 to q2 in one  step in this gnfa by reading the by  reading aabb off the input  so it reads all those four symbols all  at once  it just swoops them up and then moves  from q1 to q2  in one step  okay and then when it's in q2  it can read aab  and move to q3 and q3 happens there's  nowhere to go um so this is going to be  a non-deterministic machine there might  be several different ways of processing  the input and if any one of them gets to  an accepting state at the end of the  input  we say the gnfa accepts  so it's similar to non-deterministic to  nfa's in in the way the acceptance  criterion works  um so you know you could do an example  but hopefully the concept of how this  works is reasonably  you know you can at least buy it um that  it processes  um the input in  chunks at a time and those chunks have  to be described by the  uh regular expressions on the transition  our arrows as it moves along those  transitions  okay  so um  what we're going to do  now  is to convert  not  dfas to regular expressions we're going  to convert gnfas to regular expression  that's even harder  because gnfas are allow you to do all  sorts of other things besides just  ordinary dfas  so that's a harder job why am i making  my life harder well you'll see in a  minute  that it's going to actually turn out to  be helpful to be working with a more  powerful model um  in the way this construction is going to  work  okay  now before i dive in and do the  construction from gnfas to regular  expressions i'm going to make a  simplifying assumption about the g  anaphase  i'm going to put them in a special form  that's going to make it easier to do the  conversion  and that simpler form is  first of all i'm going to assume that  gnfa has just a single accepting state  and that accepting state is not allowed  to be the start state  okay so it has to have just a single  accepting state i've already violated  that um convenient assumption in this  gnfa because i have here two  uh accepting states that's not what i  want i want to have just one  well the thing is it's easy to obtain  just one just to modify the machine so  that i have just one by  adding a new accepting state which is  branch two from the former accepting  states by empty transition so i can  always jump from q2 to q4 at any time  without even reading any input just  going along this empty transition  and then i declassify the former  accepting states as accepting  and now i have here just a single  accepting state and  because it's going to be a new state  that i added it won't be the start state  and i have  accomplished that one aspect of my  assumption about the form of the gnfa  but there's another thing that i want to  do too  i want to assume  um as you'll see which is going to be  convenient in my uh  construction that we will have  transition arrows going from every state  to every other state in fact i want  transition i was going from every state  even back to themselves  um  i want the there to be all of all  possible transition arrows should be  present  um  uh with with two exceptions  uh for for the start state there should  be only transition arrows exiting the  start state  and for the accepting state there's just  one now there should be only transition  arrows coming in to the start state  so it's kind of what you would imagine  as being reasonable um for the other  states which are not accepting or or um  starting  there should be  transition arrows leaving and coming  from everywhere else but for the start  states just leaving and from the except  state just coming in  and you could easily modify the machine  to achieve that um let's just see how to  do that in one example so from notice  that from q3 to q2 there is no  transition right now and that's not good  that's not what i want i want that to be  a transition from q3 to q2 well i'll  just add that transition in  but i'm going to label it with the empty  language regular expression  so that means yeah the transition is  there but you never can take it  so it doesn't change  the  language that the machine is going to be  recognizing but it fulfills my um  uh  my assumption my convenient assumption  that we have all of these transition  arrows being present in the machine  okay so uh  anyway i hope you uh will buy it it's  not gonna be re if you don't quite get  this don't worry it's not totally  critical that you're following or these  little these little adjustments and  modifications to the gnf8 but it will be  helpful to understand what gnf  themselves how they work  so as i mentioned we can easily modify  gnfa to have the special form that we're  assuming here  all right so now we're going to jump in  and start doing the conversion so we're  going to have a lemma which is like a a  theorem that really is just a local  interest here it's not a  general interest theorem it's going to  be relevant just to gnfa which it really  just defined to help us do this  conversion they really don't have any  other independent value  so every you want to show that every g n  of a has an equivalent regular  expression r  that's really my goal um  and the way we're going to prove that  is by induction  it's going to be by induction on the  number of states of the gnfa  now  you really should be familiar with  induction as one of the uh expectations  for being in this course but in case  you're a little shaky on it don't worry  i'm gonna unpack it um as a procedure  it's really just recursion you know  induction is just a and a proof that  uses induction is really just a proof  that calls itself it's just a proof that  it's a recursive proof that's all it is  so if you're comfortable with the  recursion you'll be comfortable with  induction um but anyway i'm going to  describe this as a procedure so if  you're a little shaky on induction don't  worry  um  so the basis is so first i'm going to  handle the case where the gnfa has just  two states  okay um  now remember i'm assuming now my gnfas  are in the special form  so you can't even have a gnfa with one  state because it has to have a start  state and it has to have an accept state  and they have to not be the same so the  smallest possible gnfa to worry about is  a two-state gnfa  okay now if we have a if we happen to  have a two-state gnfa it turns out to be  very easy to find the equivalent regular  expression why  because  that tuesday gnfa can only look like  this  it can have a start state can have an  accept state  and it can only have a transition going  from the start to the accept because no  other transitions are  allowed um it only has outgoing from the  start only incoming from the uh  to the except and so there's only one  transition and it has a label with a  regular expression r  so what do you think the equivalent  regular expression is for this g nfa  it's just simply the one that's labeling  that transition because that tells us  when i can go from the start to the  accept and there's nothing else the  machine can do it just makes one step  which is to accept its input if it's  described by that regular expression so  therefore the equivalent regular  expression that we're looking for is  simply label on that single transition  okay so two state g nfas are easy  um but what if what happens if you have  more states then you're gonna actually  have to do some work  um  so  we call that the induction step that's  when we have more than two states  and what that the way the induction  works is we're going to assume we  already know how to do it for k minus 1  states  and we're going to use that knowledge to  show how to do it for k-states  so in other words um we already know how  to do it for two states  i'm going to use that fact to show how  to do it for three states  and then use the fact that i can do it  for three states to show how to do it  for four states and so on and so on  all right  and the idea for how to do that is  actually uh  pretty  uh easy to to grasp  um what we're going to do is if we have  a k-state gnfa that we want to convert  we're going to con we're going to change  that k state g n of a to a k minus 1  state g n of a  and then use our assumption that we  already know how to do the k minus 1  state g nfa  all right  so um  in terms of a picture i'm going to take  a k-state to prove that i can always  convert k-state g-n-phase uh to regular  expressions  i'm going to show how to convert the  k-state um one into an equivalent k  minus one state g of a and then if you  just like to think of it this  procedurally the k minus one will gets  converted to a k minus two gets  converted to a k minus three and so on  and so on until i get down to two  which then i know how to do directly  okay so the whole name of the game here  is figuring out how to convert a  gnfa that has k states  into another one that has one fewer  state that does the same language  okay so you have to  hold that in your head i mean i wish i  had more blackboard space here but you  know it's very limited here so you have  to remember what would what we're going  to be doing on the next slide  because that's going to finish the job  for us as long as i can show in general  how to convert a k-state gnfa to a gnfa  that is one fewer state but it still  does the same language  i'm good  because then i can keep iterating that  till i get down to two  all right  so here is um  this is the  the guts of the argument um so i have my  k-state machine here's my my start state  here's my accept state  um here's my k minus one state that  machine that i'm going to be uh building  for you it's actually going to be  be look almost exactly the same i'm just  going to remove one state  um  from the from the from the bigger  machine  so i'm going to pick any state which is  not the  start state or the accept state um here  it is pictured here  i mean all of the states of the k-state  machine are going to appear in the k-1  state machine  except for one state that i'm going to  rip out  okay  that's the state x it's now here as a  ghost  it's been removed  um  uh it's not there anymore okay but i'm  just helping you to remember that used  to be there  by showing his shadow  but it's a  uh i have taken  my original machine that had k-states  um  and basically just ripped out of state  um and now i've  you know one fewer state  so the good news  is that i now have a machine with k  minus one states  that's what i want  but the bad news is that it doesn't do  the same language anymore  it's i i broke the machine by rip just  if you're just going to rip out a state  you know who knows what the machine is  going to do it's going to be  probably not the same as what the  original machine did  so what i need to do  then  is repair the damage  i've got to fix the damage that i caused  by removing  x okay um  and  whatever  role  x was playing  in the original machine  i've got to make sure  that  the the new machine that i have which  doesn't have x anymore can still do the  same things  um that the original machine did  um and so the way i'm going to do that  is look at all of the paths that could  go through x and make sure that they're  still present even though i don't have x  anymore  and the way i'm going to do that is i'm  going to take  um  [Music]  consider  a part of a path that might use x  so it starts  let's pick two states q i and two j  in the uh machine that had k states  let me just here  i know this is uh  okay um  we have if we have uh we'll pick two  states q i and q j  um in in in the original machine now qi  might  have the possibility of going to state x  and then x might have a self loop  and then it might go to 2j  the new machine doesn't have any x  anymore  the way i'm going to fix that  is by  replacing the label that goes directly  from i to j  with a new label  that  adds in all of the things i lost  when i removed x  okay that's  that's the whole idea here so here is q  i to q j but there's no x anymore  how could i get  from q i to q j  um  um you know  you know what what were the  inputs  that could have brought us from qi to qj  via x  well they would have been an input  that read a string described by r1  i might have self-looped at x a few  times  so i might have read several strings  that are described by r2  and then i would have read a string that  was described by r3 and now i'm at qj  okay  so  uh the new label  that i'm going to place over here is  going to be  uh the strings that i get from reading  are one you know reading a a  a  a string that described by r1  then multiple copies of a stretch you  know  multiple strings that are possibly  describing r2 which is the same as r2  star  or and then multiples and then a string  that would be described by r3  so that is a new addition to the  transition that takes me from q i to q j  of course i need to include the things  that would have taken me from q i to q j  in the first place  so i'm also unioning in r4 what was the  direct route from qy to qj that did not  uh transit through x  okay  so by making that  uh  uh  you know  new  um regular expression  on the q i to q j transition  i have compensated for the loss of x  for paths that go from q i to x  and then  out to q j now what i  need to do  is to  do that same thing for every pair qi and  qj  that are in the original machine  and so if i do that for every possible  pair  i'll be modifying all of the transitions  in the new machine  in a way  that  [Music]  compensates for the loss of x and now  the new machine has been repaired from  the damage that i caused by removing x  and it does the same language  it's kind of thing you need to think a  little bit about i understand um but at  least hopefully uh the uh the spirit  of what i just described to you uh comes  through that we're going to convert this  case machine with k states to one with  uh k minus one states by removing a  state and repairing the damage  and now it does the same language and  then i can remove another state and do  the same thing over and over again until  i get down to two states  okay so that's the um  idea and that really completes uh the  proof  that shows  that i can  uh  convert every gnfa  to a regular expression  okay um  and that really is uh the end of the  story for this um  and thus  i claim that dfas now and regular  expressions are equivalent  so let me get going to give you a little  check in here on this  uh  um  really just to see  if high level if you're following what's  going on  all right  uh so just take a look so we just showed  how to convert g n of a to regular  expression but we really wanted to  convert dfas to regular expressions so  how do we go from g n f converting g n  of a is to converting dfas because  they're not the same obviously right um  so how do we finish that  so there are three choices here  first we have to try to convert dfa to g  interface maybe or sure to convert gnfa  to df dfas or maybe we're already done  so maybe i better launch that poll while  you're while you're reading that  um  and there you  go hopefully you can  um all right  why don't i end this it's a little  worrying worrisome because uh i would  say we have a plurality who got the  right answer but not a majority uh  so uh let us share the results um i  think  so uh i sense not all of you are with me  um  but uh um you're gonna have to uh  uh  tr either that or you're  you know you're uh playing you're  reading your email while we're uh  talking i'm not sure but um  whatever it is um  you  need to think a little bit about what's  going on here because  um  what  you know the reason why we are done  is because dfas are a kind of g-n-phase  they're just they have a very simple  kind of regular expression on each  transition  um they  just have the regular expression which  is just a single symbol  so all dfas are automatically gnaphase  so if i can convert g anaphase i can  certainly convert dfas because dnf's  include the dfas i'm done it really was  number c  was the correct answer  okay  it's a good thing we're not  counting  uh  correctness here so participation is  good enough but i do think you need to  think about what's going on and making  sure that you're you know you're you're  you're following along so anyway that's  a uh  um  you know we'll carry on here but um  makes me a little concerned um  okay uh so um let us now move on um so  we're going to talk a little bit about  non-regular languages  um  so somebody's asking don't we have to  still make the dfas into the special  type yes we do we have to make them to  the special type but we already showed  how to make g interface into the special  type and dfa that that is going to apply  to dfas as well um  you know they'll become  gnfas you know you can add the extra  starts  at a new start state and at a new uh  accept state  add in all the transitions with which  you didn't have before with the empty  language  label  and you'll have a gnfa  from um a dfa but that applies to  gnaphase as a in general so it's nothing  special about dfas there anyway  uh i think you need to chew on that  hopefully uh you know you're you'll be  uh following going forward anyway let us  look now at non-proving non-regularity  so we're finished with our goal  of showing that regular languages that  the regular languages can either come  from  dfas or from regular expressions those  are the same in terms of from the  perspective of our course they're  interchangeable  okay so now uh  as we mentioned there are going to be  some languages which are not regular  which can't be done by dfas uh their  actual dfas are actually pretty weak as  a computational model and so there's all  sorts of very simple things that they  cannot do um  uh those there are some fairly  complicated things that they can do  surprisingly enough  but anyway um  there are some simple things they can't  do and so we have to develop a method  for showing that a language is not  regular um and that's going to be useful  for your homework um and in general for  just understanding the uh the power of  dfas  so how do we show our language is not  regular so  remember if you want to show a language  is regular basically what you need to do  is give a dfa  or you know you can use the closure  properties that's another way of showing  a language is regular but underneath  that it's basically constructing dfas  all right um to show a language is not  regular you have to give a proof  uh generally not a construction it's a  proof that there is no uh dfa or that  whatever uh that it's just going to be  impossible to make a dfa um  and we have to develop a method what  what is that proof method  um now  there is a tempting um  you know i've taught this course many  times and there's a kind of attempting  approach  uh that many people have um it's not  only going to apply for finite automata  but for other things too and believe me  it's not only  people in this class it's for people uh  out there in the um who are trying to  think about computation in general  which is to say  well you know  um  uh  you know i have some language of trying  to figure out if it's regular or not and  so i thought really hard how to make a  dfa and i couldn't find one therefore  it's not regular  that's that's not that's not a proof  just because you couldn't find a dfa  doesn't mean there is no dfa  you need to prove  that the language is not regular using  some method  um so i'm going to give you an example  where that kind of approach can lead you  wrong  and that is i'll give two examples  of  languages where  you might  try to prove they're regular or not and  you could be uh  in trouble if you just follow uh that  kind of informal approach  so if you take the language b  where these are string well let's assume  our alphabet is zeros and ones uh  b is the language of all strings that  have an equal number of zeros and ones  um  uh so you wanna know you know if i have  a thousand zeros i need to have a  thousand ones so basically the way you  test that you'd have to count up the  number of zeros count up the number of  ones  and see if those two counts are the same  and that's going to be really tough to  make a dfa do  um because it's you know how you're  going to remember such you know that  really big number of zeros that you know  the dfa might have 50 states but you  might need to count up to a hundred or a  million to figure out to count up how  many um  zeros you've seen  and it seems really hard to be able to  do that kind of account when you only  have 50 states uh some so whatever  number of states you have it's you're  not it seems hard to count uh when you  have a lim when you have a finite  automaton so the intuition is it's not  regular because a finite atomic done  can't count um which  in this case  you can convert that intuition into a  real proof i would say it's not a real  proof yet  but it can be made into a real proof  um  but compare that case with another  language which i'll call c  which instead of uh looking at its input  to see whether it has an equal number of  zeros and ones i'm going to look at the  input and look at the substrings of zero  ones and one zeros those two substrings  and count the number of occurrences of  zero one as a substring and the number  of occurrences of one zero as a  substring  okay just to make sure you're  understanding let's look at some  examples uh two examples  so the string zero one zero one  is not going to be in c  because if you count up the number of  zero ones and the number of one zeros  not the same so i'm even going to help  you here uh if you can see that the  number of zero ones is two  but there's uh  there's only a single occurrence of one  zero  okay so those are those two  counts are different  and so that's why this input string is  not in c  compare that with the string  zero one one zero  now if you count up the number of zero  one and one zero sub strings you're  going to get the same value because here  we have a single zero one and a single  one zero  and so now the two counts of those  number of substrings are the same  and so that's why you're in c  okay  now my question is  is c a regular language  well it looks like it shouldn't be  regular for the same reason that b is in  regular because you have to count up two  quantities and and compare them  um  so um  uh  now  um  so  if we  um  you know so that's our intuition that  you just can't do it for the with a  finite automaton because you have to do  the same kind of counting that you would  have had to do for language b  but here  you'll be you would be wrong  because c in fact is regular  um  uh  it has a much  simpler description  than the one i gave over here uh at the  beginning there's a the there's the very  same language c can be described in a  much much simpler way i'm not going to  tell you what it is you can mull that  over you can try some examples uh to  figure it out but it has a much simpler  description it's not totally trivial  description i mean there is some content  there but there is um you know it is the  kind of thing that a finite automaton  can do it wouldn't do the counting this  way um  so the moral is the punch line is that  sometimes the intuition works but it can  also be wrong  um and so the moral of the stories you  need to give a proof when you're when  you're doing things like that  okay  so what we're going to do next in the  second half of the lecture  is to give a method for proving  languages are not regular and again  you're going to need to use that on your  homework so i hope you get it um but uh  first of all oh did i  never stop sharing that poll forgive me  um  and so  uh  um  and so with that i think we'll take our  little requested break  uh  and um for five minutes  and uh  we'll be back in five minutes  um  so  break time  alrighty  we are done here  and um  proving languages not regular  okay  um  [Music]  the way we're going to prove languages  are not regular is by introducing um a  method called the pumping lemma  um  and the overarching plan at the pumping  lemma without getting into the  specifics of it  is to say show that  um  um that lemma says  all  regular languages have a certain  property  which we will describe  and so  to show a language is not regular  you simply show the language doesn't  have that property  um because  all regular languages have to have that  property and so by showing a language  fails to have the property it could not  be regular  okay that's that's the plan  um  now uh  the property itself  is a little complicated um to describe  um but not too bad i'll try to unpack it  for you  but first let's look at the statement of  dilemma  um  which says that  whenever you have a regular language  let's call it a so for every regular  language a  there's always a special value  called the pump  a number uh p we'll call it called the  pumping length  okay it's a special number and  uh  uh it's um  and  that  uh  uh  that length  um  uh  tells you  that  whenever a string is in that language  and it's longer than that length  then um  something special happens  you can take that string and you can  modify it and you still stay in the  language so anything that's longer than  that special length can be modified in a  certain way and you still say in the  language so let's look at the the actual  um statement of the lemma  so  there is a number p  such that if s is a string in the  language and it's longer than p or at  least of length p  then you can take s and you can cut it  up into three pieces x y and z  so they're just breaking s into three  pieces  where  um  you can take that middle piece  repeat it as many times as you like  and you're still staying the language  because that's the  uh  what the pumping llama is saying and  there's a bunch of other conditions here  too but  the the spirit of the pumping lumber  says whenever you have a regular  language there's some cut off such that  all strings longer than that cut off  can be what we call pumped you can take  that string you can find a section  somewhere in the middle of that string  or somewhere you cut it up in three  piece pieces you take them  that center piece and you can repeat it  you can pump it up  um and  by repeating that string and repeating  that piece the string gets longer and  longer  but you still stay in the language um  that's the special property that all  regular languages have  so kind of in an informal way and we'll  do so i'll try to help you get the  feeling for this um formally it says  that  you know if you have a regular language  then every long string so as long as by  informing my informal way of saying  bigger than this value p every long  string in the language can be pumped  and this result still stays in the  language and by pumped means i can cut  the string into three pieces and repeat  that middle piece as many times as i  want that's what i mean by pumping a  string  um  [Music]  so uh  uh we'll do some examples uh in a second  um  but first we're going to un see how to  prove this and hopefully that will give  you some feeling  also for why it's true  so  uh and actually maybe before i actually  jump into the proof let me let's look at  these three conditions here just to  understand it a little bit more uh  uh thoroughly  uh so condition one kind of says what i  just uh was was telling you  um i can break s into three pieces x y z  such that if i take x  y to the i z  so that's repeating y as many times as i  want so here's y to the i kind of  defined if that's helpful to you it's  just y i copies of y so i can take x y  to the i z and i remain in in the  language for every value of i even i  equals zero which means we're just  removing y uh which is sometimes  actually a useful thing to do but you  know  let's not get ahead of ourselves  um you know so  if  um you know  you know i can cut s i can i'm  guaranteed to be able to cut s up into x  y z so that the string x y y y is still  on the language or x y y y y y it's  still in the language um that's going to  be guaranteed for every regular language  that's good that's that's a feature  that's going to be true  um and furthermore and this is going to  be turning out to be it's not really  kind of part of the core idea of the  pumping lamb but it actually turns out  to be very helpful in applying the  pumping lemma  you can always cut it up in such a way  that the first two pieces are not longer  than that value p  um so this  it restricts on the ways you can cut the  thing up and that actually turns out to  be very helpful  um but let's first just look at the  proof of this uh giving kind of a little  bit the high level picture  um  so  my job is to show if i have a have a  string in my language let's say  think of it as a long string really long  um so it's length is more than p but i  think intuitively it's just a very long  string um  and i'm going to feed that string into  the machine  and watch what happens  something special happens when i feed  the string and i look at how the machine  proceeds  on that string  um  because  s is  so long  that  as i wander around inside the machine i  end have to end up coming back to the  same place more than once  um it's like you know if you have a  small park and you go for a long walk  you're going to end up coming back to  wave or what you've already seen you  just can't keep on seeing new stuff when  you have a more small area of space to  explore  so  um  so we're guaranteed that m is going to  end up repeating some state when it's  reading s because s is so long  so in terms pictorially um if you  imagine here this wiggly line is kind of  describing the path that m follows when  it's reading s it ends up coming back to  that state q j more than once so it  comes back here cycles around comes back  again before it ends up accepting we  know what it ends up accepting because  we're assuming we have a string that's  in the language so we picked s in the  language so it has to be accepted by m  but the important thing is that it  repeats a state  now um  how does that tell me i can cut s up  into those three pieces  well i'm going to get those three pieces  here um first of all let's observe that  here is a process you know as processing  s here is the that  written right on top of the string that  state repetition occurring uh qj more  than once and now if i look inside the  machine the part of s that took me  to q j i'm going to call x  the part that took me from q j back to  itself is i'm going to call y and the  partner took qj  to the accept state i'm going to call z  and i'm going to mark those often in s  and that gives me the way to cut s up  into three pieces  um  now  if you're appreciating  um what's going on inside the machine  you will see  why  m will also accept the string x y y  z  because  every time you know once you're at q j  you know if you go around once you come  back to q j and then if you go again  you'll come back to q j and as many  times as you keep seeing that y you're  just going to keep coming back to q j  so  it doesn't matter how many  y's you have you're going to still if  you follow it by z which is what you'll  do you'll end up accepting the string  um  and that's really the proof um i mean  you have to do a little bit more um  uh here just to understand i i should  have mentioned why i want to forbid y  being the empty string because if it was  the empty string it's not interesting it  doesn't change uh  um you know repeating it doesn't  actually change anything so i have to  make sure it's not empty but anyway  that's kind of a detail here  uh if you look at the string x y y z  that's still going to be accepted  okay so that's the proof of the pumping  lemma  all right uh so let's have a little  check-in uh related to that uh this is  not gonna be again not super hard but uh  um  more just a curiosity uh  uh  so the pumping alignment depends on the  fact that if m has p states and it runs  for more than p steps then it's going to  enter some state twice  so you may have seen that before it  actually has a name  um which some of you may have seen um  so let's see how to just get a poll here  and  i hope not too many of you are gonna  pick c i said some of you are oh well  uh yes  i think this one most of you are  you've seen this before  this is um  i think you pretty much all got it um  this is what's known as the pigeonhole  principle  uh so  you know here uh sharing the results uh  obviously i was having a little fun with  this and sure some of you are having fun  back at me that's okay  um  okay so let's continue on um let's see  how to use the pumping lemma  to  prove the language is not regular um so  i put the pumping limb up here just uh  so you can remember the statement of it  um  uh so let's take the language d which is  the language  0 to the k1 to the k  for any k so that's  some number of zeros followed by an  equal number of ones  we're going to prove that language is  not regular by using the pumping lemma  okay and this is going to be just an  iron-clad  proof it's not going to say well i  couldn't think of how to find you know i  you know i couldn't think of how to find  a finite automaton this is going to be  you know this is going to really uh be a  proof  okay so we want to show that d is not  regular  uh  and we're going to give uh these things  always go as a proof by contradiction so  proof by contradiction hopefully as a  reminder to you the way that works is  you're going to assume the opposite of  what you're trying to prove  and then  uh from that something crazy is going to  happen something you know is obviously  false or wrong  and so therefore your assumption which  is the opposite of what you were trying  to prove had to be wrong and so  therefore the thing you're trying to  prove has to be right  um that's the essence of what's called  proof by contradiction  so first of all we're going to assume to  get our contradiction that is regular  um  and which is what we're trying to show  is not the case  now if the is regular then we can apply  the pumping lamp  um up above here uh which  gives us that pumping length p  which says that any string longer than p  can be pumped and you stay in the  language that's what the pumping limit  tells you  so let's pick the string s  uh which is the string zero to the p one  to the p here's sort of a picture of s  off on the side here so a bunch of zeros  followed by an equal number of ones  and that string is in d  because d is  strings of that form  and it's longer than p  obviously it's a blank 2p  so the pumping limit tells us there's a  way to cut it up  um satisfying those three conditions  so how in the world could we  possibly cut s s up well remember the  three conditions and especially  condition three is going to come in  handy here  say that you can cut s up into three  pieces x y and z  where the first two pieces lie in the  first  uh  p  uh symbols of s  um  you know at most  p long  so x and y together are not very big  they don't extend beyond the first half  of x  and first half of s and in particular  they're all zeros  x and y are going to be all zeros z is  going to perhaps have some zeros and  we'll have the rest of the ones we'll  have the ones  um now um  uh  the pumping limit says if you cut it up  that way you can repeat why as many  times as you like and you stay in the  language but that's obviously false  because if you repeat y which is now has  only zeros you're going to have too many  zeros  and so the resulting string is no longer  going to be of the form 0 to the k 1 to  the k it's going to be  lots of zeros followed by not so many  ones that's not in the language and that  violates what the pumping limit tells  you is supposed to happen  and that's a contradiction  so therefore our assumption that d is  regular is false  and so we conclude that d is not regular  so that's a fairly simple one  i thought i would do another couple of  examples because you have this on your  homework and i thought it might be  helpful so here's the second one  slightly harder but not too much  let's take the language f which is  looks like this strings ww  um these are strings that uh two copies  of the same string  um  for any string uh that might be in sigma  star so for any string at all i'm going  to have two copies of that string and so  f is those strings can which can be  which are just you know two copies of  the same string  uh  okay we're going to show that f is not  regular these things always go the same  way it's the same pattern you prove by  contradiction so you assume for a  contradiction that oh d that's bad  uh  that was copied from my other slide  that's wrong let's see if i can actually  make this work here  good  assume for a contradiction that f is  regular  the pumping limit gives f is above and  so now we need to choose a string s  that's in f  okay to do the pumping and show that  the pumping lemma is going to fail  um you know it's you're going to pump  and you're going to get something which  is not in language which is uh  you know shows that the pump is  something has gone wrong but which s to  choose and and sometimes that's where  the creativity in applying the pumping  lemma  comes in  because you have to figure out which is  the right string you're going to pump on  um so you know you might try the string  well  0 to the p 0 to the p that's certainly  in f  it's two copies of the same string  here it is i've written  you know uh  um  lots of zeros followed by the same  number of zeros  the problem is if you use that string  um  [Music]  it actually  uh is a string that you can pump you can  break that string up into three pieces  and then if you let  uh y be the string zero zero that you  have to be a little careful just the  string just zero it doesn't work because  there's an evenness oddness phenomenon  going here so you might want to just  think about that but if you let this y  be the string 0 0  then if you have the string x  y  x any number of y's it's still just  going to be a bunch of zeros and you're  going to be able to see that that string  is still in the language so you haven't  learned anything  if the pumping lemon works  and and you're  satisfying the pumpkin you haven't you  haven't learned anything  so  what you need to find is some other  string  so that was a bad choice for s  find a different string so here's a  different choice 0 to the p1 0 to the p1  so that's two copies of the same string  and you're going to show it can't be  we're going to show it can't be pumped  so here's a picture of that string here  so 0 is followed by 1 0's followed by 1.  and now it's very similar to the first  argument  if you cut it into three pieces in such  a way that it satisfies the conditions  the first two pieces are going to be  residing only among the zeros and so  therefore when you repeat  a y um  you're no longer going to have two  copies of the same string um and so  won't be in the language so therefore  you've got a contradiction and f is not  regular so you have to i you have to  play with the pumping lemma a little bit  if you haven't seen that before it's  going to be  you know it takes a little getting used  to but you have a few homework questions  that need to be solved using the pumping  level all right so now um  let's look at uh  lastly there is another method that can  come in which is combining closure  properties with the pumping lemma  so closure properties sometimes help you  so let's look at the language b which is  actually we saw earlier in the lecture  where we have an equal number of zeros  and ones  now we could prove that directly using  the pumping lemma as not being regular  but it's actually even easier  um  uh what we're going to prove  uh that it  we're going to prove that it's not  regular in a different way first we're  going to assume for contradiction as we  often do that it is regular um  and now we're going to use something  we're going to use some other knowledge  we're not going to use the pumping llama  here um because we're going to take  advantage of an earlier case where we  use the pumping level  and so um  now we know that the string the language  0 star 1 star is a regular language  because it's described by a regular  expression if you take the  b  which is the equal numbers of zeros and  ones  and you intersect it with zero star one  star  that's going to be a regular language if  b was regular  using closure under intersection  but this language b intersect zero star  one star  is the language  of  equal numbers of zeros and ones where  the zeros come first  and that's the language d that we show  two slides back  that we already know can't be regular  so that intersection cannot be regular  and so it violates the closure property  um  and again we get a contradiction  uh so  um that's a different way of  sometimes making a shortcut  to prove a language is not regular  okay  so we have in our last uh ten minutes or  so we're going to shift gears totally in  an entirely different way and consider a  new model of computation uh which is  more powerful that can actually do  things that we can't do with a with  finite automata and these are called  context-free grammars so this is really  just a kind of an introduction  we're going to spend uh all of next  lecture uh looking at context-free  grammars um and their associated  languages uh but let's just to kind of  get us  get a preview  so a context-free grammar looks like  this you have a bunch of these  um  uh  um what we call substitution rules or  rules sometimes  would just look like a symbol arrow a  string of symbols  all right  that's what a context-free grammar looks  like at a high level  let's define some terms um  so a rule as i just described is uh  going to be look it's going to be a  symbol which we're going to call a  variable  um and that's going to have an arrow to  a string of other possibly other  variables and  symbols called terminals  um  so a variable is a symbol that appears  on the left hand side of a rule  anything that appears on the left hand  side is going to be considered to be a  very ver a variable um  okay  so s and r are both variables  um  now  other symbols that appear in the grammar  which don't appear in the in in the  left-hand side  those  are going to be called terminals  so here 0 and 1 are terminals  now you may think that empty string  should also be a terminal but that's not  a symbol an empty string is a string  it's just a string of length zero so i'm  not considering empty string to be a  terminal  so  and then there's going to be a special  variable which is going to be considered  the starting variable just like we had a  starting state and that's typically  going to be written as the top left  symbol so this symbol s here is going to  be the starting symbol  and grammars can be used to  uh define languages  and to gen well to generate strings and  to define languages so first of all  let's see how  a grammar using this as an illustration  can generate strings um  actually just to emphasize this uh these  terminology here in this particular  example we had three rules  uh the two variables were r and s the  two terminals were zero and one  and the start variable was this top  left-hand symbol as i mentioned the s  okay  so grammars generate strings the way  they do is  you follow a certain procedure which is  really pretty simple  you  write down first of all the starts  variable and i'll do an example in a  second  you write down the start variable  and then you take a look what you've  written down  and if it has any variables in it you  can  apply  one of the corresponding right hand  sides of a rule  um  to as a substitution for that variable  and so like for example if you have an s  in the thing you've written down you can  substitute for that s a zero s one  or you can substitute for that s and r  or if you have an r you can substitute  for that's an empty string  so you're just going to keep on doing  that substitutions over and over again  until there are no variables left so  there's nothing left to substitute  only terminals remain  at that point you have generated a  string in the language  okay so the language then is the  collection of all generated strings  okay let's do an example here's an  example of g1 generating some string so  as i mentioned first of all you're going  to write down the start variable  and i'm just going to illustrate this in  sort of two parallel tracks here  on the left side i'm going to show you  the tree of substitutions and on the  right side i'm going to show you the  resulting string that you get by  applying those substitutions  okay  so over here i'm going to substitute for  s the string 0 s1 so on the right hand  side i just have 0 s1 because that's  what i substituted for s but you'll see  it's not going to it's going to look a  little different in a second  here i'm going to again i still have a  variable so i'm going to substitute for  s 0 s 1.  now i have the string resulting string 0  0 s 1 1 because i've substituted 0 s 1  for the previous s but the 0 and 1 stick  around from before they don't go  anywhere so i have at this point 0 0 s 1  1. now  uh i'm going to take a different choice  i'm going to substitute for s you know i  could have gone either way this sort of  something like almost like  non-determinism here because you have a  choice  uh i'm going to substitute for s um  instead of 0 s1 i'm going to substitute  r because that's also legitimate in  terms of the rules  and so now i'm going to have  0 0 r  1 1.  and now r has there's no choices here r  can only be substituted for by an empty  string  so i get to r becomes just empty string  and in terms of the string generated  empty string doesn't add anything it  just really is  nothing it's a nothing so i get the  string 0 0 1 1 and this is a string just  of terminal symbols  and so that is a string in the language  of  the grammar g1  okay  if you think about it g1's language is  that language that we saw before uh  which i think we called  d  um  zero to the k one to the k for k greater  than or equal to zero so this is an  example of the language that a  context-free grammar can do but i find  that automaton cannot do  okay  so that is our little introduction to  con oops there's one more check in here  um  oh yeah so i'm asking you to actually  look at  let me get myself a look out of this  picture  um  so you  don't see me blocking things  and we will do one last check-in  make sure you're staying around for the  whole thing  now you can now there could be several  of these strings that are in the  language you have to click them all  all the ones that you have found that  are in the language of this grammar that  can be generated by grammar g2  you have to click those i'll give you a  little bit more time on this one um  to see which ones uh g2 can generate  um  i'll give you a hint it's more than one  but not all  uh  so i see you're making some progress  here  um  interesting  so please uh we're gonna wrap this up  very quickly  uh you can't call us somebody's telling  me you can't unclick thank you good to  know  um  [Music]  okay so still things are coming in here  so  uh  let's not we're we're running toward the  end of the hour here i don't want to go  over so i'm going to end it in five  seconds  uh click away and don't forget  uh  we're not uh going to charge you if you  get it wrong um  sharing results  uh  i don't know why it has an orange one  there because  there are several correct answers here  um  so it's a b and d are correct  um you can get any of any of those um  it's really sort of two copies of the  language we had before  uh next to one another uh  and so  um  the only thing you cannot get is  one zero one zero  um so i encourage you to think about  that  and i will uh  uh  come to our last side of today um which  is just a quick review um  i can put myself back  so we show how to convert dfas to  regular expressions  and the summary is that dfas nfas  gnfas even ray and regular expressions  are all equivalent um in the class of  languages they can describe  uh  the second thing we did was a method for  proving languages not regular by using  the pumping lemma or closure properties  and lastly we introduced context-free  grammars and we're going to see more  about those on thursday  so with that i think we're out of time  and  other thank you for the  notes of appreciation and um  i will um  i think we're gonna  end here um and uh  see you  um on thursday if not before

2
00:00:26,150 --> 00:00:26,160
okay folks  um  here we are again  welcome back  for another episode of theory of  computation this is lecture number three  um  i  am fir i'm going to review how what  we've been doing um we've been looking  at finite automata  and regular languages those are the  languages that the fine automata can  recognize  and we  talked about  non-determinism so we had  non-deterministic finite automata and  deterministic finite automata we showed  that they're equivalent  we looked at the closure properties over  the regular operations union  concatenation and star and showed that  the  regular language is really the class of  regular languages is closed under those  regular operations  and we used the constructions that we  developed in the proof of those closure  properties to show that the  we can give away to convert  regular expressions to finite automata  so that is uh was  a  part way toward our goal  of showing that these regular  expressions and finite automata are  equivalent with respect to the class of  languages they describe namely the  regular languages so regular expressions  of finite autonomic are interchangeable  from the perspective of what kinds of  languages you can do with them  so we're going to finish that off today  so let's take a look at what  our next  topics we're going to be covering  we're going to  reverse  the  construction that we gave last time  which allowed us to convert regular  expressions to finite automata now we're  going to go backwards we're going to  show how to convert finite automata back  to regular expressions  and um that  those two  constructions together uh show us that  the regular expressions finite automata  can be inter interconverted from one  another and they're therefore equivalent  with respect to the kinds of things they  they can do in language  recognition or generation  then we're going to prove that uh we're  going to look at how you prove certain  languages are not regular they're beyond  the capabilities of fine art automata  and finally at the end we're going to  introduce a new model of computation  which is more powerful  than the finite automata and regular  expressions namely the context-free  grammars  those can do  other kinds of languages that the  simpler find at a time but the regular  expressions models can't do um  and i i would also just like to note  that  a lot of what we're doing is a warm up  toward the more powerful models of  computation that we're going to be  looking at later um well in a week or so  which are  more kind of general purpose  computation  but along the way introducing these  models of finite automata in  context-free languages  is  interesting and helpful because many of  those um a number of those models turn  out to be useful in a number of  applications um whether it's from  you know pro linguistics to  uh programming languages um and a  variety of different uh  parts of computer science and other  fields as well use those notions so  they're they're useful notions um  and beyond just uh  in this course um  okay so  um  i just wanted  a couple of administrative things to  touch on uh we are going to have  additional check-ins today um as i  uh mentioned to you we're gonna start  counting participation not correctness  of just participation in the live  check-ins  so um with that let us  move on to today's material um  as i mentioned we're going to be showing  how to convert  finite automata to regular expressions  um and that's going to complete our  equivalence of finite automata and  regular expressions so just to recap  what we did last time  we showed that if you have a regular  expression  um  uh  and it describes some language then that  language is regular  uh so in other words um we have a way of  we gave a way of converting regular  expressions to finite automata as kind  of shown in this diagram  that's what we did last time  now we're going to go the other way um  we're going to show how to convert oh  and just a reminder in case you're just  getting yourself  your memory size your memory uh to work  um maybe it'll help you just to remember  that we actually did an example of that  conversion we looked at this um regular  expression a union a b star and we  actually worked through the process of  converting that oops i need to make  myself smaller so you can see all that  we went through the process of um  converting a union a b star as an  example of that um  of uh  minimus  okay  uh  well  um  we went through the process of actually  doing that conversion and now we're  going to show how to do it the other way  around  all right so  um  so we're going to invert that  and go backwards the other way  um so today's theorem is to show that if  a is regular namely its  uh um  the language of some finite automaton  um then um  uh  you can convert it to a regular  expression which will describe that same  language so basically we're going to  give a conversion from finite automata  to regular expressions okay um  but before we do that we're going to  have to introduce a new concept um so  we're not going to be able to dive right  into that conversion we're going to have  to do introduce a new model first which  is going to facilitate that conversion  and that new model is called it's in yet  another kind of finite automaton called  a generalized  non-deterministic finite automaton or a  generalized nfa or just simply a gnfa  okay so this is yet another variant of  the finite automaton model um  and  conceptually it's very sim simple it's  similar to the nfas i'll give you here's  a picture of a  gnfa  named  g1 very similar to the nfas but if you  look at it for a second you'll see that  the  transitions have more complicated labels  for the anaphase who are only allowing  just single symbols or the empty string  to appear on the labels now i'm actually  allowing you to put full regular  expressions on the labels  for the automaton  now we have to understand how  a gnfa process as  its input and the way it works is  um not complicated to understand  um  when you're getting an input string  feeding when the when a gnfa is  processing an input string it starts at  the start state just like you would  imagine  but now to go along a transition instead  of reading just a single symbol or the  empty string as a as in the case for the  nondeterministic machine  um  it actually gets to read a whole string  at one step kind of at one byte  it can read an entire string um and go  along that transition um  uh  arrow provided that  trunk of the input that it read  is in the regular expression  that that  uh  transition uh  has as its label  so for example  um  this you can go from q1 to q2 in one  step in this gnfa by reading the by  reading aabb off the input  so it reads all those four symbols all  at once  it just swoops them up and then moves  from q1 to q2  in one step  okay and then when it's in q2  it can read aab  and move to q3 and q3 happens there's  nowhere to go um so this is going to be  a non-deterministic machine there might  be several different ways of processing  the input and if any one of them gets to  an accepting state at the end of the  input  we say the gnfa accepts  so it's similar to non-deterministic to  nfa's in in the way the acceptance  criterion works  um so you know you could do an example  but hopefully the concept of how this  works is reasonably  you know you can at least buy it um that  it processes  um the input in  chunks at a time and those chunks have  to be described by the  uh regular expressions on the transition  our arrows as it moves along those  transitions  okay  so um  what we're going to do  now  is to convert  not  dfas to regular expressions we're going  to convert gnfas to regular expression  that's even harder  because gnfas are allow you to do all  sorts of other things besides just  ordinary dfas  so that's a harder job why am i making  my life harder well you'll see in a  minute  that it's going to actually turn out to  be helpful to be working with a more  powerful model um  in the way this construction is going to  work  okay  now before i dive in and do the  construction from gnfas to regular  expressions i'm going to make a  simplifying assumption about the g  anaphase  i'm going to put them in a special form  that's going to make it easier to do the  conversion  and that simpler form is  first of all i'm going to assume that  gnfa has just a single accepting state  and that accepting state is not allowed  to be the start state  okay so it has to have just a single  accepting state i've already violated  that um convenient assumption in this  gnfa because i have here two  uh accepting states that's not what i  want i want to have just one  well the thing is it's easy to obtain  just one just to modify the machine so  that i have just one by  adding a new accepting state which is  branch two from the former accepting  states by empty transition so i can  always jump from q2 to q4 at any time  without even reading any input just  going along this empty transition  and then i declassify the former  accepting states as accepting  and now i have here just a single  accepting state and  because it's going to be a new state  that i added it won't be the start state  and i have  accomplished that one aspect of my  assumption about the form of the gnfa  but there's another thing that i want to  do too  i want to assume  um as you'll see which is going to be  convenient in my uh  construction that we will have  transition arrows going from every state  to every other state in fact i want  transition i was going from every state  even back to themselves  um  i want the there to be all of all  possible transition arrows should be  present  um  uh with with two exceptions  uh for for the start state there should  be only transition arrows exiting the  start state  and for the accepting state there's just  one now there should be only transition  arrows coming in to the start state  so it's kind of what you would imagine  as being reasonable um for the other  states which are not accepting or or um  starting  there should be  transition arrows leaving and coming  from everywhere else but for the start  states just leaving and from the except  state just coming in  and you could easily modify the machine  to achieve that um let's just see how to  do that in one example so from notice  that from q3 to q2 there is no  transition right now and that's not good  that's not what i want i want that to be  a transition from q3 to q2 well i'll  just add that transition in  but i'm going to label it with the empty  language regular expression  so that means yeah the transition is  there but you never can take it  so it doesn't change  the  language that the machine is going to be  recognizing but it fulfills my um  uh  my assumption my convenient assumption  that we have all of these transition  arrows being present in the machine  okay so uh  anyway i hope you uh will buy it it's  not gonna be re if you don't quite get  this don't worry it's not totally  critical that you're following or these  little these little adjustments and  modifications to the gnf8 but it will be  helpful to understand what gnf  themselves how they work  so as i mentioned we can easily modify  gnfa to have the special form that we're  assuming here  all right so now we're going to jump in  and start doing the conversion so we're  going to have a lemma which is like a a  theorem that really is just a local  interest here it's not a  general interest theorem it's going to  be relevant just to gnfa which it really  just defined to help us do this  conversion they really don't have any  other independent value  so every you want to show that every g n  of a has an equivalent regular  expression r  that's really my goal um  and the way we're going to prove that  is by induction  it's going to be by induction on the  number of states of the gnfa  now  you really should be familiar with  induction as one of the uh expectations  for being in this course but in case  you're a little shaky on it don't worry  i'm gonna unpack it um as a procedure  it's really just recursion you know  induction is just a and a proof that  uses induction is really just a proof  that calls itself it's just a proof that  it's a recursive proof that's all it is  so if you're comfortable with the  recursion you'll be comfortable with  induction um but anyway i'm going to  describe this as a procedure so if  you're a little shaky on induction don't  worry  um  so the basis is so first i'm going to  handle the case where the gnfa has just  two states  okay um  now remember i'm assuming now my gnfas  are in the special form  so you can't even have a gnfa with one  state because it has to have a start  state and it has to have an accept state  and they have to not be the same so the  smallest possible gnfa to worry about is  a two-state gnfa  okay now if we have a if we happen to  have a two-state gnfa it turns out to be  very easy to find the equivalent regular  expression why  because  that tuesday gnfa can only look like  this  it can have a start state can have an  accept state  and it can only have a transition going  from the start to the accept because no  other transitions are  allowed um it only has outgoing from the  start only incoming from the uh  to the except and so there's only one  transition and it has a label with a  regular expression r  so what do you think the equivalent  regular expression is for this g nfa  it's just simply the one that's labeling  that transition because that tells us  when i can go from the start to the  accept and there's nothing else the  machine can do it just makes one step  which is to accept its input if it's  described by that regular expression so  therefore the equivalent regular  expression that we're looking for is  simply label on that single transition  okay so two state g nfas are easy  um but what if what happens if you have  more states then you're gonna actually  have to do some work  um  so  we call that the induction step that's  when we have more than two states  and what that the way the induction  works is we're going to assume we  already know how to do it for k minus 1  states  and we're going to use that knowledge to  show how to do it for k-states  so in other words um we already know how  to do it for two states  i'm going to use that fact to show how  to do it for three states  and then use the fact that i can do it  for three states to show how to do it  for four states and so on and so on  all right  and the idea for how to do that is  actually uh  pretty  uh easy to to grasp  um what we're going to do is if we have  a k-state gnfa that we want to convert  we're going to con we're going to change  that k state g n of a to a k minus 1  state g n of a  and then use our assumption that we  already know how to do the k minus 1  state g nfa  all right  so um  in terms of a picture i'm going to take  a k-state to prove that i can always  convert k-state g-n-phase uh to regular  expressions  i'm going to show how to convert the  k-state um one into an equivalent k  minus one state g of a and then if you  just like to think of it this  procedurally the k minus one will gets  converted to a k minus two gets  converted to a k minus three and so on  and so on until i get down to two  which then i know how to do directly  okay so the whole name of the game here  is figuring out how to convert a  gnfa that has k states  into another one that has one fewer  state that does the same language  okay so you have to  hold that in your head i mean i wish i  had more blackboard space here but you  know it's very limited here so you have  to remember what would what we're going  to be doing on the next slide  because that's going to finish the job  for us as long as i can show in general  how to convert a k-state gnfa to a gnfa  that is one fewer state but it still  does the same language  i'm good  because then i can keep iterating that  till i get down to two  all right  so here is um  this is the  the guts of the argument um so i have my  k-state machine here's my my start state  here's my accept state  um here's my k minus one state that  machine that i'm going to be uh building  for you it's actually going to be  be look almost exactly the same i'm just  going to remove one state  um  from the from the from the bigger  machine  so i'm going to pick any state which is  not the  start state or the accept state um here  it is pictured here  i mean all of the states of the k-state  machine are going to appear in the k-1  state machine  except for one state that i'm going to  rip out  okay  that's the state x it's now here as a  ghost  it's been removed  um  uh it's not there anymore okay but i'm  just helping you to remember that used  to be there  by showing his shadow  but it's a  uh i have taken  my original machine that had k-states  um  and basically just ripped out of state  um and now i've  you know one fewer state  so the good news  is that i now have a machine with k  minus one states  that's what i want  but the bad news is that it doesn't do  the same language anymore  it's i i broke the machine by rip just  if you're just going to rip out a state  you know who knows what the machine is  going to do it's going to be  probably not the same as what the  original machine did  so what i need to do  then  is repair the damage  i've got to fix the damage that i caused  by removing  x okay um  and  whatever  role  x was playing  in the original machine  i've got to make sure  that  the the new machine that i have which  doesn't have x anymore can still do the  same things  um that the original machine did  um and so the way i'm going to do that  is look at all of the paths that could  go through x and make sure that they're  still present even though i don't have x  anymore  and the way i'm going to do that is i'm  going to take  um  [Music]  consider  a part of a path that might use x  so it starts  let's pick two states q i and two j  in the uh machine that had k states  let me just here  i know this is uh  okay um  we have if we have uh we'll pick two  states q i and q j  um in in in the original machine now qi  might  have the possibility of going to state x  and then x might have a self loop  and then it might go to 2j  the new machine doesn't have any x  anymore  the way i'm going to fix that  is by  replacing the label that goes directly  from i to j  with a new label  that  adds in all of the things i lost  when i removed x  okay that's  that's the whole idea here so here is q  i to q j but there's no x anymore  how could i get  from q i to q j  um  um you know  you know what what were the  inputs  that could have brought us from qi to qj  via x  well they would have been an input  that read a string described by r1  i might have self-looped at x a few  times  so i might have read several strings  that are described by r2  and then i would have read a string that  was described by r3 and now i'm at qj  okay  so  uh the new label  that i'm going to place over here is  going to be  uh the strings that i get from reading  are one you know reading a a  a  a string that described by r1  then multiple copies of a stretch you  know  multiple strings that are possibly  describing r2 which is the same as r2  star  or and then multiples and then a string  that would be described by r3  so that is a new addition to the  transition that takes me from q i to q j  of course i need to include the things  that would have taken me from q i to q j  in the first place  so i'm also unioning in r4 what was the  direct route from qy to qj that did not  uh transit through x  okay  so by making that  uh  uh  you know  new  um regular expression  on the q i to q j transition  i have compensated for the loss of x  for paths that go from q i to x  and then  out to q j now what i  need to do  is to  do that same thing for every pair qi and  qj  that are in the original machine  and so if i do that for every possible  pair  i'll be modifying all of the transitions  in the new machine  in a way  that  [Music]  compensates for the loss of x and now  the new machine has been repaired from  the damage that i caused by removing x  and it does the same language  it's kind of thing you need to think a  little bit about i understand um but at  least hopefully uh the uh the spirit  of what i just described to you uh comes  through that we're going to convert this  case machine with k states to one with  uh k minus one states by removing a  state and repairing the damage  and now it does the same language and  then i can remove another state and do  the same thing over and over again until  i get down to two states  okay so that's the um  idea and that really completes uh the  proof  that shows  that i can  uh  convert every gnfa  to a regular expression  okay um  and that really is uh the end of the  story for this um  and thus  i claim that dfas now and regular  expressions are equivalent  so let me get going to give you a little  check in here on this  uh  um  really just to see  if high level if you're following what's  going on  all right  uh so just take a look so we just showed  how to convert g n of a to regular  expression but we really wanted to  convert dfas to regular expressions so  how do we go from g n f converting g n  of a is to converting dfas because  they're not the same obviously right um  so how do we finish that  so there are three choices here  first we have to try to convert dfa to g  interface maybe or sure to convert gnfa  to df dfas or maybe we're already done  so maybe i better launch that poll while  you're while you're reading that  um  and there you  go hopefully you can  um all right  why don't i end this it's a little  worrying worrisome because uh i would  say we have a plurality who got the  right answer but not a majority uh  so uh let us share the results um i  think  so uh i sense not all of you are with me  um  but uh um you're gonna have to uh  uh  tr either that or you're  you know you're uh playing you're  reading your email while we're uh  talking i'm not sure but um  whatever it is um  you  need to think a little bit about what's  going on here because  um  what  you know the reason why we are done  is because dfas are a kind of g-n-phase  they're just they have a very simple  kind of regular expression on each  transition  um they  just have the regular expression which  is just a single symbol  so all dfas are automatically gnaphase  so if i can convert g anaphase i can  certainly convert dfas because dnf's  include the dfas i'm done it really was  number c  was the correct answer  okay  it's a good thing we're not  counting  uh  correctness here so participation is  good enough but i do think you need to  think about what's going on and making  sure that you're you know you're you're  you're following along so anyway that's  a uh  um  you know we'll carry on here but um  makes me a little concerned um  okay uh so um let us now move on um so  we're going to talk a little bit about  non-regular languages  um  so somebody's asking don't we have to  still make the dfas into the special  type yes we do we have to make them to  the special type but we already showed  how to make g interface into the special  type and dfa that that is going to apply  to dfas as well um  you know they'll become  gnfas you know you can add the extra  starts  at a new start state and at a new uh  accept state  add in all the transitions with which  you didn't have before with the empty  language  label  and you'll have a gnfa  from um a dfa but that applies to  gnaphase as a in general so it's nothing  special about dfas there anyway  uh i think you need to chew on that  hopefully uh you know you're you'll be  uh following going forward anyway let us  look now at non-proving non-regularity  so we're finished with our goal  of showing that regular languages that  the regular languages can either come  from  dfas or from regular expressions those  are the same in terms of from the  perspective of our course they're  interchangeable  okay so now uh  as we mentioned there are going to be  some languages which are not regular  which can't be done by dfas uh their  actual dfas are actually pretty weak as  a computational model and so there's all  sorts of very simple things that they  cannot do um  uh those there are some fairly  complicated things that they can do  surprisingly enough  but anyway um  there are some simple things they can't  do and so we have to develop a method  for showing that a language is not  regular um and that's going to be useful  for your homework um and in general for  just understanding the uh the power of  dfas  so how do we show our language is not  regular so  remember if you want to show a language  is regular basically what you need to do  is give a dfa  or you know you can use the closure  properties that's another way of showing  a language is regular but underneath  that it's basically constructing dfas  all right um to show a language is not  regular you have to give a proof  uh generally not a construction it's a  proof that there is no uh dfa or that  whatever uh that it's just going to be  impossible to make a dfa um  and we have to develop a method what  what is that proof method  um now  there is a tempting um  you know i've taught this course many  times and there's a kind of attempting  approach  uh that many people have um it's not  only going to apply for finite automata  but for other things too and believe me  it's not only  people in this class it's for people uh  out there in the um who are trying to  think about computation in general  which is to say  well you know  um  uh  you know i have some language of trying  to figure out if it's regular or not and  so i thought really hard how to make a  dfa and i couldn't find one therefore  it's not regular  that's that's not that's not a proof  just because you couldn't find a dfa  doesn't mean there is no dfa  you need to prove  that the language is not regular using  some method  um so i'm going to give you an example  where that kind of approach can lead you  wrong  and that is i'll give two examples  of  languages where  you might  try to prove they're regular or not and  you could be uh  in trouble if you just follow uh that  kind of informal approach  so if you take the language b  where these are string well let's assume  our alphabet is zeros and ones uh  b is the language of all strings that  have an equal number of zeros and ones  um  uh so you wanna know you know if i have  a thousand zeros i need to have a  thousand ones so basically the way you  test that you'd have to count up the  number of zeros count up the number of  ones  and see if those two counts are the same  and that's going to be really tough to  make a dfa do  um because it's you know how you're  going to remember such you know that  really big number of zeros that you know  the dfa might have 50 states but you  might need to count up to a hundred or a  million to figure out to count up how  many um  zeros you've seen  and it seems really hard to be able to  do that kind of account when you only  have 50 states uh some so whatever  number of states you have it's you're  not it seems hard to count uh when you  have a lim when you have a finite  automaton so the intuition is it's not  regular because a finite atomic done  can't count um which  in this case  you can convert that intuition into a  real proof i would say it's not a real  proof yet  but it can be made into a real proof  um  but compare that case with another  language which i'll call c  which instead of uh looking at its input  to see whether it has an equal number of  zeros and ones i'm going to look at the  input and look at the substrings of zero  ones and one zeros those two substrings  and count the number of occurrences of  zero one as a substring and the number  of occurrences of one zero as a  substring  okay just to make sure you're  understanding let's look at some  examples uh two examples  so the string zero one zero one  is not going to be in c  because if you count up the number of  zero ones and the number of one zeros  not the same so i'm even going to help  you here uh if you can see that the  number of zero ones is two  but there's uh  there's only a single occurrence of one  zero  okay so those are those two  counts are different  and so that's why this input string is  not in c  compare that with the string  zero one one zero  now if you count up the number of zero  one and one zero sub strings you're  going to get the same value because here  we have a single zero one and a single  one zero  and so now the two counts of those  number of substrings are the same  and so that's why you're in c  okay  now my question is  is c a regular language  well it looks like it shouldn't be  regular for the same reason that b is in  regular because you have to count up two  quantities and and compare them  um  so um  uh  now  um  so  if we  um  you know so that's our intuition that  you just can't do it for the with a  finite automaton because you have to do  the same kind of counting that you would  have had to do for language b  but here  you'll be you would be wrong  because c in fact is regular  um  uh  it has a much  simpler description  than the one i gave over here uh at the  beginning there's a the there's the very  same language c can be described in a  much much simpler way i'm not going to  tell you what it is you can mull that  over you can try some examples uh to  figure it out but it has a much simpler  description it's not totally trivial  description i mean there is some content  there but there is um you know it is the  kind of thing that a finite automaton  can do it wouldn't do the counting this  way um  so the moral is the punch line is that  sometimes the intuition works but it can  also be wrong  um and so the moral of the stories you  need to give a proof when you're when  you're doing things like that  okay  so what we're going to do next in the  second half of the lecture  is to give a method for proving  languages are not regular and again  you're going to need to use that on your  homework so i hope you get it um but uh  first of all oh did i  never stop sharing that poll forgive me  um  and so  uh  um  and so with that i think we'll take our  little requested break  uh  and um for five minutes  and uh  we'll be back in five minutes  um  so  break time  alrighty  we are done here  and um  proving languages not regular  okay  um  [Music]  the way we're going to prove languages  are not regular is by introducing um a  method called the pumping lemma  um  and the overarching plan at the pumping  lemma without getting into the  specifics of it  is to say show that  um  um that lemma says  all  regular languages have a certain  property  which we will describe  and so  to show a language is not regular  you simply show the language doesn't  have that property  um because  all regular languages have to have that  property and so by showing a language  fails to have the property it could not  be regular  okay that's that's the plan  um  now uh  the property itself  is a little complicated um to describe  um but not too bad i'll try to unpack it  for you  but first let's look at the statement of  dilemma  um  which says that  whenever you have a regular language  let's call it a so for every regular  language a  there's always a special value  called the pump  a number uh p we'll call it called the  pumping length  okay it's a special number and  uh  uh it's um  and  that  uh  uh  that length  um  uh  tells you  that  whenever a string is in that language  and it's longer than that length  then um  something special happens  you can take that string and you can  modify it and you still stay in the  language so anything that's longer than  that special length can be modified in a  certain way and you still say in the  language so let's look at the the actual  um statement of the lemma  so  there is a number p  such that if s is a string in the  language and it's longer than p or at  least of length p  then you can take s and you can cut it  up into three pieces x y and z  so they're just breaking s into three  pieces  where  um  you can take that middle piece  repeat it as many times as you like  and you're still staying the language  because that's the  uh  what the pumping llama is saying and  there's a bunch of other conditions here  too but  the the spirit of the pumping lumber  says whenever you have a regular  language there's some cut off such that  all strings longer than that cut off  can be what we call pumped you can take  that string you can find a section  somewhere in the middle of that string  or somewhere you cut it up in three  piece pieces you take them  that center piece and you can repeat it  you can pump it up  um and  by repeating that string and repeating  that piece the string gets longer and  longer  but you still stay in the language um  that's the special property that all  regular languages have  so kind of in an informal way and we'll  do so i'll try to help you get the  feeling for this um formally it says  that  you know if you have a regular language  then every long string so as long as by  informing my informal way of saying  bigger than this value p every long  string in the language can be pumped  and this result still stays in the  language and by pumped means i can cut  the string into three pieces and repeat  that middle piece as many times as i  want that's what i mean by pumping a  string  um  [Music]  so uh  uh we'll do some examples uh in a second  um  but first we're going to un see how to  prove this and hopefully that will give  you some feeling  also for why it's true  so  uh and actually maybe before i actually  jump into the proof let me let's look at  these three conditions here just to  understand it a little bit more uh  uh thoroughly  uh so condition one kind of says what i  just uh was was telling you  um i can break s into three pieces x y z  such that if i take x  y to the i z  so that's repeating y as many times as i  want so here's y to the i kind of  defined if that's helpful to you it's  just y i copies of y so i can take x y  to the i z and i remain in in the  language for every value of i even i  equals zero which means we're just  removing y uh which is sometimes  actually a useful thing to do but you  know  let's not get ahead of ourselves  um you know so  if  um you know  you know i can cut s i can i'm  guaranteed to be able to cut s up into x  y z so that the string x y y y is still  on the language or x y y y y y it's  still in the language um that's going to  be guaranteed for every regular language  that's good that's that's a feature  that's going to be true  um and furthermore and this is going to  be turning out to be it's not really  kind of part of the core idea of the  pumping lamb but it actually turns out  to be very helpful in applying the  pumping lemma  you can always cut it up in such a way  that the first two pieces are not longer  than that value p  um so this  it restricts on the ways you can cut the  thing up and that actually turns out to  be very helpful  um but let's first just look at the  proof of this uh giving kind of a little  bit the high level picture  um  so  my job is to show if i have a have a  string in my language let's say  think of it as a long string really long  um so it's length is more than p but i  think intuitively it's just a very long  string um  and i'm going to feed that string into  the machine  and watch what happens  something special happens when i feed  the string and i look at how the machine  proceeds  on that string  um  because  s is  so long  that  as i wander around inside the machine i  end have to end up coming back to the  same place more than once  um it's like you know if you have a  small park and you go for a long walk  you're going to end up coming back to  wave or what you've already seen you  just can't keep on seeing new stuff when  you have a more small area of space to  explore  so  um  so we're guaranteed that m is going to  end up repeating some state when it's  reading s because s is so long  so in terms pictorially um if you  imagine here this wiggly line is kind of  describing the path that m follows when  it's reading s it ends up coming back to  that state q j more than once so it  comes back here cycles around comes back  again before it ends up accepting we  know what it ends up accepting because  we're assuming we have a string that's  in the language so we picked s in the  language so it has to be accepted by m  but the important thing is that it  repeats a state  now um  how does that tell me i can cut s up  into those three pieces  well i'm going to get those three pieces  here um first of all let's observe that  here is a process you know as processing  s here is the that  written right on top of the string that  state repetition occurring uh qj more  than once and now if i look inside the  machine the part of s that took me  to q j i'm going to call x  the part that took me from q j back to  itself is i'm going to call y and the  partner took qj  to the accept state i'm going to call z  and i'm going to mark those often in s  and that gives me the way to cut s up  into three pieces  um  now  if you're appreciating  um what's going on inside the machine  you will see  why  m will also accept the string x y y  z  because  every time you know once you're at q j  you know if you go around once you come  back to q j and then if you go again  you'll come back to q j and as many  times as you keep seeing that y you're  just going to keep coming back to q j  so  it doesn't matter how many  y's you have you're going to still if  you follow it by z which is what you'll  do you'll end up accepting the string  um  and that's really the proof um i mean  you have to do a little bit more um  uh here just to understand i i should  have mentioned why i want to forbid y  being the empty string because if it was  the empty string it's not interesting it  doesn't change uh  um you know repeating it doesn't  actually change anything so i have to  make sure it's not empty but anyway  that's kind of a detail here  uh if you look at the string x y y z  that's still going to be accepted  okay so that's the proof of the pumping  lemma  all right uh so let's have a little  check-in uh related to that uh this is  not gonna be again not super hard but uh  um  more just a curiosity uh  uh  so the pumping alignment depends on the  fact that if m has p states and it runs  for more than p steps then it's going to  enter some state twice  so you may have seen that before it  actually has a name  um which some of you may have seen um  so let's see how to just get a poll here  and  i hope not too many of you are gonna  pick c i said some of you are oh well  uh yes  i think this one most of you are  you've seen this before  this is um  i think you pretty much all got it um  this is what's known as the pigeonhole  principle  uh so  you know here uh sharing the results uh  obviously i was having a little fun with  this and sure some of you are having fun  back at me that's okay  um  okay so let's continue on um let's see  how to use the pumping lemma  to  prove the language is not regular um so  i put the pumping limb up here just uh  so you can remember the statement of it  um  uh so let's take the language d which is  the language  0 to the k1 to the k  for any k so that's  some number of zeros followed by an  equal number of ones  we're going to prove that language is  not regular by using the pumping lemma  okay and this is going to be just an  iron-clad  proof it's not going to say well i  couldn't think of how to find you know i  you know i couldn't think of how to find  a finite automaton this is going to be  you know this is going to really uh be a  proof  okay so we want to show that d is not  regular  uh  and we're going to give uh these things  always go as a proof by contradiction so  proof by contradiction hopefully as a  reminder to you the way that works is  you're going to assume the opposite of  what you're trying to prove  and then  uh from that something crazy is going to  happen something you know is obviously  false or wrong  and so therefore your assumption which  is the opposite of what you were trying  to prove had to be wrong and so  therefore the thing you're trying to  prove has to be right  um that's the essence of what's called  proof by contradiction  so first of all we're going to assume to  get our contradiction that is regular  um  and which is what we're trying to show  is not the case  now if the is regular then we can apply  the pumping lamp  um up above here uh which  gives us that pumping length p  which says that any string longer than p  can be pumped and you stay in the  language that's what the pumping limit  tells you  so let's pick the string s  uh which is the string zero to the p one  to the p here's sort of a picture of s  off on the side here so a bunch of zeros  followed by an equal number of ones  and that string is in d  because d is  strings of that form  and it's longer than p  obviously it's a blank 2p  so the pumping limit tells us there's a  way to cut it up  um satisfying those three conditions  so how in the world could we  possibly cut s s up well remember the  three conditions and especially  condition three is going to come in  handy here  say that you can cut s up into three  pieces x y and z  where the first two pieces lie in the  first  uh  p  uh symbols of s  um  you know at most  p long  so x and y together are not very big  they don't extend beyond the first half  of x  and first half of s and in particular  they're all zeros  x and y are going to be all zeros z is  going to perhaps have some zeros and  we'll have the rest of the ones we'll  have the ones  um now um  uh  the pumping limit says if you cut it up  that way you can repeat why as many  times as you like and you stay in the  language but that's obviously false  because if you repeat y which is now has  only zeros you're going to have too many  zeros  and so the resulting string is no longer  going to be of the form 0 to the k 1 to  the k it's going to be  lots of zeros followed by not so many  ones that's not in the language and that  violates what the pumping limit tells  you is supposed to happen  and that's a contradiction  so therefore our assumption that d is  regular is false  and so we conclude that d is not regular  so that's a fairly simple one  i thought i would do another couple of  examples because you have this on your  homework and i thought it might be  helpful so here's the second one  slightly harder but not too much  let's take the language f which is  looks like this strings ww  um these are strings that uh two copies  of the same string  um  for any string uh that might be in sigma  star so for any string at all i'm going  to have two copies of that string and so  f is those strings can which can be  which are just you know two copies of  the same string  uh  okay we're going to show that f is not  regular these things always go the same  way it's the same pattern you prove by  contradiction so you assume for a  contradiction that oh d that's bad  uh  that was copied from my other slide  that's wrong let's see if i can actually  make this work here  good  assume for a contradiction that f is  regular  the pumping limit gives f is above and  so now we need to choose a string s  that's in f  okay to do the pumping and show that  the pumping lemma is going to fail  um you know it's you're going to pump  and you're going to get something which  is not in language which is uh  you know shows that the pump is  something has gone wrong but which s to  choose and and sometimes that's where  the creativity in applying the pumping  lemma  comes in  because you have to figure out which is  the right string you're going to pump on  um so you know you might try the string  well  0 to the p 0 to the p that's certainly  in f  it's two copies of the same string  here it is i've written  you know uh  um  lots of zeros followed by the same  number of zeros  the problem is if you use that string  um  [Music]  it actually  uh is a string that you can pump you can  break that string up into three pieces  and then if you let  uh y be the string zero zero that you  have to be a little careful just the  string just zero it doesn't work because  there's an evenness oddness phenomenon  going here so you might want to just  think about that but if you let this y  be the string 0 0  then if you have the string x  y  x any number of y's it's still just  going to be a bunch of zeros and you're  going to be able to see that that string  is still in the language so you haven't  learned anything  if the pumping lemon works  and and you're  satisfying the pumpkin you haven't you  haven't learned anything  so  what you need to find is some other  string  so that was a bad choice for s  find a different string so here's a  different choice 0 to the p1 0 to the p1  so that's two copies of the same string  and you're going to show it can't be  we're going to show it can't be pumped  so here's a picture of that string here  so 0 is followed by 1 0's followed by 1.  and now it's very similar to the first  argument  if you cut it into three pieces in such  a way that it satisfies the conditions  the first two pieces are going to be  residing only among the zeros and so  therefore when you repeat  a y um  you're no longer going to have two  copies of the same string um and so  won't be in the language so therefore  you've got a contradiction and f is not  regular so you have to i you have to  play with the pumping lemma a little bit  if you haven't seen that before it's  going to be  you know it takes a little getting used  to but you have a few homework questions  that need to be solved using the pumping  level all right so now um  let's look at uh  lastly there is another method that can  come in which is combining closure  properties with the pumping lemma  so closure properties sometimes help you  so let's look at the language b which is  actually we saw earlier in the lecture  where we have an equal number of zeros  and ones  now we could prove that directly using  the pumping lemma as not being regular  but it's actually even easier  um  uh what we're going to prove  uh that it  we're going to prove that it's not  regular in a different way first we're  going to assume for contradiction as we  often do that it is regular um  and now we're going to use something  we're going to use some other knowledge  we're not going to use the pumping llama  here um because we're going to take  advantage of an earlier case where we  use the pumping level  and so um  now we know that the string the language  0 star 1 star is a regular language  because it's described by a regular  expression if you take the  b  which is the equal numbers of zeros and  ones  and you intersect it with zero star one  star  that's going to be a regular language if  b was regular  using closure under intersection  but this language b intersect zero star  one star  is the language  of  equal numbers of zeros and ones where  the zeros come first  and that's the language d that we show  two slides back  that we already know can't be regular  so that intersection cannot be regular  and so it violates the closure property  um  and again we get a contradiction  uh so  um that's a different way of  sometimes making a shortcut  to prove a language is not regular  okay  so we have in our last uh ten minutes or  so we're going to shift gears totally in  an entirely different way and consider a  new model of computation uh which is  more powerful that can actually do  things that we can't do with a with  finite automata and these are called  context-free grammars so this is really  just a kind of an introduction  we're going to spend uh all of next  lecture uh looking at context-free  grammars um and their associated  languages uh but let's just to kind of  get us  get a preview  so a context-free grammar looks like  this you have a bunch of these  um  uh  um what we call substitution rules or  rules sometimes  would just look like a symbol arrow a  string of symbols  all right  that's what a context-free grammar looks  like at a high level  let's define some terms um  so a rule as i just described is uh  going to be look it's going to be a  symbol which we're going to call a  variable  um and that's going to have an arrow to  a string of other possibly other  variables and  symbols called terminals  um  so a variable is a symbol that appears  on the left hand side of a rule  anything that appears on the left hand  side is going to be considered to be a  very ver a variable um  okay  so s and r are both variables  um  now  other symbols that appear in the grammar  which don't appear in the in in the  left-hand side  those  are going to be called terminals  so here 0 and 1 are terminals  now you may think that empty string  should also be a terminal but that's not  a symbol an empty string is a string  it's just a string of length zero so i'm  not considering empty string to be a  terminal  so  and then there's going to be a special  variable which is going to be considered  the starting variable just like we had a  starting state and that's typically  going to be written as the top left  symbol so this symbol s here is going to  be the starting symbol  and grammars can be used to  uh define languages  and to gen well to generate strings and  to define languages so first of all  let's see how  a grammar using this as an illustration  can generate strings um  actually just to emphasize this uh these  terminology here in this particular  example we had three rules  uh the two variables were r and s the  two terminals were zero and one  and the start variable was this top  left-hand symbol as i mentioned the s  okay  so grammars generate strings the way  they do is  you follow a certain procedure which is  really pretty simple  you  write down first of all the starts  variable and i'll do an example in a  second  you write down the start variable  and then you take a look what you've  written down  and if it has any variables in it you  can  apply  one of the corresponding right hand  sides of a rule  um  to as a substitution for that variable  and so like for example if you have an s  in the thing you've written down you can  substitute for that s a zero s one  or you can substitute for that s and r  or if you have an r you can substitute  for that's an empty string  so you're just going to keep on doing  that substitutions over and over again  until there are no variables left so  there's nothing left to substitute  only terminals remain  at that point you have generated a  string in the language  okay so the language then is the  collection of all generated strings  okay let's do an example here's an  example of g1 generating some string so  as i mentioned first of all you're going  to write down the start variable  and i'm just going to illustrate this in  sort of two parallel tracks here  on the left side i'm going to show you  the tree of substitutions and on the  right side i'm going to show you the  resulting string that you get by  applying those substitutions  okay  so over here i'm going to substitute for  s the string 0 s1 so on the right hand  side i just have 0 s1 because that's  what i substituted for s but you'll see  it's not going to it's going to look a  little different in a second  here i'm going to again i still have a  variable so i'm going to substitute for  s 0 s 1.  now i have the string resulting string 0  0 s 1 1 because i've substituted 0 s 1  for the previous s but the 0 and 1 stick  around from before they don't go  anywhere so i have at this point 0 0 s 1  1. now  uh i'm going to take a different choice  i'm going to substitute for s you know i  could have gone either way this sort of  something like almost like  non-determinism here because you have a  choice  uh i'm going to substitute for s um  instead of 0 s1 i'm going to substitute  r because that's also legitimate in  terms of the rules  and so now i'm going to have  0 0 r  1 1.  and now r has there's no choices here r  can only be substituted for by an empty  string  so i get to r becomes just empty string  and in terms of the string generated  empty string doesn't add anything it  just really is  nothing it's a nothing so i get the  string 0 0 1 1 and this is a string just  of terminal symbols  and so that is a string in the language  of  the grammar g1  okay  if you think about it g1's language is  that language that we saw before uh  which i think we called  d  um  zero to the k one to the k for k greater  than or equal to zero so this is an  example of the language that a  context-free grammar can do but i find  that automaton cannot do  okay  so that is our little introduction to  con oops there's one more check in here  um  oh yeah so i'm asking you to actually  look at  let me get myself a look out of this  picture  um  so you  don't see me blocking things  and we will do one last check-in  make sure you're staying around for the  whole thing  now you can now there could be several  of these strings that are in the  language you have to click them all  all the ones that you have found that  are in the language of this grammar that  can be generated by grammar g2  you have to click those i'll give you a  little bit more time on this one um  to see which ones uh g2 can generate  um  i'll give you a hint it's more than one  but not all  uh  so i see you're making some progress  here  um  interesting  so please uh we're gonna wrap this up  very quickly  uh you can't call us somebody's telling  me you can't unclick thank you good to  know  um  [Music]  okay so still things are coming in here  so  uh  let's not we're we're running toward the  end of the hour here i don't want to go  over so i'm going to end it in five  seconds  uh click away and don't forget  uh  we're not uh going to charge you if you  get it wrong um  sharing results  uh  i don't know why it has an orange one  there because  there are several correct answers here  um  so it's a b and d are correct  um you can get any of any of those um  it's really sort of two copies of the  language we had before  uh next to one another uh  and so  um  the only thing you cannot get is  one zero one zero  um so i encourage you to think about  that  and i will uh  uh  come to our last side of today um which  is just a quick review um  i can put myself back  so we show how to convert dfas to  regular expressions  and the summary is that dfas nfas  gnfas even ray and regular expressions  are all equivalent um in the class of  languages they can describe  uh  the second thing we did was a method for  proving languages not regular by using  the pumping lemma or closure properties  and lastly we introduced context-free  grammars and we're going to see more  about those on thursday  so with that i think we're out of time  and  other thank you for the  notes of appreciation and um  i will um  i think we're gonna  end here um and uh  see you  um on thursday if not before
 

3
00:00:26,160 --> 00:00:27,990
okay folks  um  here we are again  welcome back  for another episode of theory of  computation this is lecture number three  um  i  am fir i'm going to review how what  we've been doing um we've been looking  at finite automata  and regular languages those are the  languages that the fine automata can  recognize  and we  talked about  non-determinism so we had  non-deterministic finite automata and  deterministic finite automata we showed  that they're equivalent  we looked at the closure properties over  the regular operations union  concatenation and star and showed that  the  regular language is really the class of  regular languages is closed under those  regular operations  and we used the constructions that we  developed in the proof of those closure  properties to show that the  we can give away to convert  regular expressions to finite automata  so that is uh was  a  part way toward our goal  of showing that these regular  expressions and finite automata are  equivalent with respect to the class of  languages they describe namely the  regular languages so regular expressions  of finite autonomic are interchangeable  from the perspective of what kinds of  languages you can do with them  so we're going to finish that off today  so let's take a look at what  our next  topics we're going to be covering  we're going to  reverse  the  construction that we gave last time  which allowed us to convert regular  expressions to finite automata now we're  going to go backwards we're going to  show how to convert finite automata back  to regular expressions  and um that  those two  constructions together uh show us that  the regular expressions finite automata  can be inter interconverted from one  another and they're therefore equivalent  with respect to the kinds of things they  they can do in language  recognition or generation  then we're going to prove that uh we're  going to look at how you prove certain  languages are not regular they're beyond  the capabilities of fine art automata  and finally at the end we're going to  introduce a new model of computation  which is more powerful  than the finite automata and regular  expressions namely the context-free  grammars  those can do  other kinds of languages that the  simpler find at a time but the regular  expressions models can't do um  and i i would also just like to note  that  a lot of what we're doing is a warm up  toward the more powerful models of  computation that we're going to be  looking at later um well in a week or so  which are  more kind of general purpose  computation  but along the way introducing these  models of finite automata in  context-free languages  is  interesting and helpful because many of  those um a number of those models turn  out to be useful in a number of  applications um whether it's from  you know pro linguistics to  uh programming languages um and a  variety of different uh  parts of computer science and other  fields as well use those notions so  they're they're useful notions um  and beyond just uh  in this course um  okay so  um  i just wanted  a couple of administrative things to  touch on uh we are going to have  additional check-ins today um as i  uh mentioned to you we're gonna start  counting participation not correctness  of just participation in the live  check-ins  so um with that let us  move on to today's material um  as i mentioned we're going to be showing  how to convert  finite automata to regular expressions  um and that's going to complete our  equivalence of finite automata and  regular expressions so just to recap  what we did last time  we showed that if you have a regular  expression  um  uh  and it describes some language then that  language is regular  uh so in other words um we have a way of  we gave a way of converting regular  expressions to finite automata as kind  of shown in this diagram  that's what we did last time  now we're going to go the other way um  we're going to show how to convert oh  and just a reminder in case you're just  getting yourself  your memory size your memory uh to work  um maybe it'll help you just to remember  that we actually did an example of that  conversion we looked at this um regular  expression a union a b star and we  actually worked through the process of  converting that oops i need to make  myself smaller so you can see all that  we went through the process of um  converting a union a b star as an  example of that um  of uh  minimus  okay  uh  well  um  we went through the process of actually  doing that conversion and now we're  going to show how to do it the other way  around  all right so  um  so we're going to invert that  and go backwards the other way  um so today's theorem is to show that if  a is regular namely its  uh um  the language of some finite automaton  um then um  uh  you can convert it to a regular  expression which will describe that same  language so basically we're going to  give a conversion from finite automata  to regular expressions okay um  but before we do that we're going to  have to introduce a new concept um so  we're not going to be able to dive right  into that conversion we're going to have  to do introduce a new model first which  is going to facilitate that conversion  and that new model is called it's in yet  another kind of finite automaton called  a generalized  non-deterministic finite automaton or a  generalized nfa or just simply a gnfa  okay so this is yet another variant of  the finite automaton model um  and  conceptually it's very sim simple it's  similar to the nfas i'll give you here's  a picture of a  gnfa  named  g1 very similar to the nfas but if you  look at it for a second you'll see that  the  transitions have more complicated labels  for the anaphase who are only allowing  just single symbols or the empty string  to appear on the labels now i'm actually  allowing you to put full regular  expressions on the labels  for the automaton  now we have to understand how  a gnfa process as  its input and the way it works is  um not complicated to understand  um  when you're getting an input string  feeding when the when a gnfa is  processing an input string it starts at  the start state just like you would  imagine  but now to go along a transition instead  of reading just a single symbol or the  empty string as a as in the case for the  nondeterministic machine  um  it actually gets to read a whole string  at one step kind of at one byte  it can read an entire string um and go  along that transition um  uh  arrow provided that  trunk of the input that it read  is in the regular expression  that that  uh  transition uh  has as its label  so for example  um  this you can go from q1 to q2 in one  step in this gnfa by reading the by  reading aabb off the input  so it reads all those four symbols all  at once  it just swoops them up and then moves  from q1 to q2  in one step  okay and then when it's in q2  it can read aab  and move to q3 and q3 happens there's  nowhere to go um so this is going to be  a non-deterministic machine there might  be several different ways of processing  the input and if any one of them gets to  an accepting state at the end of the  input  we say the gnfa accepts  so it's similar to non-deterministic to  nfa's in in the way the acceptance  criterion works  um so you know you could do an example  but hopefully the concept of how this  works is reasonably  you know you can at least buy it um that  it processes  um the input in  chunks at a time and those chunks have  to be described by the  uh regular expressions on the transition  our arrows as it moves along those  transitions  okay  so um  what we're going to do  now  is to convert  not  dfas to regular expressions we're going  to convert gnfas to regular expression  that's even harder  because gnfas are allow you to do all  sorts of other things besides just  ordinary dfas  so that's a harder job why am i making  my life harder well you'll see in a  minute  that it's going to actually turn out to  be helpful to be working with a more  powerful model um  in the way this construction is going to  work  okay  now before i dive in and do the  construction from gnfas to regular  expressions i'm going to make a  simplifying assumption about the g  anaphase  i'm going to put them in a special form  that's going to make it easier to do the  conversion  and that simpler form is  first of all i'm going to assume that  gnfa has just a single accepting state  and that accepting state is not allowed  to be the start state  okay so it has to have just a single  accepting state i've already violated  that um convenient assumption in this  gnfa because i have here two  uh accepting states that's not what i  want i want to have just one  well the thing is it's easy to obtain  just one just to modify the machine so  that i have just one by  adding a new accepting state which is  branch two from the former accepting  states by empty transition so i can  always jump from q2 to q4 at any time  without even reading any input just  going along this empty transition  and then i declassify the former  accepting states as accepting  and now i have here just a single  accepting state and  because it's going to be a new state  that i added it won't be the start state  and i have  accomplished that one aspect of my  assumption about the form of the gnfa  but there's another thing that i want to  do too  i want to assume  um as you'll see which is going to be  convenient in my uh  construction that we will have  transition arrows going from every state  to every other state in fact i want  transition i was going from every state  even back to themselves  um  i want the there to be all of all  possible transition arrows should be  present  um  uh with with two exceptions  uh for for the start state there should  be only transition arrows exiting the  start state  and for the accepting state there's just  one now there should be only transition  arrows coming in to the start state  so it's kind of what you would imagine  as being reasonable um for the other  states which are not accepting or or um  starting  there should be  transition arrows leaving and coming  from everywhere else but for the start  states just leaving and from the except  state just coming in  and you could easily modify the machine  to achieve that um let's just see how to  do that in one example so from notice  that from q3 to q2 there is no  transition right now and that's not good  that's not what i want i want that to be  a transition from q3 to q2 well i'll  just add that transition in  but i'm going to label it with the empty  language regular expression  so that means yeah the transition is  there but you never can take it  so it doesn't change  the  language that the machine is going to be  recognizing but it fulfills my um  uh  my assumption my convenient assumption  that we have all of these transition  arrows being present in the machine  okay so uh  anyway i hope you uh will buy it it's  not gonna be re if you don't quite get  this don't worry it's not totally  critical that you're following or these  little these little adjustments and  modifications to the gnf8 but it will be  helpful to understand what gnf  themselves how they work  so as i mentioned we can easily modify  gnfa to have the special form that we're  assuming here  all right so now we're going to jump in  and start doing the conversion so we're  going to have a lemma which is like a a  theorem that really is just a local  interest here it's not a  general interest theorem it's going to  be relevant just to gnfa which it really  just defined to help us do this  conversion they really don't have any  other independent value  so every you want to show that every g n  of a has an equivalent regular  expression r  that's really my goal um  and the way we're going to prove that  is by induction  it's going to be by induction on the  number of states of the gnfa  now  you really should be familiar with  induction as one of the uh expectations  for being in this course but in case  you're a little shaky on it don't worry  i'm gonna unpack it um as a procedure  it's really just recursion you know  induction is just a and a proof that  uses induction is really just a proof  that calls itself it's just a proof that  it's a recursive proof that's all it is  so if you're comfortable with the  recursion you'll be comfortable with  induction um but anyway i'm going to  describe this as a procedure so if  you're a little shaky on induction don't  worry  um  so the basis is so first i'm going to  handle the case where the gnfa has just  two states  okay um  now remember i'm assuming now my gnfas  are in the special form  so you can't even have a gnfa with one  state because it has to have a start  state and it has to have an accept state  and they have to not be the same so the  smallest possible gnfa to worry about is  a two-state gnfa  okay now if we have a if we happen to  have a two-state gnfa it turns out to be  very easy to find the equivalent regular  expression why  because  that tuesday gnfa can only look like  this  it can have a start state can have an  accept state  and it can only have a transition going  from the start to the accept because no  other transitions are  allowed um it only has outgoing from the  start only incoming from the uh  to the except and so there's only one  transition and it has a label with a  regular expression r  so what do you think the equivalent  regular expression is for this g nfa  it's just simply the one that's labeling  that transition because that tells us  when i can go from the start to the  accept and there's nothing else the  machine can do it just makes one step  which is to accept its input if it's  described by that regular expression so  therefore the equivalent regular  expression that we're looking for is  simply label on that single transition  okay so two state g nfas are easy  um but what if what happens if you have  more states then you're gonna actually  have to do some work  um  so  we call that the induction step that's  when we have more than two states  and what that the way the induction  works is we're going to assume we  already know how to do it for k minus 1  states  and we're going to use that knowledge to  show how to do it for k-states  so in other words um we already know how  to do it for two states  i'm going to use that fact to show how  to do it for three states  and then use the fact that i can do it  for three states to show how to do it  for four states and so on and so on  all right  and the idea for how to do that is  actually uh  pretty  uh easy to to grasp  um what we're going to do is if we have  a k-state gnfa that we want to convert  we're going to con we're going to change  that k state g n of a to a k minus 1  state g n of a  and then use our assumption that we  already know how to do the k minus 1  state g nfa  all right  so um  in terms of a picture i'm going to take  a k-state to prove that i can always  convert k-state g-n-phase uh to regular  expressions  i'm going to show how to convert the  k-state um one into an equivalent k  minus one state g of a and then if you  just like to think of it this  procedurally the k minus one will gets  converted to a k minus two gets  converted to a k minus three and so on  and so on until i get down to two  which then i know how to do directly  okay so the whole name of the game here  is figuring out how to convert a  gnfa that has k states  into another one that has one fewer  state that does the same language  okay so you have to  hold that in your head i mean i wish i  had more blackboard space here but you  know it's very limited here so you have  to remember what would what we're going  to be doing on the next slide  because that's going to finish the job  for us as long as i can show in general  how to convert a k-state gnfa to a gnfa  that is one fewer state but it still  does the same language  i'm good  because then i can keep iterating that  till i get down to two  all right  so here is um  this is the  the guts of the argument um so i have my  k-state machine here's my my start state  here's my accept state  um here's my k minus one state that  machine that i'm going to be uh building  for you it's actually going to be  be look almost exactly the same i'm just  going to remove one state  um  from the from the from the bigger  machine  so i'm going to pick any state which is  not the  start state or the accept state um here  it is pictured here  i mean all of the states of the k-state  machine are going to appear in the k-1  state machine  except for one state that i'm going to  rip out  okay  that's the state x it's now here as a  ghost  it's been removed  um  uh it's not there anymore okay but i'm  just helping you to remember that used  to be there  by showing his shadow  but it's a  uh i have taken  my original machine that had k-states  um  and basically just ripped out of state  um and now i've  you know one fewer state  so the good news  is that i now have a machine with k  minus one states  that's what i want  but the bad news is that it doesn't do  the same language anymore  it's i i broke the machine by rip just  if you're just going to rip out a state  you know who knows what the machine is  going to do it's going to be  probably not the same as what the  original machine did  so what i need to do  then  is repair the damage  i've got to fix the damage that i caused  by removing  x okay um  and  whatever  role  x was playing  in the original machine  i've got to make sure  that  the the new machine that i have which  doesn't have x anymore can still do the  same things  um that the original machine did  um and so the way i'm going to do that  is look at all of the paths that could  go through x and make sure that they're  still present even though i don't have x  anymore  and the way i'm going to do that is i'm  going to take  um  [Music]  consider  a part of a path that might use x  so it starts  let's pick two states q i and two j  in the uh machine that had k states  let me just here  i know this is uh  okay um  we have if we have uh we'll pick two  states q i and q j  um in in in the original machine now qi  might  have the possibility of going to state x  and then x might have a self loop  and then it might go to 2j  the new machine doesn't have any x  anymore  the way i'm going to fix that  is by  replacing the label that goes directly  from i to j  with a new label  that  adds in all of the things i lost  when i removed x  okay that's  that's the whole idea here so here is q  i to q j but there's no x anymore  how could i get  from q i to q j  um  um you know  you know what what were the  inputs  that could have brought us from qi to qj  via x  well they would have been an input  that read a string described by r1  i might have self-looped at x a few  times  so i might have read several strings  that are described by r2  and then i would have read a string that  was described by r3 and now i'm at qj  okay  so  uh the new label  that i'm going to place over here is  going to be  uh the strings that i get from reading  are one you know reading a a  a  a string that described by r1  then multiple copies of a stretch you  know  multiple strings that are possibly  describing r2 which is the same as r2  star  or and then multiples and then a string  that would be described by r3  so that is a new addition to the  transition that takes me from q i to q j  of course i need to include the things  that would have taken me from q i to q j  in the first place  so i'm also unioning in r4 what was the  direct route from qy to qj that did not  uh transit through x  okay  so by making that  uh  uh  you know  new  um regular expression  on the q i to q j transition  i have compensated for the loss of x  for paths that go from q i to x  and then  out to q j now what i  need to do  is to  do that same thing for every pair qi and  qj  that are in the original machine  and so if i do that for every possible  pair  i'll be modifying all of the transitions  in the new machine  in a way  that  [Music]  compensates for the loss of x and now  the new machine has been repaired from  the damage that i caused by removing x  and it does the same language  it's kind of thing you need to think a  little bit about i understand um but at  least hopefully uh the uh the spirit  of what i just described to you uh comes  through that we're going to convert this  case machine with k states to one with  uh k minus one states by removing a  state and repairing the damage  and now it does the same language and  then i can remove another state and do  the same thing over and over again until  i get down to two states  okay so that's the um  idea and that really completes uh the  proof  that shows  that i can  uh  convert every gnfa  to a regular expression  okay um  and that really is uh the end of the  story for this um  and thus  i claim that dfas now and regular  expressions are equivalent  so let me get going to give you a little  check in here on this  uh  um  really just to see  if high level if you're following what's  going on  all right  uh so just take a look so we just showed  how to convert g n of a to regular  expression but we really wanted to  convert dfas to regular expressions so  how do we go from g n f converting g n  of a is to converting dfas because  they're not the same obviously right um  so how do we finish that  so there are three choices here  first we have to try to convert dfa to g  interface maybe or sure to convert gnfa  to df dfas or maybe we're already done  so maybe i better launch that poll while  you're while you're reading that  um  and there you  go hopefully you can  um all right  why don't i end this it's a little  worrying worrisome because uh i would  say we have a plurality who got the  right answer but not a majority uh  so uh let us share the results um i  think  so uh i sense not all of you are with me  um  but uh um you're gonna have to uh  uh  tr either that or you're  you know you're uh playing you're  reading your email while we're uh  talking i'm not sure but um  whatever it is um  you  need to think a little bit about what's  going on here because  um  what  you know the reason why we are done  is because dfas are a kind of g-n-phase  they're just they have a very simple  kind of regular expression on each  transition  um they  just have the regular expression which  is just a single symbol  so all dfas are automatically gnaphase  so if i can convert g anaphase i can  certainly convert dfas because dnf's  include the dfas i'm done it really was  number c  was the correct answer  okay  it's a good thing we're not  counting  uh  correctness here so participation is  good enough but i do think you need to  think about what's going on and making  sure that you're you know you're you're  you're following along so anyway that's  a uh  um  you know we'll carry on here but um  makes me a little concerned um  okay uh so um let us now move on um so  we're going to talk a little bit about  non-regular languages  um  so somebody's asking don't we have to  still make the dfas into the special  type yes we do we have to make them to  the special type but we already showed  how to make g interface into the special  type and dfa that that is going to apply  to dfas as well um  you know they'll become  gnfas you know you can add the extra  starts  at a new start state and at a new uh  accept state  add in all the transitions with which  you didn't have before with the empty  language  label  and you'll have a gnfa  from um a dfa but that applies to  gnaphase as a in general so it's nothing  special about dfas there anyway  uh i think you need to chew on that  hopefully uh you know you're you'll be  uh following going forward anyway let us  look now at non-proving non-regularity  so we're finished with our goal  of showing that regular languages that  the regular languages can either come  from  dfas or from regular expressions those  are the same in terms of from the  perspective of our course they're  interchangeable  okay so now uh  as we mentioned there are going to be  some languages which are not regular  which can't be done by dfas uh their  actual dfas are actually pretty weak as  a computational model and so there's all  sorts of very simple things that they  cannot do um  uh those there are some fairly  complicated things that they can do  surprisingly enough  but anyway um  there are some simple things they can't  do and so we have to develop a method  for showing that a language is not  regular um and that's going to be useful  for your homework um and in general for  just understanding the uh the power of  dfas  so how do we show our language is not  regular so  remember if you want to show a language  is regular basically what you need to do  is give a dfa  or you know you can use the closure  properties that's another way of showing  a language is regular but underneath  that it's basically constructing dfas  all right um to show a language is not  regular you have to give a proof  uh generally not a construction it's a  proof that there is no uh dfa or that  whatever uh that it's just going to be  impossible to make a dfa um  and we have to develop a method what  what is that proof method  um now  there is a tempting um  you know i've taught this course many  times and there's a kind of attempting  approach  uh that many people have um it's not  only going to apply for finite automata  but for other things too and believe me  it's not only  people in this class it's for people uh  out there in the um who are trying to  think about computation in general  which is to say  well you know  um  uh  you know i have some language of trying  to figure out if it's regular or not and  so i thought really hard how to make a  dfa and i couldn't find one therefore  it's not regular  that's that's not that's not a proof  just because you couldn't find a dfa  doesn't mean there is no dfa  you need to prove  that the language is not regular using  some method  um so i'm going to give you an example  where that kind of approach can lead you  wrong  and that is i'll give two examples  of  languages where  you might  try to prove they're regular or not and  you could be uh  in trouble if you just follow uh that  kind of informal approach  so if you take the language b  where these are string well let's assume  our alphabet is zeros and ones uh  b is the language of all strings that  have an equal number of zeros and ones  um  uh so you wanna know you know if i have  a thousand zeros i need to have a  thousand ones so basically the way you  test that you'd have to count up the  number of zeros count up the number of  ones  and see if those two counts are the same  and that's going to be really tough to  make a dfa do  um because it's you know how you're  going to remember such you know that  really big number of zeros that you know  the dfa might have 50 states but you  might need to count up to a hundred or a  million to figure out to count up how  many um  zeros you've seen  and it seems really hard to be able to  do that kind of account when you only  have 50 states uh some so whatever  number of states you have it's you're  not it seems hard to count uh when you  have a lim when you have a finite  automaton so the intuition is it's not  regular because a finite atomic done  can't count um which  in this case  you can convert that intuition into a  real proof i would say it's not a real  proof yet  but it can be made into a real proof  um  but compare that case with another  language which i'll call c  which instead of uh looking at its input  to see whether it has an equal number of  zeros and ones i'm going to look at the  input and look at the substrings of zero  ones and one zeros those two substrings  and count the number of occurrences of  zero one as a substring and the number  of occurrences of one zero as a  substring  okay just to make sure you're  understanding let's look at some  examples uh two examples  so the string zero one zero one  is not going to be in c  because if you count up the number of  zero ones and the number of one zeros  not the same so i'm even going to help  you here uh if you can see that the  number of zero ones is two  but there's uh  there's only a single occurrence of one  zero  okay so those are those two  counts are different  and so that's why this input string is  not in c  compare that with the string  zero one one zero  now if you count up the number of zero  one and one zero sub strings you're  going to get the same value because here  we have a single zero one and a single  one zero  and so now the two counts of those  number of substrings are the same  and so that's why you're in c  okay  now my question is  is c a regular language  well it looks like it shouldn't be  regular for the same reason that b is in  regular because you have to count up two  quantities and and compare them  um  so um  uh  now  um  so  if we  um  you know so that's our intuition that  you just can't do it for the with a  finite automaton because you have to do  the same kind of counting that you would  have had to do for language b  but here  you'll be you would be wrong  because c in fact is regular  um  uh  it has a much  simpler description  than the one i gave over here uh at the  beginning there's a the there's the very  same language c can be described in a  much much simpler way i'm not going to  tell you what it is you can mull that  over you can try some examples uh to  figure it out but it has a much simpler  description it's not totally trivial  description i mean there is some content  there but there is um you know it is the  kind of thing that a finite automaton  can do it wouldn't do the counting this  way um  so the moral is the punch line is that  sometimes the intuition works but it can  also be wrong  um and so the moral of the stories you  need to give a proof when you're when  you're doing things like that  okay  so what we're going to do next in the  second half of the lecture  is to give a method for proving  languages are not regular and again  you're going to need to use that on your  homework so i hope you get it um but uh  first of all oh did i  never stop sharing that poll forgive me  um  and so  uh  um  and so with that i think we'll take our  little requested break  uh  and um for five minutes  and uh  we'll be back in five minutes  um  so  break time  alrighty  we are done here  and um  proving languages not regular  okay  um  [Music]  the way we're going to prove languages  are not regular is by introducing um a  method called the pumping lemma  um  and the overarching plan at the pumping  lemma without getting into the  specifics of it  is to say show that  um  um that lemma says  all  regular languages have a certain  property  which we will describe  and so  to show a language is not regular  you simply show the language doesn't  have that property  um because  all regular languages have to have that  property and so by showing a language  fails to have the property it could not  be regular  okay that's that's the plan  um  now uh  the property itself  is a little complicated um to describe  um but not too bad i'll try to unpack it  for you  but first let's look at the statement of  dilemma  um  which says that  whenever you have a regular language  let's call it a so for every regular  language a  there's always a special value  called the pump  a number uh p we'll call it called the  pumping length  okay it's a special number and  uh  uh it's um  and  that  uh  uh  that length  um  uh  tells you  that  whenever a string is in that language  and it's longer than that length  then um  something special happens  you can take that string and you can  modify it and you still stay in the  language so anything that's longer than  that special length can be modified in a  certain way and you still say in the  language so let's look at the the actual  um statement of the lemma  so  there is a number p  such that if s is a string in the  language and it's longer than p or at  least of length p  then you can take s and you can cut it  up into three pieces x y and z  so they're just breaking s into three  pieces  where  um  you can take that middle piece  repeat it as many times as you like  and you're still staying the language  because that's the  uh  what the pumping llama is saying and  there's a bunch of other conditions here  too but  the the spirit of the pumping lumber  says whenever you have a regular  language there's some cut off such that  all strings longer than that cut off  can be what we call pumped you can take  that string you can find a section  somewhere in the middle of that string  or somewhere you cut it up in three  piece pieces you take them  that center piece and you can repeat it  you can pump it up  um and  by repeating that string and repeating  that piece the string gets longer and  longer  but you still stay in the language um  that's the special property that all  regular languages have  so kind of in an informal way and we'll  do so i'll try to help you get the  feeling for this um formally it says  that  you know if you have a regular language  then every long string so as long as by  informing my informal way of saying  bigger than this value p every long  string in the language can be pumped  and this result still stays in the  language and by pumped means i can cut  the string into three pieces and repeat  that middle piece as many times as i  want that's what i mean by pumping a  string  um  [Music]  so uh  uh we'll do some examples uh in a second  um  but first we're going to un see how to  prove this and hopefully that will give  you some feeling  also for why it's true  so  uh and actually maybe before i actually  jump into the proof let me let's look at  these three conditions here just to  understand it a little bit more uh  uh thoroughly  uh so condition one kind of says what i  just uh was was telling you  um i can break s into three pieces x y z  such that if i take x  y to the i z  so that's repeating y as many times as i  want so here's y to the i kind of  defined if that's helpful to you it's  just y i copies of y so i can take x y  to the i z and i remain in in the  language for every value of i even i  equals zero which means we're just  removing y uh which is sometimes  actually a useful thing to do but you  know  let's not get ahead of ourselves  um you know so  if  um you know  you know i can cut s i can i'm  guaranteed to be able to cut s up into x  y z so that the string x y y y is still  on the language or x y y y y y it's  still in the language um that's going to  be guaranteed for every regular language  that's good that's that's a feature  that's going to be true  um and furthermore and this is going to  be turning out to be it's not really  kind of part of the core idea of the  pumping lamb but it actually turns out  to be very helpful in applying the  pumping lemma  you can always cut it up in such a way  that the first two pieces are not longer  than that value p  um so this  it restricts on the ways you can cut the  thing up and that actually turns out to  be very helpful  um but let's first just look at the  proof of this uh giving kind of a little  bit the high level picture  um  so  my job is to show if i have a have a  string in my language let's say  think of it as a long string really long  um so it's length is more than p but i  think intuitively it's just a very long  string um  and i'm going to feed that string into  the machine  and watch what happens  something special happens when i feed  the string and i look at how the machine  proceeds  on that string  um  because  s is  so long  that  as i wander around inside the machine i  end have to end up coming back to the  same place more than once  um it's like you know if you have a  small park and you go for a long walk  you're going to end up coming back to  wave or what you've already seen you  just can't keep on seeing new stuff when  you have a more small area of space to  explore  so  um  so we're guaranteed that m is going to  end up repeating some state when it's  reading s because s is so long  so in terms pictorially um if you  imagine here this wiggly line is kind of  describing the path that m follows when  it's reading s it ends up coming back to  that state q j more than once so it  comes back here cycles around comes back  again before it ends up accepting we  know what it ends up accepting because  we're assuming we have a string that's  in the language so we picked s in the  language so it has to be accepted by m  but the important thing is that it  repeats a state  now um  how does that tell me i can cut s up  into those three pieces  well i'm going to get those three pieces  here um first of all let's observe that  here is a process you know as processing  s here is the that  written right on top of the string that  state repetition occurring uh qj more  than once and now if i look inside the  machine the part of s that took me  to q j i'm going to call x  the part that took me from q j back to  itself is i'm going to call y and the  partner took qj  to the accept state i'm going to call z  and i'm going to mark those often in s  and that gives me the way to cut s up  into three pieces  um  now  if you're appreciating  um what's going on inside the machine  you will see  why  m will also accept the string x y y  z  because  every time you know once you're at q j  you know if you go around once you come  back to q j and then if you go again  you'll come back to q j and as many  times as you keep seeing that y you're  just going to keep coming back to q j  so  it doesn't matter how many  y's you have you're going to still if  you follow it by z which is what you'll  do you'll end up accepting the string  um  and that's really the proof um i mean  you have to do a little bit more um  uh here just to understand i i should  have mentioned why i want to forbid y  being the empty string because if it was  the empty string it's not interesting it  doesn't change uh  um you know repeating it doesn't  actually change anything so i have to  make sure it's not empty but anyway  that's kind of a detail here  uh if you look at the string x y y z  that's still going to be accepted  okay so that's the proof of the pumping  lemma  all right uh so let's have a little  check-in uh related to that uh this is  not gonna be again not super hard but uh  um  more just a curiosity uh  uh  so the pumping alignment depends on the  fact that if m has p states and it runs  for more than p steps then it's going to  enter some state twice  so you may have seen that before it  actually has a name  um which some of you may have seen um  so let's see how to just get a poll here  and  i hope not too many of you are gonna  pick c i said some of you are oh well  uh yes  i think this one most of you are  you've seen this before  this is um  i think you pretty much all got it um  this is what's known as the pigeonhole  principle  uh so  you know here uh sharing the results uh  obviously i was having a little fun with  this and sure some of you are having fun  back at me that's okay  um  okay so let's continue on um let's see  how to use the pumping lemma  to  prove the language is not regular um so  i put the pumping limb up here just uh  so you can remember the statement of it  um  uh so let's take the language d which is  the language  0 to the k1 to the k  for any k so that's  some number of zeros followed by an  equal number of ones  we're going to prove that language is  not regular by using the pumping lemma  okay and this is going to be just an  iron-clad  proof it's not going to say well i  couldn't think of how to find you know i  you know i couldn't think of how to find  a finite automaton this is going to be  you know this is going to really uh be a  proof  okay so we want to show that d is not  regular  uh  and we're going to give uh these things  always go as a proof by contradiction so  proof by contradiction hopefully as a  reminder to you the way that works is  you're going to assume the opposite of  what you're trying to prove  and then  uh from that something crazy is going to  happen something you know is obviously  false or wrong  and so therefore your assumption which  is the opposite of what you were trying  to prove had to be wrong and so  therefore the thing you're trying to  prove has to be right  um that's the essence of what's called  proof by contradiction  so first of all we're going to assume to  get our contradiction that is regular  um  and which is what we're trying to show  is not the case  now if the is regular then we can apply  the pumping lamp  um up above here uh which  gives us that pumping length p  which says that any string longer than p  can be pumped and you stay in the  language that's what the pumping limit  tells you  so let's pick the string s  uh which is the string zero to the p one  to the p here's sort of a picture of s  off on the side here so a bunch of zeros  followed by an equal number of ones  and that string is in d  because d is  strings of that form  and it's longer than p  obviously it's a blank 2p  so the pumping limit tells us there's a  way to cut it up  um satisfying those three conditions  so how in the world could we  possibly cut s s up well remember the  three conditions and especially  condition three is going to come in  handy here  say that you can cut s up into three  pieces x y and z  where the first two pieces lie in the  first  uh  p  uh symbols of s  um  you know at most  p long  so x and y together are not very big  they don't extend beyond the first half  of x  and first half of s and in particular  they're all zeros  x and y are going to be all zeros z is  going to perhaps have some zeros and  we'll have the rest of the ones we'll  have the ones  um now um  uh  the pumping limit says if you cut it up  that way you can repeat why as many  times as you like and you stay in the  language but that's obviously false  because if you repeat y which is now has  only zeros you're going to have too many  zeros  and so the resulting string is no longer  going to be of the form 0 to the k 1 to  the k it's going to be  lots of zeros followed by not so many  ones that's not in the language and that  violates what the pumping limit tells  you is supposed to happen  and that's a contradiction  so therefore our assumption that d is  regular is false  and so we conclude that d is not regular  so that's a fairly simple one  i thought i would do another couple of  examples because you have this on your  homework and i thought it might be  helpful so here's the second one  slightly harder but not too much  let's take the language f which is  looks like this strings ww  um these are strings that uh two copies  of the same string  um  for any string uh that might be in sigma  star so for any string at all i'm going  to have two copies of that string and so  f is those strings can which can be  which are just you know two copies of  the same string  uh  okay we're going to show that f is not  regular these things always go the same  way it's the same pattern you prove by  contradiction so you assume for a  contradiction that oh d that's bad  uh  that was copied from my other slide  that's wrong let's see if i can actually  make this work here  good  assume for a contradiction that f is  regular  the pumping limit gives f is above and  so now we need to choose a string s  that's in f  okay to do the pumping and show that  the pumping lemma is going to fail  um you know it's you're going to pump  and you're going to get something which  is not in language which is uh  you know shows that the pump is  something has gone wrong but which s to  choose and and sometimes that's where  the creativity in applying the pumping  lemma  comes in  because you have to figure out which is  the right string you're going to pump on  um so you know you might try the string  well  0 to the p 0 to the p that's certainly  in f  it's two copies of the same string  here it is i've written  you know uh  um  lots of zeros followed by the same  number of zeros  the problem is if you use that string  um  [Music]  it actually  uh is a string that you can pump you can  break that string up into three pieces  and then if you let  uh y be the string zero zero that you  have to be a little careful just the  string just zero it doesn't work because  there's an evenness oddness phenomenon  going here so you might want to just  think about that but if you let this y  be the string 0 0  then if you have the string x  y  x any number of y's it's still just  going to be a bunch of zeros and you're  going to be able to see that that string  is still in the language so you haven't  learned anything  if the pumping lemon works  and and you're  satisfying the pumpkin you haven't you  haven't learned anything  so  what you need to find is some other  string  so that was a bad choice for s  find a different string so here's a  different choice 0 to the p1 0 to the p1  so that's two copies of the same string  and you're going to show it can't be  we're going to show it can't be pumped  so here's a picture of that string here  so 0 is followed by 1 0's followed by 1.  and now it's very similar to the first  argument  if you cut it into three pieces in such  a way that it satisfies the conditions  the first two pieces are going to be  residing only among the zeros and so  therefore when you repeat  a y um  you're no longer going to have two  copies of the same string um and so  won't be in the language so therefore  you've got a contradiction and f is not  regular so you have to i you have to  play with the pumping lemma a little bit  if you haven't seen that before it's  going to be  you know it takes a little getting used  to but you have a few homework questions  that need to be solved using the pumping  level all right so now um  let's look at uh  lastly there is another method that can  come in which is combining closure  properties with the pumping lemma  so closure properties sometimes help you  so let's look at the language b which is  actually we saw earlier in the lecture  where we have an equal number of zeros  and ones  now we could prove that directly using  the pumping lemma as not being regular  but it's actually even easier  um  uh what we're going to prove  uh that it  we're going to prove that it's not  regular in a different way first we're  going to assume for contradiction as we  often do that it is regular um  and now we're going to use something  we're going to use some other knowledge  we're not going to use the pumping llama  here um because we're going to take  advantage of an earlier case where we  use the pumping level  and so um  now we know that the string the language  0 star 1 star is a regular language  because it's described by a regular  expression if you take the  b  which is the equal numbers of zeros and  ones  and you intersect it with zero star one  star  that's going to be a regular language if  b was regular  using closure under intersection  but this language b intersect zero star  one star  is the language  of  equal numbers of zeros and ones where  the zeros come first  and that's the language d that we show  two slides back  that we already know can't be regular  so that intersection cannot be regular  and so it violates the closure property  um  and again we get a contradiction  uh so  um that's a different way of  sometimes making a shortcut  to prove a language is not regular  okay  so we have in our last uh ten minutes or  so we're going to shift gears totally in  an entirely different way and consider a  new model of computation uh which is  more powerful that can actually do  things that we can't do with a with  finite automata and these are called  context-free grammars so this is really  just a kind of an introduction  we're going to spend uh all of next  lecture uh looking at context-free  grammars um and their associated  languages uh but let's just to kind of  get us  get a preview  so a context-free grammar looks like  this you have a bunch of these  um  uh  um what we call substitution rules or  rules sometimes  would just look like a symbol arrow a  string of symbols  all right  that's what a context-free grammar looks  like at a high level  let's define some terms um  so a rule as i just described is uh  going to be look it's going to be a  symbol which we're going to call a  variable  um and that's going to have an arrow to  a string of other possibly other  variables and  symbols called terminals  um  so a variable is a symbol that appears  on the left hand side of a rule  anything that appears on the left hand  side is going to be considered to be a  very ver a variable um  okay  so s and r are both variables  um  now  other symbols that appear in the grammar  which don't appear in the in in the  left-hand side  those  are going to be called terminals  so here 0 and 1 are terminals  now you may think that empty string  should also be a terminal but that's not  a symbol an empty string is a string  it's just a string of length zero so i'm  not considering empty string to be a  terminal  so  and then there's going to be a special  variable which is going to be considered  the starting variable just like we had a  starting state and that's typically  going to be written as the top left  symbol so this symbol s here is going to  be the starting symbol  and grammars can be used to  uh define languages  and to gen well to generate strings and  to define languages so first of all  let's see how  a grammar using this as an illustration  can generate strings um  actually just to emphasize this uh these  terminology here in this particular  example we had three rules  uh the two variables were r and s the  two terminals were zero and one  and the start variable was this top  left-hand symbol as i mentioned the s  okay  so grammars generate strings the way  they do is  you follow a certain procedure which is  really pretty simple  you  write down first of all the starts  variable and i'll do an example in a  second  you write down the start variable  and then you take a look what you've  written down  and if it has any variables in it you  can  apply  one of the corresponding right hand  sides of a rule  um  to as a substitution for that variable  and so like for example if you have an s  in the thing you've written down you can  substitute for that s a zero s one  or you can substitute for that s and r  or if you have an r you can substitute  for that's an empty string  so you're just going to keep on doing  that substitutions over and over again  until there are no variables left so  there's nothing left to substitute  only terminals remain  at that point you have generated a  string in the language  okay so the language then is the  collection of all generated strings  okay let's do an example here's an  example of g1 generating some string so  as i mentioned first of all you're going  to write down the start variable  and i'm just going to illustrate this in  sort of two parallel tracks here  on the left side i'm going to show you  the tree of substitutions and on the  right side i'm going to show you the  resulting string that you get by  applying those substitutions  okay  so over here i'm going to substitute for  s the string 0 s1 so on the right hand  side i just have 0 s1 because that's  what i substituted for s but you'll see  it's not going to it's going to look a  little different in a second  here i'm going to again i still have a  variable so i'm going to substitute for  s 0 s 1.  now i have the string resulting string 0  0 s 1 1 because i've substituted 0 s 1  for the previous s but the 0 and 1 stick  around from before they don't go  anywhere so i have at this point 0 0 s 1  1. now  uh i'm going to take a different choice  i'm going to substitute for s you know i  could have gone either way this sort of  something like almost like  non-determinism here because you have a  choice  uh i'm going to substitute for s um  instead of 0 s1 i'm going to substitute  r because that's also legitimate in  terms of the rules  and so now i'm going to have  0 0 r  1 1.  and now r has there's no choices here r  can only be substituted for by an empty  string  so i get to r becomes just empty string  and in terms of the string generated  empty string doesn't add anything it  just really is  nothing it's a nothing so i get the  string 0 0 1 1 and this is a string just  of terminal symbols  and so that is a string in the language  of  the grammar g1  okay  if you think about it g1's language is  that language that we saw before uh  which i think we called  d  um  zero to the k one to the k for k greater  than or equal to zero so this is an  example of the language that a  context-free grammar can do but i find  that automaton cannot do  okay  so that is our little introduction to  con oops there's one more check in here  um  oh yeah so i'm asking you to actually  look at  let me get myself a look out of this  picture  um  so you  don't see me blocking things  and we will do one last check-in  make sure you're staying around for the  whole thing  now you can now there could be several  of these strings that are in the  language you have to click them all  all the ones that you have found that  are in the language of this grammar that  can be generated by grammar g2  you have to click those i'll give you a  little bit more time on this one um  to see which ones uh g2 can generate  um  i'll give you a hint it's more than one  but not all  uh  so i see you're making some progress  here  um  interesting  so please uh we're gonna wrap this up  very quickly  uh you can't call us somebody's telling  me you can't unclick thank you good to  know  um  [Music]  okay so still things are coming in here  so  uh  let's not we're we're running toward the  end of the hour here i don't want to go  over so i'm going to end it in five  seconds  uh click away and don't forget  uh  we're not uh going to charge you if you  get it wrong um  sharing results  uh  i don't know why it has an orange one  there because  there are several correct answers here  um  so it's a b and d are correct  um you can get any of any of those um  it's really sort of two copies of the  language we had before  uh next to one another uh  and so  um  the only thing you cannot get is  one zero one zero  um so i encourage you to think about  that  and i will uh  uh  come to our last side of today um which  is just a quick review um  i can put myself back  so we show how to convert dfas to  regular expressions  and the summary is that dfas nfas  gnfas even ray and regular expressions  are all equivalent um in the class of  languages they can describe  uh  the second thing we did was a method for  proving languages not regular by using  the pumping lemma or closure properties  and lastly we introduced context-free  grammars and we're going to see more  about those on thursday  so with that i think we're out of time  and  other thank you for the  notes of appreciation and um  i will um  i think we're gonna  end here um and uh  see you  um on thursday if not before

4
00:00:27,990 --> 00:00:29,669

 

5
00:00:29,669 --> 00:00:31,349

 

6
00:00:31,349 --> 00:00:33,270

 

7
00:00:33,270 --> 00:00:35,910

 

8
00:00:35,910 --> 00:00:35,920

 

9
00:00:35,920 --> 00:00:37,190


10
00:00:37,190 --> 00:00:37,200

 

11
00:00:37,200 --> 00:00:38,069


12
00:00:38,069 --> 00:00:40,950

 

13
00:00:40,950 --> 00:00:43,110

 

14
00:00:43,110 --> 00:00:45,670

 

15
00:00:45,670 --> 00:00:48,069

 

16
00:00:48,069 --> 00:00:49,830

 

17
00:00:49,830 --> 00:00:49,840

 

18
00:00:49,840 --> 00:00:51,590


19
00:00:51,590 --> 00:00:53,270

 

20
00:00:53,270 --> 00:00:54,630

 

21
00:00:54,630 --> 00:00:56,150

 

22
00:00:56,150 --> 00:00:58,069

 

23
00:00:58,069 --> 00:00:59,910

 

24
00:00:59,910 --> 00:01:01,830

 

25
00:01:01,830 --> 00:01:05,270

 

26
00:01:05,270 --> 00:01:06,950

 

27
00:01:06,950 --> 00:01:09,109

 

28
00:01:09,109 --> 00:01:09,119

 

29
00:01:09,119 --> 00:01:09,910


30
00:01:09,910 --> 00:01:12,070

 

31
00:01:12,070 --> 00:01:13,910

 

32
00:01:13,910 --> 00:01:15,670

 

33
00:01:15,670 --> 00:01:18,469

 

34
00:01:18,469 --> 00:01:20,390

 

35
00:01:20,390 --> 00:01:23,830

 

36
00:01:23,830 --> 00:01:26,789

 

37
00:01:26,789 --> 00:01:31,670

 

38
00:01:31,670 --> 00:01:33,830

 

39
00:01:33,830 --> 00:01:33,840

 

40
00:01:33,840 --> 00:01:34,550


41
00:01:34,550 --> 00:01:36,950

 

42
00:01:36,950 --> 00:01:38,469

 

43
00:01:38,469 --> 00:01:41,030

 

44
00:01:41,030 --> 00:01:43,270

 

45
00:01:43,270 --> 00:01:44,870

 

46
00:01:44,870 --> 00:01:47,270

 

47
00:01:47,270 --> 00:01:49,190

 

48
00:01:49,190 --> 00:01:51,270

 

49
00:01:51,270 --> 00:01:53,749

 

50
00:01:53,749 --> 00:01:56,789

 

51
00:01:56,789 --> 00:01:58,709

 

52
00:01:58,709 --> 00:02:00,870

 

53
00:02:00,870 --> 00:02:03,109

 

54
00:02:03,109 --> 00:02:04,469

 

55
00:02:04,469 --> 00:02:04,479

 

56
00:02:04,479 --> 00:02:05,590


57
00:02:05,590 --> 00:02:05,600

 

58
00:02:05,600 --> 00:02:07,030


59
00:02:07,030 --> 00:02:08,949

 

60
00:02:08,949 --> 00:02:10,469

 

61
00:02:10,469 --> 00:02:12,630

 

62
00:02:12,630 --> 00:02:13,830

 

63
00:02:13,830 --> 00:02:16,229

 

64
00:02:16,229 --> 00:02:18,309

 

65
00:02:18,309 --> 00:02:20,630

 

66
00:02:20,630 --> 00:02:21,750

 

67
00:02:21,750 --> 00:02:24,390

 

68
00:02:24,390 --> 00:02:26,550

 

69
00:02:26,550 --> 00:02:28,869

 

70
00:02:28,869 --> 00:02:31,110

 

71
00:02:31,110 --> 00:02:32,869

 

72
00:02:32,869 --> 00:02:34,830

 

73
00:02:34,830 --> 00:02:38,309

 

74
00:02:38,309 --> 00:02:41,110

 

75
00:02:41,110 --> 00:02:42,869

 

76
00:02:42,869 --> 00:02:44,949

 

77
00:02:44,949 --> 00:02:47,110

 

78
00:02:47,110 --> 00:02:48,710

 

79
00:02:48,710 --> 00:02:50,869

 

80
00:02:50,869 --> 00:02:52,630

 

81
00:02:52,630 --> 00:02:54,309

 

82
00:02:54,309 --> 00:02:56,309

 

83
00:02:56,309 --> 00:02:56,319

 

84
00:02:56,319 --> 00:02:57,270


85
00:02:57,270 --> 00:02:59,589

 

86
00:02:59,589 --> 00:03:02,229

 

87
00:03:02,229 --> 00:03:04,149

 

88
00:03:04,149 --> 00:03:07,190

 

89
00:03:07,190 --> 00:03:08,790

 

90
00:03:08,790 --> 00:03:08,800

 

91
00:03:08,800 --> 00:03:09,990


92
00:03:09,990 --> 00:03:12,070

 

93
00:03:12,070 --> 00:03:14,470

 

94
00:03:14,470 --> 00:03:15,589

 

95
00:03:15,589 --> 00:03:19,190

 

96
00:03:19,190 --> 00:03:20,149

 

97
00:03:20,149 --> 00:03:22,229

 

98
00:03:22,229 --> 00:03:22,239

 

99
00:03:22,239 --> 00:03:24,229


100
00:03:24,229 --> 00:03:26,470

 

101
00:03:26,470 --> 00:03:27,830

 

102
00:03:27,830 --> 00:03:30,710

 

103
00:03:30,710 --> 00:03:30,720

 

104
00:03:30,720 --> 00:03:31,589


105
00:03:31,589 --> 00:03:33,350

 

106
00:03:33,350 --> 00:03:36,229

 

107
00:03:36,229 --> 00:03:37,830

 

108
00:03:37,830 --> 00:03:41,110

 

109
00:03:41,110 --> 00:03:44,149

 

110
00:03:44,149 --> 00:03:47,190

 

111
00:03:47,190 --> 00:03:49,750

 

112
00:03:49,750 --> 00:03:51,990

 

113
00:03:51,990 --> 00:03:54,470

 

114
00:03:54,470 --> 00:03:56,789

 

115
00:03:56,789 --> 00:03:58,550

 

116
00:03:58,550 --> 00:04:00,390

 

117
00:04:00,390 --> 00:04:03,270

 

118
00:04:03,270 --> 00:04:03,280

 

119
00:04:03,280 --> 00:04:05,670


120
00:04:05,670 --> 00:04:06,869

 

121
00:04:06,869 --> 00:04:08,949

 

122
00:04:08,949 --> 00:04:11,110

 

123
00:04:11,110 --> 00:04:14,390

 

124
00:04:14,390 --> 00:04:16,629

 

125
00:04:16,629 --> 00:04:19,189

 

126
00:04:19,189 --> 00:04:21,909

 

127
00:04:21,909 --> 00:04:21,919

 

128
00:04:21,919 --> 00:04:23,270


129
00:04:23,270 --> 00:04:27,110

 

130
00:04:27,110 --> 00:04:30,469

 

131
00:04:30,469 --> 00:04:32,070

 

132
00:04:32,070 --> 00:04:33,430

 

133
00:04:33,430 --> 00:04:36,070

 

134
00:04:36,070 --> 00:04:37,749

 

135
00:04:37,749 --> 00:04:39,749

 

136
00:04:39,749 --> 00:04:41,990

 

137
00:04:41,990 --> 00:04:43,749

 

138
00:04:43,749 --> 00:04:45,749

 

139
00:04:45,749 --> 00:04:45,759

 

140
00:04:45,759 --> 00:04:47,110


141
00:04:47,110 --> 00:04:47,120

 

142
00:04:47,120 --> 00:04:48,390


143
00:04:48,390 --> 00:04:48,400

 

144
00:04:48,400 --> 00:04:50,469


145
00:04:50,469 --> 00:04:52,710

 

146
00:04:52,710 --> 00:04:54,629

 

147
00:04:54,629 --> 00:04:58,310

 

148
00:04:58,310 --> 00:05:00,550

 

149
00:05:00,550 --> 00:05:02,710

 

150
00:05:02,710 --> 00:05:04,310

 

151
00:05:04,310 --> 00:05:06,390

 

152
00:05:06,390 --> 00:05:09,029

 

153
00:05:09,029 --> 00:05:11,029

 

154
00:05:11,029 --> 00:05:13,510

 

155
00:05:13,510 --> 00:05:15,189

 

156
00:05:15,189 --> 00:05:18,230

 

157
00:05:18,230 --> 00:05:20,150

 

158
00:05:20,150 --> 00:05:21,749

 

159
00:05:21,749 --> 00:05:24,629

 

160
00:05:24,629 --> 00:05:26,950

 

161
00:05:26,950 --> 00:05:29,270

 

162
00:05:29,270 --> 00:05:31,510

 

163
00:05:31,510 --> 00:05:34,230

 

164
00:05:34,230 --> 00:05:37,110

 

165
00:05:37,110 --> 00:05:40,150

 

166
00:05:40,150 --> 00:05:42,310

 

167
00:05:42,310 --> 00:05:44,950

 

168
00:05:44,950 --> 00:05:44,960

 

169
00:05:44,960 --> 00:05:47,670


170
00:05:47,670 --> 00:05:47,680

 

171
00:05:47,680 --> 00:05:48,550


172
00:05:48,550 --> 00:05:48,560

 

173
00:05:48,560 --> 00:05:49,430


174
00:05:49,430 --> 00:05:49,440

 

175
00:05:49,440 --> 00:05:50,230


176
00:05:50,230 --> 00:05:50,240

 

177
00:05:50,240 --> 00:05:51,430


178
00:05:51,430 --> 00:05:53,430

 

179
00:05:53,430 --> 00:05:55,029

 

180
00:05:55,029 --> 00:05:56,390

 

181
00:05:56,390 --> 00:05:56,400

 

182
00:05:56,400 --> 00:05:57,350


183
00:05:57,350 --> 00:05:58,790

 

184
00:05:58,790 --> 00:05:58,800

 

185
00:05:58,800 --> 00:06:00,390


186
00:06:00,390 --> 00:06:02,390

 

187
00:06:02,390 --> 00:06:04,950

 

188
00:06:04,950 --> 00:06:07,350

 

189
00:06:07,350 --> 00:06:09,350

 

190
00:06:09,350 --> 00:06:10,870

 

191
00:06:10,870 --> 00:06:13,189

 

192
00:06:13,189 --> 00:06:15,590

 

193
00:06:15,590 --> 00:06:15,600

 

194
00:06:15,600 --> 00:06:17,590


195
00:06:17,590 --> 00:06:19,110

 

196
00:06:19,110 --> 00:06:21,830

 

197
00:06:21,830 --> 00:06:23,670

 

198
00:06:23,670 --> 00:06:26,150

 

199
00:06:26,150 --> 00:06:29,510

 

200
00:06:29,510 --> 00:06:31,270

 

201
00:06:31,270 --> 00:06:34,070

 

202
00:06:34,070 --> 00:06:35,510

 

203
00:06:35,510 --> 00:06:37,110

 

204
00:06:37,110 --> 00:06:39,590

 

205
00:06:39,590 --> 00:06:42,230

 

206
00:06:42,230 --> 00:06:44,710

 

207
00:06:44,710 --> 00:06:47,510

 

208
00:06:47,510 --> 00:06:49,589

 

209
00:06:49,589 --> 00:06:52,550

 

210
00:06:52,550 --> 00:06:57,029

 

211
00:06:57,029 --> 00:06:59,909

 

212
00:06:59,909 --> 00:07:02,710

 

213
00:07:02,710 --> 00:07:02,720

 

214
00:07:02,720 --> 00:07:03,830


215
00:07:03,830 --> 00:07:06,550

 

216
00:07:06,550 --> 00:07:09,350

 

217
00:07:09,350 --> 00:07:11,510

 

218
00:07:11,510 --> 00:07:11,520

 

219
00:07:11,520 --> 00:07:13,589


220
00:07:13,589 --> 00:07:13,599

 

221
00:07:13,599 --> 00:07:14,830


222
00:07:14,830 --> 00:07:18,469

 

223
00:07:18,469 --> 00:07:20,790

 

224
00:07:20,790 --> 00:07:20,800

 

225
00:07:20,800 --> 00:07:21,990


226
00:07:21,990 --> 00:07:25,830

 

227
00:07:25,830 --> 00:07:27,670

 

228
00:07:27,670 --> 00:07:30,469

 

229
00:07:30,469 --> 00:07:32,870

 

230
00:07:32,870 --> 00:07:35,270

 

231
00:07:35,270 --> 00:07:38,469

 

232
00:07:38,469 --> 00:07:40,230

 

233
00:07:40,230 --> 00:07:42,550

 

234
00:07:42,550 --> 00:07:44,710

 

235
00:07:44,710 --> 00:07:47,749

 

236
00:07:47,749 --> 00:07:50,469

 

237
00:07:50,469 --> 00:07:50,479

 

238
00:07:50,479 --> 00:07:51,430


239
00:07:51,430 --> 00:07:53,270

 

240
00:07:53,270 --> 00:07:55,430

 

241
00:07:55,430 --> 00:07:58,230

 

242
00:07:58,230 --> 00:08:00,070

 

243
00:08:00,070 --> 00:08:00,080

 

244
00:08:00,080 --> 00:08:01,189


245
00:08:01,189 --> 00:08:04,070

 

246
00:08:04,070 --> 00:08:06,070

 

247
00:08:06,070 --> 00:08:08,629

 

248
00:08:08,629 --> 00:08:10,309

 

249
00:08:10,309 --> 00:08:10,319

 

250
00:08:10,319 --> 00:08:11,430


251
00:08:11,430 --> 00:08:14,550

 

252
00:08:14,550 --> 00:08:18,150

 

253
00:08:18,150 --> 00:08:20,869

 

254
00:08:20,869 --> 00:08:23,510

 

255
00:08:23,510 --> 00:08:23,520

 

256
00:08:23,520 --> 00:08:24,309


257
00:08:24,309 --> 00:08:26,790

 

258
00:08:26,790 --> 00:08:29,990

 

259
00:08:29,990 --> 00:08:32,310

 

260
00:08:32,310 --> 00:08:33,750

 

261
00:08:33,750 --> 00:08:33,760

 

262
00:08:33,760 --> 00:08:34,870


263
00:08:34,870 --> 00:08:37,029

 

264
00:08:37,029 --> 00:08:39,029

 

265
00:08:39,029 --> 00:08:40,469

 

266
00:08:40,469 --> 00:08:40,479

 

267
00:08:40,479 --> 00:08:42,149


268
00:08:42,149 --> 00:08:45,990

 

269
00:08:45,990 --> 00:08:49,750

 

270
00:08:49,750 --> 00:08:53,350

 

271
00:08:53,350 --> 00:08:55,509

 

272
00:08:55,509 --> 00:08:56,630

 

273
00:08:56,630 --> 00:08:59,110

 

274
00:08:59,110 --> 00:09:01,030

 

275
00:09:01,030 --> 00:09:02,790

 

276
00:09:02,790 --> 00:09:05,670

 

277
00:09:05,670 --> 00:09:07,670

 

278
00:09:07,670 --> 00:09:10,230

 

279
00:09:10,230 --> 00:09:12,630

 

280
00:09:12,630 --> 00:09:14,630

 

281
00:09:14,630 --> 00:09:16,310

 

282
00:09:16,310 --> 00:09:19,670

 

283
00:09:19,670 --> 00:09:21,670

 

284
00:09:21,670 --> 00:09:21,680

 

285
00:09:21,680 --> 00:09:22,389


286
00:09:22,389 --> 00:09:25,269

 

287
00:09:25,269 --> 00:09:27,829

 

288
00:09:27,829 --> 00:09:30,150

 

289
00:09:30,150 --> 00:09:31,990

 

290
00:09:31,990 --> 00:09:34,790

 

291
00:09:34,790 --> 00:09:37,350

 

292
00:09:37,350 --> 00:09:39,110

 

293
00:09:39,110 --> 00:09:42,070

 

294
00:09:42,070 --> 00:09:43,509

 

295
00:09:43,509 --> 00:09:47,269

 

296
00:09:47,269 --> 00:09:49,910

 

297
00:09:49,910 --> 00:09:53,110

 

298
00:09:53,110 --> 00:09:55,990

 

299
00:09:55,990 --> 00:09:58,150

 

300
00:09:58,150 --> 00:09:58,160

 

301
00:09:58,160 --> 00:09:59,509


302
00:09:59,509 --> 00:09:59,519

 

303
00:09:59,519 --> 00:10:00,870


304
00:10:00,870 --> 00:10:02,710

 

305
00:10:02,710 --> 00:10:04,630

 

306
00:10:04,630 --> 00:10:04,640

 

307
00:10:04,640 --> 00:10:05,590


308
00:10:05,590 --> 00:10:07,430

 

309
00:10:07,430 --> 00:10:07,440

 

310
00:10:07,440 --> 00:10:09,509


311
00:10:09,509 --> 00:10:12,389

 

312
00:10:12,389 --> 00:10:15,910

 

313
00:10:15,910 --> 00:10:17,590

 

314
00:10:17,590 --> 00:10:20,470

 

315
00:10:20,470 --> 00:10:22,310

 

316
00:10:22,310 --> 00:10:24,150

 

317
00:10:24,150 --> 00:10:26,069

 

318
00:10:26,069 --> 00:10:28,069

 

319
00:10:28,069 --> 00:10:28,079

 

320
00:10:28,079 --> 00:10:28,949


321
00:10:28,949 --> 00:10:31,190

 

322
00:10:31,190 --> 00:10:33,750

 

323
00:10:33,750 --> 00:10:35,670

 

324
00:10:35,670 --> 00:10:37,509

 

325
00:10:37,509 --> 00:10:37,519

 

326
00:10:37,519 --> 00:10:38,550


327
00:10:38,550 --> 00:10:38,560

 

328
00:10:38,560 --> 00:10:40,069


329
00:10:40,069 --> 00:10:42,310

 

330
00:10:42,310 --> 00:10:44,949

 

331
00:10:44,949 --> 00:10:46,550

 

332
00:10:46,550 --> 00:10:48,630

 

333
00:10:48,630 --> 00:10:48,640

 

334
00:10:48,640 --> 00:10:49,910


335
00:10:49,910 --> 00:10:51,910

 

336
00:10:51,910 --> 00:10:54,949

 

337
00:10:54,949 --> 00:10:54,959

 

338
00:10:54,959 --> 00:10:55,990


339
00:10:55,990 --> 00:10:59,190

 

340
00:10:59,190 --> 00:11:02,069

 

341
00:11:02,069 --> 00:11:07,190

 

342
00:11:07,190 --> 00:11:09,590

 

343
00:11:09,590 --> 00:11:12,710

 

344
00:11:12,710 --> 00:11:15,269

 

345
00:11:15,269 --> 00:11:17,190

 

346
00:11:17,190 --> 00:11:21,750

 

347
00:11:21,750 --> 00:11:24,310

 

348
00:11:24,310 --> 00:11:25,829

 

349
00:11:25,829 --> 00:11:27,670

 

350
00:11:27,670 --> 00:11:30,069

 

351
00:11:30,069 --> 00:11:32,470

 

352
00:11:32,470 --> 00:11:34,870

 

353
00:11:34,870 --> 00:11:37,990

 

354
00:11:37,990 --> 00:11:40,550

 

355
00:11:40,550 --> 00:11:43,030

 

356
00:11:43,030 --> 00:11:46,470

 

357
00:11:46,470 --> 00:11:48,150

 

358
00:11:48,150 --> 00:11:51,110

 

359
00:11:51,110 --> 00:11:54,310

 

360
00:11:54,310 --> 00:11:56,710

 

361
00:11:56,710 --> 00:11:58,470

 

362
00:11:58,470 --> 00:12:00,710

 

363
00:12:00,710 --> 00:12:02,150

 

364
00:12:02,150 --> 00:12:04,629

 

365
00:12:04,629 --> 00:12:06,550

 

366
00:12:06,550 --> 00:12:09,509

 

367
00:12:09,509 --> 00:12:13,030

 

368
00:12:13,030 --> 00:12:14,310

 

369
00:12:14,310 --> 00:12:15,430

 

370
00:12:15,430 --> 00:12:17,190

 

371
00:12:17,190 --> 00:12:19,430

 

372
00:12:19,430 --> 00:12:22,790

 

373
00:12:22,790 --> 00:12:26,230

 

374
00:12:26,230 --> 00:12:29,670

 

375
00:12:29,670 --> 00:12:31,910

 

376
00:12:31,910 --> 00:12:33,350

 

377
00:12:33,350 --> 00:12:35,030

 

378
00:12:35,030 --> 00:12:35,040

 

379
00:12:35,040 --> 00:12:35,829


380
00:12:35,829 --> 00:12:37,910

 

381
00:12:37,910 --> 00:12:39,990

 

382
00:12:39,990 --> 00:12:40,000

 

383
00:12:40,000 --> 00:12:40,949


384
00:12:40,949 --> 00:12:40,959

 

385
00:12:40,959 --> 00:12:41,910


386
00:12:41,910 --> 00:12:44,710

 

387
00:12:44,710 --> 00:12:47,269

 

388
00:12:47,269 --> 00:12:49,829

 

389
00:12:49,829 --> 00:12:51,190

 

390
00:12:51,190 --> 00:12:52,710

 

391
00:12:52,710 --> 00:12:55,030

 

392
00:12:55,030 --> 00:12:58,470

 

393
00:12:58,470 --> 00:12:59,829

 

394
00:12:59,829 --> 00:13:02,550

 

395
00:13:02,550 --> 00:13:05,430

 

396
00:13:05,430 --> 00:13:05,440

 

397
00:13:05,440 --> 00:13:06,470


398
00:13:06,470 --> 00:13:07,829

 

399
00:13:07,829 --> 00:13:09,990

 

400
00:13:09,990 --> 00:13:12,069

 

401
00:13:12,069 --> 00:13:13,990

 

402
00:13:13,990 --> 00:13:15,910

 

403
00:13:15,910 --> 00:13:18,069

 

404
00:13:18,069 --> 00:13:20,310

 

405
00:13:20,310 --> 00:13:22,870

 

406
00:13:22,870 --> 00:13:26,069

 

407
00:13:26,069 --> 00:13:28,069

 

408
00:13:28,069 --> 00:13:29,590

 

409
00:13:29,590 --> 00:13:31,910

 

410
00:13:31,910 --> 00:13:35,269

 

411
00:13:35,269 --> 00:13:37,269

 

412
00:13:37,269 --> 00:13:39,670

 

413
00:13:39,670 --> 00:13:41,350

 

414
00:13:41,350 --> 00:13:43,350

 

415
00:13:43,350 --> 00:13:45,030

 

416
00:13:45,030 --> 00:13:45,040

 

417
00:13:45,040 --> 00:13:46,470


418
00:13:46,470 --> 00:13:48,629

 

419
00:13:48,629 --> 00:13:52,550

 

420
00:13:52,550 --> 00:13:52,560

 

421
00:13:52,560 --> 00:13:53,670


422
00:13:53,670 --> 00:13:55,990

 

423
00:13:55,990 --> 00:13:58,069

 

424
00:13:58,069 --> 00:14:00,870

 

425
00:14:00,870 --> 00:14:03,030

 

426
00:14:03,030 --> 00:14:05,990

 

427
00:14:05,990 --> 00:14:08,150

 

428
00:14:08,150 --> 00:14:10,150

 

429
00:14:10,150 --> 00:14:12,470

 

430
00:14:12,470 --> 00:14:14,550

 

431
00:14:14,550 --> 00:14:16,710

 

432
00:14:16,710 --> 00:14:18,310

 

433
00:14:18,310 --> 00:14:21,350

 

434
00:14:21,350 --> 00:14:23,269

 

435
00:14:23,269 --> 00:14:25,189

 

436
00:14:25,189 --> 00:14:27,030

 

437
00:14:27,030 --> 00:14:29,750

 

438
00:14:29,750 --> 00:14:32,310

 

439
00:14:32,310 --> 00:14:35,110

 

440
00:14:35,110 --> 00:14:37,269

 

441
00:14:37,269 --> 00:14:38,949

 

442
00:14:38,949 --> 00:14:40,310

 

443
00:14:40,310 --> 00:14:42,550

 

444
00:14:42,550 --> 00:14:44,470

 

445
00:14:44,470 --> 00:14:46,550

 

446
00:14:46,550 --> 00:14:48,790

 

447
00:14:48,790 --> 00:14:51,030

 

448
00:14:51,030 --> 00:14:52,790

 

449
00:14:52,790 --> 00:14:55,269

 

450
00:14:55,269 --> 00:14:57,670

 

451
00:14:57,670 --> 00:14:59,750

 

452
00:14:59,750 --> 00:15:02,310

 

453
00:15:02,310 --> 00:15:04,310

 

454
00:15:04,310 --> 00:15:07,990

 

455
00:15:07,990 --> 00:15:08,000

 

456
00:15:08,000 --> 00:15:08,949


457
00:15:08,949 --> 00:15:11,189

 

458
00:15:11,189 --> 00:15:13,990

 

459
00:15:13,990 --> 00:15:16,150

 

460
00:15:16,150 --> 00:15:18,150

 

461
00:15:18,150 --> 00:15:21,269

 

462
00:15:21,269 --> 00:15:23,030

 

463
00:15:23,030 --> 00:15:25,350

 

464
00:15:25,350 --> 00:15:27,350

 

465
00:15:27,350 --> 00:15:29,590

 

466
00:15:29,590 --> 00:15:31,990

 

467
00:15:31,990 --> 00:15:33,030

 

468
00:15:33,030 --> 00:15:34,870

 

469
00:15:34,870 --> 00:15:36,949

 

470
00:15:36,949 --> 00:15:38,870

 

471
00:15:38,870 --> 00:15:40,310

 

472
00:15:40,310 --> 00:15:40,320

 

473
00:15:40,320 --> 00:15:41,829


474
00:15:41,829 --> 00:15:41,839

 

475
00:15:41,839 --> 00:15:43,030


476
00:15:43,030 --> 00:15:45,670

 

477
00:15:45,670 --> 00:15:48,710

 

478
00:15:48,710 --> 00:15:50,870

 

479
00:15:50,870 --> 00:15:53,350

 

480
00:15:53,350 --> 00:15:56,870

 

481
00:15:56,870 --> 00:15:58,790

 

482
00:15:58,790 --> 00:16:00,629

 

483
00:16:00,629 --> 00:16:02,150

 

484
00:16:02,150 --> 00:16:04,230

 

485
00:16:04,230 --> 00:16:06,310

 

486
00:16:06,310 --> 00:16:08,870

 

487
00:16:08,870 --> 00:16:11,110

 

488
00:16:11,110 --> 00:16:12,949

 

489
00:16:12,949 --> 00:16:15,749

 

490
00:16:15,749 --> 00:16:17,829

 

491
00:16:17,829 --> 00:16:19,590

 

492
00:16:19,590 --> 00:16:19,600

 

493
00:16:19,600 --> 00:16:20,870


494
00:16:20,870 --> 00:16:23,509

 

495
00:16:23,509 --> 00:16:23,519

 

496
00:16:23,519 --> 00:16:24,710


497
00:16:24,710 --> 00:16:26,790

 

498
00:16:26,790 --> 00:16:28,069

 

499
00:16:28,069 --> 00:16:30,629

 

500
00:16:30,629 --> 00:16:32,790

 

501
00:16:32,790 --> 00:16:34,829

 

502
00:16:34,829 --> 00:16:38,230

 

503
00:16:38,230 --> 00:16:40,550

 

504
00:16:40,550 --> 00:16:42,949

 

505
00:16:42,949 --> 00:16:45,350

 

506
00:16:45,350 --> 00:16:47,269

 

507
00:16:47,269 --> 00:16:48,949

 

508
00:16:48,949 --> 00:16:51,590

 

509
00:16:51,590 --> 00:16:53,509

 

510
00:16:53,509 --> 00:16:55,749

 

511
00:16:55,749 --> 00:16:57,509

 

512
00:16:57,509 --> 00:16:59,189

 

513
00:16:59,189 --> 00:17:01,110

 

514
00:17:01,110 --> 00:17:03,829

 

515
00:17:03,829 --> 00:17:05,669

 

516
00:17:05,669 --> 00:17:07,669

 

517
00:17:07,669 --> 00:17:09,189

 

518
00:17:09,189 --> 00:17:13,429

 

519
00:17:13,429 --> 00:17:16,789

 

520
00:17:16,789 --> 00:17:19,029

 

521
00:17:19,029 --> 00:17:21,110

 

522
00:17:21,110 --> 00:17:23,110

 

523
00:17:23,110 --> 00:17:23,120

 

524
00:17:23,120 --> 00:17:24,230


525
00:17:24,230 --> 00:17:24,240

 

526
00:17:24,240 --> 00:17:25,189


527
00:17:25,189 --> 00:17:27,270

 

528
00:17:27,270 --> 00:17:30,070

 

529
00:17:30,070 --> 00:17:31,909

 

530
00:17:31,909 --> 00:17:34,390

 

531
00:17:34,390 --> 00:17:36,870

 

532
00:17:36,870 --> 00:17:36,880

 

533
00:17:36,880 --> 00:17:39,430


534
00:17:39,430 --> 00:17:41,270

 

535
00:17:41,270 --> 00:17:44,150

 

536
00:17:44,150 --> 00:17:46,789

 

537
00:17:46,789 --> 00:17:48,470

 

538
00:17:48,470 --> 00:17:49,830

 

539
00:17:49,830 --> 00:17:51,430

 

540
00:17:51,430 --> 00:17:52,870

 

541
00:17:52,870 --> 00:17:54,549

 

542
00:17:54,549 --> 00:17:57,510

 

543
00:17:57,510 --> 00:17:59,270

 

544
00:17:59,270 --> 00:18:01,830

 

545
00:18:01,830 --> 00:18:04,230

 

546
00:18:04,230 --> 00:18:04,240

 

547
00:18:04,240 --> 00:18:05,350


548
00:18:05,350 --> 00:18:08,230

 

549
00:18:08,230 --> 00:18:10,549

 

550
00:18:10,549 --> 00:18:14,549

 

551
00:18:14,549 --> 00:18:16,230

 

552
00:18:16,230 --> 00:18:19,029

 

553
00:18:19,029 --> 00:18:20,470

 

554
00:18:20,470 --> 00:18:22,470

 

555
00:18:22,470 --> 00:18:24,310

 

556
00:18:24,310 --> 00:18:28,310

 

557
00:18:28,310 --> 00:18:29,350

 

558
00:18:29,350 --> 00:18:31,270

 

559
00:18:31,270 --> 00:18:33,669

 

560
00:18:33,669 --> 00:18:36,630

 

561
00:18:36,630 --> 00:18:40,070

 

562
00:18:40,070 --> 00:18:40,080

 

563
00:18:40,080 --> 00:18:41,590


564
00:18:41,590 --> 00:18:43,510

 

565
00:18:43,510 --> 00:18:46,630

 

566
00:18:46,630 --> 00:18:49,110

 

567
00:18:49,110 --> 00:18:50,070

 

568
00:18:50,070 --> 00:18:52,310

 

569
00:18:52,310 --> 00:18:53,830

 

570
00:18:53,830 --> 00:18:55,990

 

571
00:18:55,990 --> 00:18:58,310

 

572
00:18:58,310 --> 00:19:00,950

 

573
00:19:00,950 --> 00:19:03,510

 

574
00:19:03,510 --> 00:19:06,630

 

575
00:19:06,630 --> 00:19:09,350

 

576
00:19:09,350 --> 00:19:11,350

 

577
00:19:11,350 --> 00:19:15,190

 

578
00:19:15,190 --> 00:19:16,549

 

579
00:19:16,549 --> 00:19:18,150

 

580
00:19:18,150 --> 00:19:19,830

 

581
00:19:19,830 --> 00:19:21,430

 

582
00:19:21,430 --> 00:19:23,510

 

583
00:19:23,510 --> 00:19:25,990

 

584
00:19:25,990 --> 00:19:27,430

 

585
00:19:27,430 --> 00:19:29,669

 

586
00:19:29,669 --> 00:19:33,110

 

587
00:19:33,110 --> 00:19:34,870

 

588
00:19:34,870 --> 00:19:37,110

 

589
00:19:37,110 --> 00:19:38,870

 

590
00:19:38,870 --> 00:19:40,390

 

591
00:19:40,390 --> 00:19:42,870

 

592
00:19:42,870 --> 00:19:43,909

 

593
00:19:43,909 --> 00:19:46,549

 

594
00:19:46,549 --> 00:19:47,909

 

595
00:19:47,909 --> 00:19:51,190

 

596
00:19:51,190 --> 00:19:53,830

 

597
00:19:53,830 --> 00:19:55,590

 

598
00:19:55,590 --> 00:19:58,470

 

599
00:19:58,470 --> 00:20:00,789

 

600
00:20:00,789 --> 00:20:03,350

 

601
00:20:03,350 --> 00:20:06,549

 

602
00:20:06,549 --> 00:20:08,950

 

603
00:20:08,950 --> 00:20:08,960

 

604
00:20:08,960 --> 00:20:10,870


605
00:20:10,870 --> 00:20:12,789

 

606
00:20:12,789 --> 00:20:12,799

 

607
00:20:12,799 --> 00:20:14,390


608
00:20:14,390 --> 00:20:16,390

 

609
00:20:16,390 --> 00:20:17,909

 

610
00:20:17,909 --> 00:20:21,110

 

611
00:20:21,110 --> 00:20:23,750

 

612
00:20:23,750 --> 00:20:25,830

 

613
00:20:25,830 --> 00:20:28,070

 

614
00:20:28,070 --> 00:20:29,270

 

615
00:20:29,270 --> 00:20:32,149

 

616
00:20:32,149 --> 00:20:33,590

 

617
00:20:33,590 --> 00:20:33,600

 

618
00:20:33,600 --> 00:20:36,390


619
00:20:36,390 --> 00:20:39,909

 

620
00:20:39,909 --> 00:20:39,919

 

621
00:20:39,919 --> 00:20:41,270


622
00:20:41,270 --> 00:20:42,630

 

623
00:20:42,630 --> 00:20:42,640

 

624
00:20:42,640 --> 00:20:43,909


625
00:20:43,909 --> 00:20:46,149

 

626
00:20:46,149 --> 00:20:47,909

 

627
00:20:47,909 --> 00:20:49,510

 

628
00:20:49,510 --> 00:20:51,430

 

629
00:20:51,430 --> 00:20:54,710

 

630
00:20:54,710 --> 00:20:57,350

 

631
00:20:57,350 --> 00:20:59,909

 

632
00:20:59,909 --> 00:20:59,919

 

633
00:20:59,919 --> 00:21:01,110


634
00:21:01,110 --> 00:21:04,390

 

635
00:21:04,390 --> 00:21:07,590

 

636
00:21:07,590 --> 00:21:09,510

 

637
00:21:09,510 --> 00:21:11,350

 

638
00:21:11,350 --> 00:21:13,510

 

639
00:21:13,510 --> 00:21:14,950

 

640
00:21:14,950 --> 00:21:17,029

 

641
00:21:17,029 --> 00:21:19,110

 

642
00:21:19,110 --> 00:21:20,870

 

643
00:21:20,870 --> 00:21:23,909

 

644
00:21:23,909 --> 00:21:25,830

 

645
00:21:25,830 --> 00:21:27,430

 

646
00:21:27,430 --> 00:21:29,909

 

647
00:21:29,909 --> 00:21:31,270

 

648
00:21:31,270 --> 00:21:33,190

 

649
00:21:33,190 --> 00:21:35,110

 

650
00:21:35,110 --> 00:21:35,120

 

651
00:21:35,120 --> 00:21:36,549


652
00:21:36,549 --> 00:21:38,870

 

653
00:21:38,870 --> 00:21:41,510

 

654
00:21:41,510 --> 00:21:42,830

 

655
00:21:42,830 --> 00:21:45,990

 

656
00:21:45,990 --> 00:21:46,000

 

657
00:21:46,000 --> 00:21:46,950


658
00:21:46,950 --> 00:21:46,960

 

659
00:21:46,960 --> 00:21:48,070


660
00:21:48,070 --> 00:21:48,080

 

661
00:21:48,080 --> 00:21:49,029


662
00:21:49,029 --> 00:21:51,029

 

663
00:21:51,029 --> 00:21:53,350

 

664
00:21:53,350 --> 00:21:55,110

 

665
00:21:55,110 --> 00:21:55,120

 

666
00:21:55,120 --> 00:21:56,390


667
00:21:56,390 --> 00:21:59,029

 

668
00:21:59,029 --> 00:22:01,750

 

669
00:22:01,750 --> 00:22:03,270

 

670
00:22:03,270 --> 00:22:05,830

 

671
00:22:05,830 --> 00:22:08,310

 

672
00:22:08,310 --> 00:22:10,390

 

673
00:22:10,390 --> 00:22:13,669

 

674
00:22:13,669 --> 00:22:15,669

 

675
00:22:15,669 --> 00:22:15,679

 

676
00:22:15,679 --> 00:22:18,070


677
00:22:18,070 --> 00:22:19,909

 

678
00:22:19,909 --> 00:22:21,430

 

679
00:22:21,430 --> 00:22:21,440

 

680
00:22:21,440 --> 00:22:21,840


681
00:22:21,840 --> 00:22:21,850

 

682
00:22:21,850 --> 00:22:23,270


683
00:22:23,270 --> 00:22:23,280

 

684
00:22:23,280 --> 00:22:24,950


685
00:22:24,950 --> 00:22:28,149

 

686
00:22:28,149 --> 00:22:30,070

 

687
00:22:30,070 --> 00:22:34,230

 

688
00:22:34,230 --> 00:22:38,149

 

689
00:22:38,149 --> 00:22:39,590

 

690
00:22:39,590 --> 00:22:44,070

 

691
00:22:44,070 --> 00:22:45,669

 

692
00:22:45,669 --> 00:22:47,990

 

693
00:22:47,990 --> 00:22:51,350

 

694
00:22:51,350 --> 00:22:55,350

 

695
00:22:55,350 --> 00:22:55,360

 

696
00:22:55,360 --> 00:22:56,870


697
00:22:56,870 --> 00:23:00,070

 

698
00:23:00,070 --> 00:23:03,029

 

699
00:23:03,029 --> 00:23:07,750

 

700
00:23:07,750 --> 00:23:09,669

 

701
00:23:09,669 --> 00:23:09,679

 

702
00:23:09,679 --> 00:23:13,270


703
00:23:13,270 --> 00:23:15,430

 

704
00:23:15,430 --> 00:23:17,430

 

705
00:23:17,430 --> 00:23:21,590

 

706
00:23:21,590 --> 00:23:23,510

 

707
00:23:23,510 --> 00:23:25,110

 

708
00:23:25,110 --> 00:23:25,120

 

709
00:23:25,120 --> 00:23:26,230


710
00:23:26,230 --> 00:23:29,750

 

711
00:23:29,750 --> 00:23:36,070

 

712
00:23:36,070 --> 00:23:37,350

 

713
00:23:37,350 --> 00:23:39,350

 

714
00:23:39,350 --> 00:23:42,630

 

715
00:23:42,630 --> 00:23:44,149

 

716
00:23:44,149 --> 00:23:47,750

 

717
00:23:47,750 --> 00:23:47,760

 

718
00:23:47,760 --> 00:23:48,710


719
00:23:48,710 --> 00:23:50,549

 

720
00:23:50,549 --> 00:23:53,029

 

721
00:23:53,029 --> 00:23:53,039

 

722
00:23:53,039 --> 00:23:54,870


723
00:23:54,870 --> 00:23:58,470

 

724
00:23:58,470 --> 00:24:02,070

 

725
00:24:02,070 --> 00:24:04,390

 

726
00:24:04,390 --> 00:24:08,310

 

727
00:24:08,310 --> 00:24:10,230

 

728
00:24:10,230 --> 00:24:10,240

 

729
00:24:10,240 --> 00:24:11,190


730
00:24:11,190 --> 00:24:14,710

 

731
00:24:14,710 --> 00:24:17,669

 

732
00:24:17,669 --> 00:24:19,990

 

733
00:24:19,990 --> 00:24:25,990

 

734
00:24:25,990 --> 00:24:26,000

 

735
00:24:26,000 --> 00:24:27,990


736
00:24:27,990 --> 00:24:28,000

 

737
00:24:28,000 --> 00:24:28,789


738
00:24:28,789 --> 00:24:30,710

 

739
00:24:30,710 --> 00:24:33,350

 

740
00:24:33,350 --> 00:24:36,549

 

741
00:24:36,549 --> 00:24:39,350

 

742
00:24:39,350 --> 00:24:41,590

 

743
00:24:41,590 --> 00:24:41,600

 

744
00:24:41,600 --> 00:24:43,110


745
00:24:43,110 --> 00:24:45,590

 

746
00:24:45,590 --> 00:24:48,470

 

747
00:24:48,470 --> 00:24:48,480

 

748
00:24:48,480 --> 00:24:49,350


749
00:24:49,350 --> 00:24:51,190

 

750
00:24:51,190 --> 00:24:53,269

 

751
00:24:53,269 --> 00:24:53,279

 

752
00:24:53,279 --> 00:24:54,549


753
00:24:54,549 --> 00:24:56,630

 

754
00:24:56,630 --> 00:24:59,269

 

755
00:24:59,269 --> 00:25:02,310

 

756
00:25:02,310 --> 00:25:07,269

 

757
00:25:07,269 --> 00:25:09,510

 

758
00:25:09,510 --> 00:25:11,430

 

759
00:25:11,430 --> 00:25:13,350

 

760
00:25:13,350 --> 00:25:17,190

 

761
00:25:17,190 --> 00:25:20,789

 

762
00:25:20,789 --> 00:25:23,350

 

763
00:25:23,350 --> 00:25:23,360

 

764
00:25:23,360 --> 00:25:24,149


765
00:25:24,149 --> 00:25:27,510

 

766
00:25:27,510 --> 00:25:27,520

 

767
00:25:27,520 --> 00:25:28,630


768
00:25:28,630 --> 00:25:28,640

 

769
00:25:28,640 --> 00:25:29,909


770
00:25:29,909 --> 00:25:31,590

 

771
00:25:31,590 --> 00:25:31,600

 

772
00:25:31,600 --> 00:25:33,510


773
00:25:33,510 --> 00:25:36,390

 

774
00:25:36,390 --> 00:25:39,830

 

775
00:25:39,830 --> 00:25:45,190

 

776
00:25:45,190 --> 00:25:48,789

 

777
00:25:48,789 --> 00:25:49,990

 

778
00:25:49,990 --> 00:25:52,549

 

779
00:25:52,549 --> 00:25:53,669

 

780
00:25:53,669 --> 00:25:54,710

 

781
00:25:54,710 --> 00:25:58,390

 

782
00:25:58,390 --> 00:25:58,400

 

783
00:25:58,400 --> 00:25:59,990


784
00:25:59,990 --> 00:26:04,310

 

785
00:26:04,310 --> 00:26:06,310

 

786
00:26:06,310 --> 00:26:06,320

 

787
00:26:06,320 --> 00:26:07,750


788
00:26:07,750 --> 00:26:10,710

 

789
00:26:10,710 --> 00:26:12,630

 

790
00:26:12,630 --> 00:26:13,669

 

791
00:26:13,669 --> 00:26:13,679

 

792
00:26:13,679 --> 00:26:16,060


793
00:26:16,060 --> 00:26:16,070

 

794
00:26:16,070 --> 00:26:18,710


795
00:26:18,710 --> 00:26:21,430

 

796
00:26:21,430 --> 00:26:23,510

 

797
00:26:23,510 --> 00:26:26,230

 

798
00:26:26,230 --> 00:26:28,390

 

799
00:26:28,390 --> 00:26:29,669

 

800
00:26:29,669 --> 00:26:32,470

 

801
00:26:32,470 --> 00:26:35,990

 

802
00:26:35,990 --> 00:26:37,990

 

803
00:26:37,990 --> 00:26:41,430

 

804
00:26:41,430 --> 00:26:43,669

 

805
00:26:43,669 --> 00:26:46,149

 

806
00:26:46,149 --> 00:26:47,990

 

807
00:26:47,990 --> 00:26:49,669

 

808
00:26:49,669 --> 00:26:51,430

 

809
00:26:51,430 --> 00:26:53,190

 

810
00:26:53,190 --> 00:26:56,230

 

811
00:26:56,230 --> 00:26:58,390

 

812
00:26:58,390 --> 00:27:01,909

 

813
00:27:01,909 --> 00:27:01,919

 

814
00:27:01,919 --> 00:27:03,029


815
00:27:03,029 --> 00:27:05,190

 

816
00:27:05,190 --> 00:27:06,470

 

817
00:27:06,470 --> 00:27:06,480

 

818
00:27:06,480 --> 00:27:07,269


819
00:27:07,269 --> 00:27:10,390

 

820
00:27:10,390 --> 00:27:13,269

 

821
00:27:13,269 --> 00:27:14,789

 

822
00:27:14,789 --> 00:27:17,590

 

823
00:27:17,590 --> 00:27:19,350

 

824
00:27:19,350 --> 00:27:20,389

 

825
00:27:20,389 --> 00:27:22,630

 

826
00:27:22,630 --> 00:27:25,350

 

827
00:27:25,350 --> 00:27:27,669

 

828
00:27:27,669 --> 00:27:29,669

 

829
00:27:29,669 --> 00:27:29,679

 

830
00:27:29,679 --> 00:27:30,630


831
00:27:30,630 --> 00:27:30,640

 

832
00:27:30,640 --> 00:27:31,510


833
00:27:31,510 --> 00:27:33,029

 

834
00:27:33,029 --> 00:27:35,750

 

835
00:27:35,750 --> 00:27:37,590

 

836
00:27:37,590 --> 00:27:38,870

 

837
00:27:38,870 --> 00:27:41,029

 

838
00:27:41,029 --> 00:27:42,789

 

839
00:27:42,789 --> 00:27:44,389

 

840
00:27:44,389 --> 00:27:47,190

 

841
00:27:47,190 --> 00:27:49,750

 

842
00:27:49,750 --> 00:27:51,830

 

843
00:27:51,830 --> 00:27:55,590

 

844
00:27:55,590 --> 00:27:57,269

 

845
00:27:57,269 --> 00:27:59,430

 

846
00:27:59,430 --> 00:28:01,909

 

847
00:28:01,909 --> 00:28:04,310

 

848
00:28:04,310 --> 00:28:07,029

 

849
00:28:07,029 --> 00:28:08,549

 

850
00:28:08,549 --> 00:28:10,470

 

851
00:28:10,470 --> 00:28:10,480

 

852
00:28:10,480 --> 00:28:13,590


853
00:28:13,590 --> 00:28:14,830

 

854
00:28:14,830 --> 00:28:21,909

 

855
00:28:21,909 --> 00:28:23,750

 

856
00:28:23,750 --> 00:28:25,510

 

857
00:28:25,510 --> 00:28:27,590

 

858
00:28:27,590 --> 00:28:30,470

 

859
00:28:30,470 --> 00:28:34,389

 

860
00:28:34,389 --> 00:28:37,269

 

861
00:28:37,269 --> 00:28:37,279

 

862
00:28:37,279 --> 00:28:38,310


863
00:28:38,310 --> 00:28:41,269

 

864
00:28:41,269 --> 00:28:41,279

 

865
00:28:41,279 --> 00:28:42,870


866
00:28:42,870 --> 00:28:47,110

 

867
00:28:47,110 --> 00:28:47,120

 

868
00:28:47,120 --> 00:28:47,909


869
00:28:47,909 --> 00:28:49,510

 

870
00:28:49,510 --> 00:28:51,269

 

871
00:28:51,269 --> 00:28:53,590

 

872
00:28:53,590 --> 00:28:55,669

 

873
00:28:55,669 --> 00:28:58,870

 

874
00:28:58,870 --> 00:28:58,880

 

875
00:28:58,880 --> 00:28:59,669


876
00:28:59,669 --> 00:29:01,029

 

877
00:29:01,029 --> 00:29:03,269

 

878
00:29:03,269 --> 00:29:03,279

 

879
00:29:03,279 --> 00:29:04,950


880
00:29:04,950 --> 00:29:04,960

 

881
00:29:04,960 --> 00:29:05,990


882
00:29:05,990 --> 00:29:09,029

 

883
00:29:09,029 --> 00:29:13,350

 

884
00:29:13,350 --> 00:29:15,190

 

885
00:29:15,190 --> 00:29:16,710

 

886
00:29:16,710 --> 00:29:16,720

 

887
00:29:16,720 --> 00:29:17,909


888
00:29:17,909 --> 00:29:19,669

 

889
00:29:19,669 --> 00:29:21,350

 

890
00:29:21,350 --> 00:29:23,350

 

891
00:29:23,350 --> 00:29:26,230

 

892
00:29:26,230 --> 00:29:28,549

 

893
00:29:28,549 --> 00:29:30,870

 

894
00:29:30,870 --> 00:29:34,870

 

895
00:29:34,870 --> 00:29:36,070

 

896
00:29:36,070 --> 00:29:38,230

 

897
00:29:38,230 --> 00:29:38,240

 

898
00:29:38,240 --> 00:29:39,350


899
00:29:39,350 --> 00:29:41,110

 

900
00:29:41,110 --> 00:29:41,120

 

901
00:29:41,120 --> 00:29:42,549


902
00:29:42,549 --> 00:29:42,559

 

903
00:29:42,559 --> 00:29:43,669


904
00:29:43,669 --> 00:29:46,230

 

905
00:29:46,230 --> 00:29:48,149

 

906
00:29:48,149 --> 00:29:49,830

 

907
00:29:49,830 --> 00:29:51,669

 

908
00:29:51,669 --> 00:29:53,510

 

909
00:29:53,510 --> 00:29:57,510

 

910
00:29:57,510 --> 00:29:57,520

 

911
00:29:57,520 --> 00:29:58,389


912
00:29:58,389 --> 00:30:00,950

 

913
00:30:00,950 --> 00:30:04,870

 

914
00:30:04,870 --> 00:30:10,230

 

915
00:30:10,230 --> 00:30:11,350

 

916
00:30:11,350 --> 00:30:13,830

 

917
00:30:13,830 --> 00:30:13,840

 

918
00:30:13,840 --> 00:30:16,470


919
00:30:16,470 --> 00:30:18,149

 

920
00:30:18,149 --> 00:30:19,830

 

921
00:30:19,830 --> 00:30:21,590

 

922
00:30:21,590 --> 00:30:24,070

 

923
00:30:24,070 --> 00:30:26,149

 

924
00:30:26,149 --> 00:30:28,389

 

925
00:30:28,389 --> 00:30:30,950

 

926
00:30:30,950 --> 00:30:32,389

 

927
00:30:32,389 --> 00:30:34,630

 

928
00:30:34,630 --> 00:30:34,640

 

929
00:30:34,640 --> 00:30:35,669


930
00:30:35,669 --> 00:30:38,070

 

931
00:30:38,070 --> 00:30:39,350

 

932
00:30:39,350 --> 00:30:41,510

 

933
00:30:41,510 --> 00:30:43,029

 

934
00:30:43,029 --> 00:30:43,039

 

935
00:30:43,039 --> 00:30:44,789


936
00:30:44,789 --> 00:30:44,799

 

937
00:30:44,799 --> 00:30:45,669


938
00:30:45,669 --> 00:30:47,669

 

939
00:30:47,669 --> 00:30:50,389

 

940
00:30:50,389 --> 00:30:53,110

 

941
00:30:53,110 --> 00:30:55,750

 

942
00:30:55,750 --> 00:30:58,310

 

943
00:30:58,310 --> 00:31:01,190

 

944
00:31:01,190 --> 00:31:03,590

 

945
00:31:03,590 --> 00:31:05,909

 

946
00:31:05,909 --> 00:31:08,789

 

947
00:31:08,789 --> 00:31:11,430

 

948
00:31:11,430 --> 00:31:13,029

 

949
00:31:13,029 --> 00:31:13,039

 

950
00:31:13,039 --> 00:31:14,389


951
00:31:14,389 --> 00:31:17,110

 

952
00:31:17,110 --> 00:31:19,110

 

953
00:31:19,110 --> 00:31:20,789

 

954
00:31:20,789 --> 00:31:20,799

 

955
00:31:20,799 --> 00:31:22,789


956
00:31:22,789 --> 00:31:25,350

 

957
00:31:25,350 --> 00:31:27,110

 

958
00:31:27,110 --> 00:31:28,789

 

959
00:31:28,789 --> 00:31:31,269

 

960
00:31:31,269 --> 00:31:33,590

 

961
00:31:33,590 --> 00:31:35,110

 

962
00:31:35,110 --> 00:31:36,950

 

963
00:31:36,950 --> 00:31:39,190

 

964
00:31:39,190 --> 00:31:41,029

 

965
00:31:41,029 --> 00:31:42,549

 

966
00:31:42,549 --> 00:31:44,549

 

967
00:31:44,549 --> 00:31:46,549

 

968
00:31:46,549 --> 00:31:48,149

 

969
00:31:48,149 --> 00:31:51,190

 

970
00:31:51,190 --> 00:31:53,669

 

971
00:31:53,669 --> 00:31:55,669

 

972
00:31:55,669 --> 00:31:58,549

 

973
00:31:58,549 --> 00:32:01,269

 

974
00:32:01,269 --> 00:32:01,279

 

975
00:32:01,279 --> 00:32:03,430


976
00:32:03,430 --> 00:32:05,269

 

977
00:32:05,269 --> 00:32:06,710

 

978
00:32:06,710 --> 00:32:08,149

 

979
00:32:08,149 --> 00:32:10,230

 

980
00:32:10,230 --> 00:32:12,710

 

981
00:32:12,710 --> 00:32:14,230

 

982
00:32:14,230 --> 00:32:15,590

 

983
00:32:15,590 --> 00:32:17,110

 

984
00:32:17,110 --> 00:32:20,950

 

985
00:32:20,950 --> 00:32:23,990

 

986
00:32:23,990 --> 00:32:25,990

 

987
00:32:25,990 --> 00:32:27,830

 

988
00:32:27,830 --> 00:32:31,110

 

989
00:32:31,110 --> 00:32:33,110

 

990
00:32:33,110 --> 00:32:36,950

 

991
00:32:36,950 --> 00:32:38,630

 

992
00:32:38,630 --> 00:32:40,830

 

993
00:32:40,830 --> 00:32:43,029

 

994
00:32:43,029 --> 00:32:45,350

 

995
00:32:45,350 --> 00:32:46,950

 

996
00:32:46,950 --> 00:32:51,509

 

997
00:32:51,509 --> 00:32:51,519

 

998
00:32:51,519 --> 00:32:52,870


999
00:32:52,870 --> 00:32:55,750

 

1000
00:32:55,750 --> 00:32:57,350

 

1001
00:32:57,350 --> 00:32:58,710

 

1002
00:32:58,710 --> 00:32:59,830

 

1003
00:32:59,830 --> 00:33:02,149

 

1004
00:33:02,149 --> 00:33:04,310

 

1005
00:33:04,310 --> 00:33:07,509

 

1006
00:33:07,509 --> 00:33:08,870

 

1007
00:33:08,870 --> 00:33:10,630

 

1008
00:33:10,630 --> 00:33:10,640

 

1009
00:33:10,640 --> 00:33:12,549


1010
00:33:12,549 --> 00:33:12,559

 

1011
00:33:12,559 --> 00:33:14,389


1012
00:33:14,389 --> 00:33:15,830

 

1013
00:33:15,830 --> 00:33:18,149

 

1014
00:33:18,149 --> 00:33:20,310

 

1015
00:33:20,310 --> 00:33:23,029

 

1016
00:33:23,029 --> 00:33:25,190

 

1017
00:33:25,190 --> 00:33:27,669

 

1018
00:33:27,669 --> 00:33:29,750

 

1019
00:33:29,750 --> 00:33:32,070

 

1020
00:33:32,070 --> 00:33:33,669

 

1021
00:33:33,669 --> 00:33:35,509

 

1022
00:33:35,509 --> 00:33:36,630

 

1023
00:33:36,630 --> 00:33:39,110

 

1024
00:33:39,110 --> 00:33:41,509

 

1025
00:33:41,509 --> 00:33:41,519

 

1026
00:33:41,519 --> 00:33:43,190


1027
00:33:43,190 --> 00:33:45,350

 

1028
00:33:45,350 --> 00:33:45,360

 

1029
00:33:45,360 --> 00:33:46,389


1030
00:33:46,389 --> 00:33:49,029

 

1031
00:33:49,029 --> 00:33:50,549

 

1032
00:33:50,549 --> 00:33:53,190

 

1033
00:33:53,190 --> 00:33:54,789

 

1034
00:33:54,789 --> 00:33:57,110

 

1035
00:33:57,110 --> 00:34:00,230

 

1036
00:34:00,230 --> 00:34:02,149

 

1037
00:34:02,149 --> 00:34:04,070

 

1038
00:34:04,070 --> 00:34:07,430

 

1039
00:34:07,430 --> 00:34:09,030

 

1040
00:34:09,030 --> 00:34:11,030

 

1041
00:34:11,030 --> 00:34:11,040

 

1042
00:34:11,040 --> 00:34:12,470


1043
00:34:12,470 --> 00:34:14,550

 

1044
00:34:14,550 --> 00:34:16,310

 

1045
00:34:16,310 --> 00:34:18,550

 

1046
00:34:18,550 --> 00:34:19,829

 

1047
00:34:19,829 --> 00:34:21,349

 

1048
00:34:21,349 --> 00:34:21,359

 

1049
00:34:21,359 --> 00:34:22,230


1050
00:34:22,230 --> 00:34:25,349

 

1051
00:34:25,349 --> 00:34:27,430

 

1052
00:34:27,430 --> 00:34:29,109

 

1053
00:34:29,109 --> 00:34:31,270

 

1054
00:34:31,270 --> 00:34:33,430

 

1055
00:34:33,430 --> 00:34:35,270

 

1056
00:34:35,270 --> 00:34:37,990

 

1057
00:34:37,990 --> 00:34:40,950

 

1058
00:34:40,950 --> 00:34:43,669

 

1059
00:34:43,669 --> 00:34:45,190

 

1060
00:34:45,190 --> 00:34:46,790

 

1061
00:34:46,790 --> 00:34:48,710

 

1062
00:34:48,710 --> 00:34:50,790

 

1063
00:34:50,790 --> 00:34:53,589

 

1064
00:34:53,589 --> 00:34:55,430

 

1065
00:34:55,430 --> 00:34:58,550

 

1066
00:34:58,550 --> 00:34:59,990

 

1067
00:34:59,990 --> 00:35:02,710

 

1068
00:35:02,710 --> 00:35:05,030

 

1069
00:35:05,030 --> 00:35:07,670

 

1070
00:35:07,670 --> 00:35:09,190

 

1071
00:35:09,190 --> 00:35:11,430

 

1072
00:35:11,430 --> 00:35:12,950

 

1073
00:35:12,950 --> 00:35:14,310

 

1074
00:35:14,310 --> 00:35:16,550

 

1075
00:35:16,550 --> 00:35:16,560

 

1076
00:35:16,560 --> 00:35:17,829


1077
00:35:17,829 --> 00:35:20,630

 

1078
00:35:20,630 --> 00:35:23,430

 

1079
00:35:23,430 --> 00:35:26,950

 

1080
00:35:26,950 --> 00:35:28,630

 

1081
00:35:28,630 --> 00:35:31,109

 

1082
00:35:31,109 --> 00:35:34,550

 

1083
00:35:34,550 --> 00:35:38,150

 

1084
00:35:38,150 --> 00:35:40,710

 

1085
00:35:40,710 --> 00:35:42,870

 

1086
00:35:42,870 --> 00:35:44,950

 

1087
00:35:44,950 --> 00:35:44,960

 

1088
00:35:44,960 --> 00:35:46,470


1089
00:35:46,470 --> 00:35:47,910

 

1090
00:35:47,910 --> 00:35:49,430

 

1091
00:35:49,430 --> 00:35:51,510

 

1092
00:35:51,510 --> 00:35:55,589

 

1093
00:35:55,589 --> 00:35:57,750

 

1094
00:35:57,750 --> 00:35:59,910

 

1095
00:35:59,910 --> 00:36:02,310

 

1096
00:36:02,310 --> 00:36:04,390

 

1097
00:36:04,390 --> 00:36:07,030

 

1098
00:36:07,030 --> 00:36:09,190

 

1099
00:36:09,190 --> 00:36:10,950

 

1100
00:36:10,950 --> 00:36:12,950

 

1101
00:36:12,950 --> 00:36:12,960

 

1102
00:36:12,960 --> 00:36:14,150


1103
00:36:14,150 --> 00:36:16,150

 

1104
00:36:16,150 --> 00:36:17,829

 

1105
00:36:17,829 --> 00:36:20,069

 

1106
00:36:20,069 --> 00:36:21,829

 

1107
00:36:21,829 --> 00:36:25,030

 

1108
00:36:25,030 --> 00:36:27,270

 

1109
00:36:27,270 --> 00:36:29,670

 

1110
00:36:29,670 --> 00:36:31,589

 

1111
00:36:31,589 --> 00:36:33,430

 

1112
00:36:33,430 --> 00:36:36,630

 

1113
00:36:36,630 --> 00:36:37,990

 

1114
00:36:37,990 --> 00:36:40,069

 

1115
00:36:40,069 --> 00:36:42,230

 

1116
00:36:42,230 --> 00:36:45,270

 

1117
00:36:45,270 --> 00:36:45,280

 

1118
00:36:45,280 --> 00:36:46,630


1119
00:36:46,630 --> 00:36:48,230

 

1120
00:36:48,230 --> 00:36:51,750

 

1121
00:36:51,750 --> 00:36:53,349

 

1122
00:36:53,349 --> 00:36:55,349

 

1123
00:36:55,349 --> 00:36:57,750

 

1124
00:36:57,750 --> 00:37:00,870

 

1125
00:37:00,870 --> 00:37:00,880

 

1126
00:37:00,880 --> 00:37:08,550


1127
00:37:08,550 --> 00:37:10,390

 

1128
00:37:10,390 --> 00:37:10,400

 

1129
00:37:10,400 --> 00:37:11,829


1130
00:37:11,829 --> 00:37:11,839

 

1131
00:37:11,839 --> 00:37:13,270


1132
00:37:13,270 --> 00:37:13,280

 

1133
00:37:13,280 --> 00:37:15,430


1134
00:37:15,430 --> 00:37:15,440

 

1135
00:37:15,440 --> 00:37:16,230


1136
00:37:16,230 --> 00:37:17,829

 

1137
00:37:17,829 --> 00:37:17,839

 

1138
00:37:17,839 --> 00:37:20,310


1139
00:37:20,310 --> 00:37:21,990

 

1140
00:37:21,990 --> 00:37:23,349

 

1141
00:37:23,349 --> 00:37:25,030

 

1142
00:37:25,030 --> 00:37:26,390

 

1143
00:37:26,390 --> 00:37:28,710

 

1144
00:37:28,710 --> 00:37:29,990

 

1145
00:37:29,990 --> 00:37:32,069

 

1146
00:37:32,069 --> 00:37:34,870

 

1147
00:37:34,870 --> 00:37:34,880

 

1148
00:37:34,880 --> 00:37:36,790


1149
00:37:36,790 --> 00:37:36,800

 

1150
00:37:36,800 --> 00:37:38,870


1151
00:37:38,870 --> 00:37:40,390

 

1152
00:37:40,390 --> 00:37:42,470

 

1153
00:37:42,470 --> 00:37:45,510

 

1154
00:37:45,510 --> 00:37:47,829

 

1155
00:37:47,829 --> 00:37:50,390

 

1156
00:37:50,390 --> 00:37:51,829

 

1157
00:37:51,829 --> 00:37:53,270

 

1158
00:37:53,270 --> 00:37:56,069

 

1159
00:37:56,069 --> 00:37:57,829

 

1160
00:37:57,829 --> 00:37:59,589

 

1161
00:37:59,589 --> 00:38:01,430

 

1162
00:38:01,430 --> 00:38:04,069

 

1163
00:38:04,069 --> 00:38:05,589

 

1164
00:38:05,589 --> 00:38:07,829

 

1165
00:38:07,829 --> 00:38:09,510

 

1166
00:38:09,510 --> 00:38:12,310

 

1167
00:38:12,310 --> 00:38:14,390

 

1168
00:38:14,390 --> 00:38:16,069

 

1169
00:38:16,069 --> 00:38:17,910

 

1170
00:38:17,910 --> 00:38:19,270

 

1171
00:38:19,270 --> 00:38:21,190

 

1172
00:38:21,190 --> 00:38:21,200

 

1173
00:38:21,200 --> 00:38:22,150


1174
00:38:22,150 --> 00:38:24,150

 

1175
00:38:24,150 --> 00:38:25,910

 

1176
00:38:25,910 --> 00:38:28,230

 

1177
00:38:28,230 --> 00:38:30,230

 

1178
00:38:30,230 --> 00:38:31,510

 

1179
00:38:31,510 --> 00:38:34,390

 

1180
00:38:34,390 --> 00:38:37,109

 

1181
00:38:37,109 --> 00:38:39,510

 

1182
00:38:39,510 --> 00:38:39,520

 

1183
00:38:39,520 --> 00:38:41,030


1184
00:38:41,030 --> 00:38:43,349

 

1185
00:38:43,349 --> 00:38:43,359

 

1186
00:38:43,359 --> 00:38:45,109


1187
00:38:45,109 --> 00:38:45,119

 

1188
00:38:45,119 --> 00:38:46,470


1189
00:38:46,470 --> 00:38:48,310

 

1190
00:38:48,310 --> 00:38:51,270

 

1191
00:38:51,270 --> 00:38:51,280

 

1192
00:38:51,280 --> 00:38:52,470


1193
00:38:52,470 --> 00:38:55,829

 

1194
00:38:55,829 --> 00:38:58,069

 

1195
00:38:58,069 --> 00:39:00,550

 

1196
00:39:00,550 --> 00:39:00,560

 

1197
00:39:00,560 --> 00:39:02,470


1198
00:39:02,470 --> 00:39:02,480

 

1199
00:39:02,480 --> 00:39:03,349


1200
00:39:03,349 --> 00:39:19,910

 

1201
00:39:19,910 --> 00:39:19,920

 

1202
00:39:19,920 --> 00:39:21,190


1203
00:39:21,190 --> 00:39:23,109

 

1204
00:39:23,109 --> 00:39:25,910

 

1205
00:39:25,910 --> 00:39:28,710

 

1206
00:39:28,710 --> 00:39:28,720

 

1207
00:39:28,720 --> 00:39:29,589


1208
00:39:29,589 --> 00:39:29,599

 

1209
00:39:29,599 --> 00:39:30,040


1210
00:39:30,040 --> 00:39:30,050

 

1211
00:39:30,050 --> 00:39:31,270


1212
00:39:31,270 --> 00:39:33,030

 

1213
00:39:33,030 --> 00:39:36,310

 

1214
00:39:36,310 --> 00:39:39,349

 

1215
00:39:39,349 --> 00:39:39,359

 

1216
00:39:39,359 --> 00:39:40,829


1217
00:39:40,829 --> 00:39:44,870

 

1218
00:39:44,870 --> 00:39:47,190

 

1219
00:39:47,190 --> 00:39:48,710

 

1220
00:39:48,710 --> 00:39:51,190

 

1221
00:39:51,190 --> 00:39:51,200

 

1222
00:39:51,200 --> 00:39:54,829


1223
00:39:54,829 --> 00:39:57,510

 

1224
00:39:57,510 --> 00:39:57,520

 

1225
00:39:57,520 --> 00:39:58,390


1226
00:39:58,390 --> 00:40:00,470

 

1227
00:40:00,470 --> 00:40:00,480

 

1228
00:40:00,480 --> 00:40:02,150


1229
00:40:02,150 --> 00:40:04,630

 

1230
00:40:04,630 --> 00:40:06,069

 

1231
00:40:06,069 --> 00:40:08,630

 

1232
00:40:08,630 --> 00:40:10,390

 

1233
00:40:10,390 --> 00:40:12,550

 

1234
00:40:12,550 --> 00:40:14,230

 

1235
00:40:14,230 --> 00:40:16,550

 

1236
00:40:16,550 --> 00:40:19,190

 

1237
00:40:19,190 --> 00:40:20,790

 

1238
00:40:20,790 --> 00:40:22,230

 

1239
00:40:22,230 --> 00:40:25,589

 

1240
00:40:25,589 --> 00:40:25,599

 

1241
00:40:25,599 --> 00:40:26,790


1242
00:40:26,790 --> 00:40:28,230

 

1243
00:40:28,230 --> 00:40:30,550

 

1244
00:40:30,550 --> 00:40:33,510

 

1245
00:40:33,510 --> 00:40:35,990

 

1246
00:40:35,990 --> 00:40:37,030

 

1247
00:40:37,030 --> 00:40:40,150

 

1248
00:40:40,150 --> 00:40:40,160

 

1249
00:40:40,160 --> 00:40:41,589


1250
00:40:41,589 --> 00:40:41,599

 

1251
00:40:41,599 --> 00:40:43,430


1252
00:40:43,430 --> 00:40:44,870

 

1253
00:40:44,870 --> 00:40:46,870

 

1254
00:40:46,870 --> 00:40:48,950

 

1255
00:40:48,950 --> 00:40:50,470

 

1256
00:40:50,470 --> 00:40:52,710

 

1257
00:40:52,710 --> 00:40:55,030

 

1258
00:40:55,030 --> 00:40:57,510

 

1259
00:40:57,510 --> 00:40:59,910

 

1260
00:40:59,910 --> 00:41:03,990

 

1261
00:41:03,990 --> 00:41:04,000

 

1262
00:41:04,000 --> 00:41:04,950


1263
00:41:04,950 --> 00:41:07,430

 

1264
00:41:07,430 --> 00:41:07,440

 

1265
00:41:07,440 --> 00:41:08,230


1266
00:41:08,230 --> 00:41:08,240

 

1267
00:41:08,240 --> 00:41:09,349


1268
00:41:09,349 --> 00:41:09,359

 

1269
00:41:09,359 --> 00:41:11,430


1270
00:41:11,430 --> 00:41:11,440

 

1271
00:41:11,440 --> 00:41:12,470


1272
00:41:12,470 --> 00:41:14,309

 

1273
00:41:14,309 --> 00:41:14,319

 

1274
00:41:14,319 --> 00:41:15,750


1275
00:41:15,750 --> 00:41:15,760

 

1276
00:41:15,760 --> 00:41:16,550


1277
00:41:16,550 --> 00:41:17,750

 

1278
00:41:17,750 --> 00:41:17,760

 

1279
00:41:17,760 --> 00:41:18,710


1280
00:41:18,710 --> 00:41:21,750

 

1281
00:41:21,750 --> 00:41:25,270

 

1282
00:41:25,270 --> 00:41:27,589

 

1283
00:41:27,589 --> 00:41:30,150

 

1284
00:41:30,150 --> 00:41:32,390

 

1285
00:41:32,390 --> 00:41:34,150

 

1286
00:41:34,150 --> 00:41:36,470

 

1287
00:41:36,470 --> 00:41:38,630

 

1288
00:41:38,630 --> 00:41:40,390

 

1289
00:41:40,390 --> 00:41:43,670

 

1290
00:41:43,670 --> 00:41:47,190

 

1291
00:41:47,190 --> 00:41:47,200

 

1292
00:41:47,200 --> 00:41:49,910


1293
00:41:49,910 --> 00:41:52,309

 

1294
00:41:52,309 --> 00:41:53,990

 

1295
00:41:53,990 --> 00:41:55,990

 

1296
00:41:55,990 --> 00:41:57,990

 

1297
00:41:57,990 --> 00:42:00,230

 

1298
00:42:00,230 --> 00:42:03,270

 

1299
00:42:03,270 --> 00:42:04,790

 

1300
00:42:04,790 --> 00:42:04,800

 

1301
00:42:04,800 --> 00:42:05,910


1302
00:42:05,910 --> 00:42:05,920

 

1303
00:42:05,920 --> 00:42:06,950


1304
00:42:06,950 --> 00:42:06,960

 

1305
00:42:06,960 --> 00:42:07,829


1306
00:42:07,829 --> 00:42:10,470

 

1307
00:42:10,470 --> 00:42:13,510

 

1308
00:42:13,510 --> 00:42:17,670

 

1309
00:42:17,670 --> 00:42:19,670

 

1310
00:42:19,670 --> 00:42:19,680

 

1311
00:42:19,680 --> 00:42:20,550


1312
00:42:20,550 --> 00:42:22,550

 

1313
00:42:22,550 --> 00:42:23,910

 

1314
00:42:23,910 --> 00:42:24,870

 

1315
00:42:24,870 --> 00:42:26,790

 

1316
00:42:26,790 --> 00:42:28,829

 

1317
00:42:28,829 --> 00:42:31,349

 

1318
00:42:31,349 --> 00:42:34,069

 

1319
00:42:34,069 --> 00:42:37,190

 

1320
00:42:37,190 --> 00:42:39,910

 

1321
00:42:39,910 --> 00:42:41,430

 

1322
00:42:41,430 --> 00:42:42,870

 

1323
00:42:42,870 --> 00:42:44,710

 

1324
00:42:44,710 --> 00:42:47,030

 

1325
00:42:47,030 --> 00:42:49,510

 

1326
00:42:49,510 --> 00:42:51,270

 

1327
00:42:51,270 --> 00:42:53,190

 

1328
00:42:53,190 --> 00:42:54,870

 

1329
00:42:54,870 --> 00:42:54,880

 

1330
00:42:54,880 --> 00:42:55,910


1331
00:42:55,910 --> 00:42:58,870

 

1332
00:42:58,870 --> 00:43:00,550

 

1333
00:43:00,550 --> 00:43:03,190

 

1334
00:43:03,190 --> 00:43:04,790

 

1335
00:43:04,790 --> 00:43:06,550

 

1336
00:43:06,550 --> 00:43:08,790

 

1337
00:43:08,790 --> 00:43:08,800

 

1338
00:43:08,800 --> 00:43:09,589


1339
00:43:09,589 --> 00:43:12,390

 

1340
00:43:12,390 --> 00:43:14,790

 

1341
00:43:14,790 --> 00:43:16,710

 

1342
00:43:16,710 --> 00:43:18,630

 

1343
00:43:18,630 --> 00:43:21,430

 

1344
00:43:21,430 --> 00:43:23,270

 

1345
00:43:23,270 --> 00:43:25,829

 

1346
00:43:25,829 --> 00:43:27,910

 

1347
00:43:27,910 --> 00:43:29,430

 

1348
00:43:29,430 --> 00:43:30,870

 

1349
00:43:30,870 --> 00:43:30,880

 

1350
00:43:30,880 --> 00:43:32,230


1351
00:43:32,230 --> 00:43:32,240

 

1352
00:43:32,240 --> 00:43:32,580


1353
00:43:32,580 --> 00:43:32,590

 

1354
00:43:32,590 --> 00:43:34,470


1355
00:43:34,470 --> 00:43:37,109

 

1356
00:43:37,109 --> 00:43:39,910

 

1357
00:43:39,910 --> 00:43:39,920

 

1358
00:43:39,920 --> 00:43:41,109


1359
00:43:41,109 --> 00:43:43,349

 

1360
00:43:43,349 --> 00:43:45,270

 

1361
00:43:45,270 --> 00:43:46,630

 

1362
00:43:46,630 --> 00:43:49,990

 

1363
00:43:49,990 --> 00:43:50,000

 

1364
00:43:50,000 --> 00:43:52,829


1365
00:43:52,829 --> 00:43:55,670

 

1366
00:43:55,670 --> 00:43:57,750

 

1367
00:43:57,750 --> 00:44:00,150

 

1368
00:44:00,150 --> 00:44:02,470

 

1369
00:44:02,470 --> 00:44:04,069

 

1370
00:44:04,069 --> 00:44:06,950

 

1371
00:44:06,950 --> 00:44:09,990

 

1372
00:44:09,990 --> 00:44:13,270

 

1373
00:44:13,270 --> 00:44:15,589

 

1374
00:44:15,589 --> 00:44:17,589

 

1375
00:44:17,589 --> 00:44:20,230

 

1376
00:44:20,230 --> 00:44:21,829

 

1377
00:44:21,829 --> 00:44:23,270

 

1378
00:44:23,270 --> 00:44:26,710

 

1379
00:44:26,710 --> 00:44:29,670

 

1380
00:44:29,670 --> 00:44:33,270

 

1381
00:44:33,270 --> 00:44:34,950

 

1382
00:44:34,950 --> 00:44:37,349

 

1383
00:44:37,349 --> 00:44:38,870

 

1384
00:44:38,870 --> 00:44:38,880

 

1385
00:44:38,880 --> 00:44:39,670


1386
00:44:39,670 --> 00:44:41,510

 

1387
00:44:41,510 --> 00:44:43,510

 

1388
00:44:43,510 --> 00:44:43,520

 

1389
00:44:43,520 --> 00:44:44,390


1390
00:44:44,390 --> 00:44:46,630

 

1391
00:44:46,630 --> 00:44:48,309

 

1392
00:44:48,309 --> 00:44:50,390

 

1393
00:44:50,390 --> 00:44:55,109

 

1394
00:44:55,109 --> 00:44:57,990

 

1395
00:44:57,990 --> 00:45:00,309

 

1396
00:45:00,309 --> 00:45:02,390

 

1397
00:45:02,390 --> 00:45:03,829

 

1398
00:45:03,829 --> 00:45:05,829

 

1399
00:45:05,829 --> 00:45:07,910

 

1400
00:45:07,910 --> 00:45:09,829

 

1401
00:45:09,829 --> 00:45:11,990

 

1402
00:45:11,990 --> 00:45:13,430

 

1403
00:45:13,430 --> 00:45:14,950

 

1404
00:45:14,950 --> 00:45:16,710

 

1405
00:45:16,710 --> 00:45:18,870

 

1406
00:45:18,870 --> 00:45:21,190

 

1407
00:45:21,190 --> 00:45:23,670

 

1408
00:45:23,670 --> 00:45:25,750

 

1409
00:45:25,750 --> 00:45:27,670

 

1410
00:45:27,670 --> 00:45:29,109

 

1411
00:45:29,109 --> 00:45:30,390

 

1412
00:45:30,390 --> 00:45:32,150

 

1413
00:45:32,150 --> 00:45:34,069

 

1414
00:45:34,069 --> 00:45:35,750

 

1415
00:45:35,750 --> 00:45:35,760

 

1416
00:45:35,760 --> 00:45:37,829


1417
00:45:37,829 --> 00:45:37,839

 

1418
00:45:37,839 --> 00:45:40,550


1419
00:45:40,550 --> 00:45:43,109

 

1420
00:45:43,109 --> 00:45:45,430

 

1421
00:45:45,430 --> 00:45:48,150

 

1422
00:45:48,150 --> 00:45:50,230

 

1423
00:45:50,230 --> 00:45:52,630

 

1424
00:45:52,630 --> 00:45:54,550

 

1425
00:45:54,550 --> 00:45:56,870

 

1426
00:45:56,870 --> 00:45:58,790

 

1427
00:45:58,790 --> 00:46:00,870

 

1428
00:46:00,870 --> 00:46:02,630

 

1429
00:46:02,630 --> 00:46:04,950

 

1430
00:46:04,950 --> 00:46:04,960

 

1431
00:46:04,960 --> 00:46:06,150


1432
00:46:06,150 --> 00:46:07,510

 

1433
00:46:07,510 --> 00:46:07,520

 

1434
00:46:07,520 --> 00:46:09,109


1435
00:46:09,109 --> 00:46:09,119

 

1436
00:46:09,119 --> 00:46:10,550


1437
00:46:10,550 --> 00:46:11,750

 

1438
00:46:11,750 --> 00:46:13,510

 

1439
00:46:13,510 --> 00:46:13,520

 

1440
00:46:13,520 --> 00:46:14,950


1441
00:46:14,950 --> 00:46:17,510

 

1442
00:46:17,510 --> 00:46:19,589

 

1443
00:46:19,589 --> 00:46:23,030

 

1444
00:46:23,030 --> 00:46:24,790

 

1445
00:46:24,790 --> 00:46:27,430

 

1446
00:46:27,430 --> 00:46:28,630

 

1447
00:46:28,630 --> 00:46:30,390

 

1448
00:46:30,390 --> 00:46:32,470

 

1449
00:46:32,470 --> 00:46:34,950

 

1450
00:46:34,950 --> 00:46:34,960

 

1451
00:46:34,960 --> 00:46:37,829


1452
00:46:37,829 --> 00:46:37,839

 

1453
00:46:37,839 --> 00:46:38,710


1454
00:46:38,710 --> 00:46:38,720

 

1455
00:46:38,720 --> 00:46:41,430


1456
00:46:41,430 --> 00:46:43,270

 

1457
00:46:43,270 --> 00:46:45,750

 

1458
00:46:45,750 --> 00:46:47,910

 

1459
00:46:47,910 --> 00:46:50,630

 

1460
00:46:50,630 --> 00:46:53,349

 

1461
00:46:53,349 --> 00:46:55,430

 

1462
00:46:55,430 --> 00:46:57,750

 

1463
00:46:57,750 --> 00:47:00,550

 

1464
00:47:00,550 --> 00:47:03,270

 

1465
00:47:03,270 --> 00:47:05,430

 

1466
00:47:05,430 --> 00:47:06,870

 

1467
00:47:06,870 --> 00:47:08,470

 

1468
00:47:08,470 --> 00:47:11,270

 

1469
00:47:11,270 --> 00:47:14,230

 

1470
00:47:14,230 --> 00:47:16,069

 

1471
00:47:16,069 --> 00:47:18,710

 

1472
00:47:18,710 --> 00:47:20,150

 

1473
00:47:20,150 --> 00:47:22,870

 

1474
00:47:22,870 --> 00:47:24,470

 

1475
00:47:24,470 --> 00:47:26,069

 

1476
00:47:26,069 --> 00:47:28,790

 

1477
00:47:28,790 --> 00:47:31,190

 

1478
00:47:31,190 --> 00:47:33,910

 

1479
00:47:33,910 --> 00:47:36,069

 

1480
00:47:36,069 --> 00:47:38,549

 

1481
00:47:38,549 --> 00:47:41,190

 

1482
00:47:41,190 --> 00:47:44,790

 

1483
00:47:44,790 --> 00:47:47,430

 

1484
00:47:47,430 --> 00:47:50,069

 

1485
00:47:50,069 --> 00:47:52,390

 

1486
00:47:52,390 --> 00:47:54,230

 

1487
00:47:54,230 --> 00:47:57,030

 

1488
00:47:57,030 --> 00:47:59,750

 

1489
00:47:59,750 --> 00:48:01,750

 

1490
00:48:01,750 --> 00:48:04,309

 

1491
00:48:04,309 --> 00:48:04,319

 

1492
00:48:04,319 --> 00:48:05,109


1493
00:48:05,109 --> 00:48:05,119

 

1494
00:48:05,119 --> 00:48:07,510


1495
00:48:07,510 --> 00:48:09,990

 

1496
00:48:09,990 --> 00:48:12,630

 

1497
00:48:12,630 --> 00:48:14,150

 

1498
00:48:14,150 --> 00:48:14,160

 

1499
00:48:14,160 --> 00:48:15,349


1500
00:48:15,349 --> 00:48:20,390

 

1501
00:48:20,390 --> 00:48:20,400

 

1502
00:48:20,400 --> 00:48:22,230


1503
00:48:22,230 --> 00:48:22,240

 

1504
00:48:22,240 --> 00:48:23,750


1505
00:48:23,750 --> 00:48:27,190

 

1506
00:48:27,190 --> 00:48:28,870

 

1507
00:48:28,870 --> 00:48:31,430

 

1508
00:48:31,430 --> 00:48:33,349

 

1509
00:48:33,349 --> 00:48:35,109

 

1510
00:48:35,109 --> 00:48:37,270

 

1511
00:48:37,270 --> 00:48:37,280

 

1512
00:48:37,280 --> 00:48:37,990


1513
00:48:37,990 --> 00:48:39,670

 

1514
00:48:39,670 --> 00:48:41,829

 

1515
00:48:41,829 --> 00:48:44,069

 

1516
00:48:44,069 --> 00:48:47,190

 

1517
00:48:47,190 --> 00:48:47,200

 

1518
00:48:47,200 --> 00:48:48,630


1519
00:48:48,630 --> 00:48:50,870

 

1520
00:48:50,870 --> 00:48:53,190

 

1521
00:48:53,190 --> 00:48:55,510

 

1522
00:48:55,510 --> 00:48:57,670

 

1523
00:48:57,670 --> 00:48:59,430

 

1524
00:48:59,430 --> 00:49:00,790

 

1525
00:49:00,790 --> 00:49:03,670

 

1526
00:49:03,670 --> 00:49:05,589

 

1527
00:49:05,589 --> 00:49:06,710

 

1528
00:49:06,710 --> 00:49:08,309

 

1529
00:49:08,309 --> 00:49:10,470

 

1530
00:49:10,470 --> 00:49:14,549

 

1531
00:49:14,549 --> 00:49:16,549

 

1532
00:49:16,549 --> 00:49:19,109

 

1533
00:49:19,109 --> 00:49:19,119

 

1534
00:49:19,119 --> 00:49:20,470


1535
00:49:20,470 --> 00:49:22,390

 

1536
00:49:22,390 --> 00:49:24,790

 

1537
00:49:24,790 --> 00:49:28,309

 

1538
00:49:28,309 --> 00:49:28,319

 

1539
00:49:28,319 --> 00:49:29,270


1540
00:49:29,270 --> 00:49:31,990

 

1541
00:49:31,990 --> 00:49:32,000

 

1542
00:49:32,000 --> 00:49:33,750


1543
00:49:33,750 --> 00:49:35,190

 

1544
00:49:35,190 --> 00:49:37,589

 

1545
00:49:37,589 --> 00:49:39,670

 

1546
00:49:39,670 --> 00:49:41,670

 

1547
00:49:41,670 --> 00:49:44,069

 

1548
00:49:44,069 --> 00:49:45,589

 

1549
00:49:45,589 --> 00:49:49,190

 

1550
00:49:49,190 --> 00:49:55,190

 

1551
00:49:55,190 --> 00:49:55,200

 

1552
00:49:55,200 --> 00:50:04,230


1553
00:50:04,230 --> 00:50:05,510

 

1554
00:50:05,510 --> 00:50:09,990

 

1555
00:50:09,990 --> 00:50:11,430

 

1556
00:50:11,430 --> 00:50:13,430

 

1557
00:50:13,430 --> 00:50:15,190

 

1558
00:50:15,190 --> 00:50:17,109

 

1559
00:50:17,109 --> 00:50:19,510

 

1560
00:50:19,510 --> 00:50:22,630

 

1561
00:50:22,630 --> 00:50:22,640

 

1562
00:50:22,640 --> 00:50:24,230


1563
00:50:24,230 --> 00:50:25,750

 

1564
00:50:25,750 --> 00:50:29,270

 

1565
00:50:29,270 --> 00:50:31,190

 

1566
00:50:31,190 --> 00:50:32,630

 

1567
00:50:32,630 --> 00:50:34,150

 

1568
00:50:34,150 --> 00:50:34,160

 

1569
00:50:34,160 --> 00:50:35,190


1570
00:50:35,190 --> 00:50:37,670

 

1571
00:50:37,670 --> 00:50:40,710

 

1572
00:50:40,710 --> 00:50:40,720

 

1573
00:50:40,720 --> 00:50:42,710


1574
00:50:42,710 --> 00:50:45,190

 

1575
00:50:45,190 --> 00:50:47,750

 

1576
00:50:47,750 --> 00:50:49,910

 

1577
00:50:49,910 --> 00:50:49,920

 

1578
00:50:49,920 --> 00:50:50,870


1579
00:50:50,870 --> 00:50:53,670

 

1580
00:50:53,670 --> 00:50:54,870

 

1581
00:50:54,870 --> 00:50:57,109

 

1582
00:50:57,109 --> 00:50:59,270

 

1583
00:50:59,270 --> 00:51:01,030

 

1584
00:51:01,030 --> 00:51:03,190

 

1585
00:51:03,190 --> 00:51:05,349

 

1586
00:51:05,349 --> 00:51:09,270

 

1587
00:51:09,270 --> 00:51:10,710

 

1588
00:51:10,710 --> 00:51:10,720

 

1589
00:51:10,720 --> 00:51:12,069


1590
00:51:12,069 --> 00:51:13,910

 

1591
00:51:13,910 --> 00:51:15,990

 

1592
00:51:15,990 --> 00:51:17,190

 

1593
00:51:17,190 --> 00:51:20,150

 

1594
00:51:20,150 --> 00:51:21,990

 

1595
00:51:21,990 --> 00:51:22,000

 

1596
00:51:22,000 --> 00:51:23,190


1597
00:51:23,190 --> 00:51:25,030

 

1598
00:51:25,030 --> 00:51:25,040

 

1599
00:51:25,040 --> 00:51:26,150


1600
00:51:26,150 --> 00:51:26,160

 

1601
00:51:26,160 --> 00:51:27,589


1602
00:51:27,589 --> 00:51:29,750

 

1603
00:51:29,750 --> 00:51:32,390

 

1604
00:51:32,390 --> 00:51:34,150

 

1605
00:51:34,150 --> 00:51:36,470

 

1606
00:51:36,470 --> 00:51:37,910

 

1607
00:51:37,910 --> 00:51:39,750

 

1608
00:51:39,750 --> 00:51:41,030

 

1609
00:51:41,030 --> 00:51:43,510

 

1610
00:51:43,510 --> 00:51:45,829

 

1611
00:51:45,829 --> 00:51:47,910

 

1612
00:51:47,910 --> 00:51:49,670

 

1613
00:51:49,670 --> 00:51:50,790

 

1614
00:51:50,790 --> 00:51:53,109

 

1615
00:51:53,109 --> 00:51:54,230

 

1616
00:51:54,230 --> 00:51:56,069

 

1617
00:51:56,069 --> 00:51:58,390

 

1618
00:51:58,390 --> 00:51:59,990

 

1619
00:51:59,990 --> 00:52:01,589

 

1620
00:52:01,589 --> 00:52:04,390

 

1621
00:52:04,390 --> 00:52:04,400

 

1622
00:52:04,400 --> 00:52:05,670


1623
00:52:05,670 --> 00:52:07,589

 

1624
00:52:07,589 --> 00:52:09,030

 

1625
00:52:09,030 --> 00:52:12,069

 

1626
00:52:12,069 --> 00:52:13,349

 

1627
00:52:13,349 --> 00:52:17,589

 

1628
00:52:17,589 --> 00:52:19,750

 

1629
00:52:19,750 --> 00:52:21,910

 

1630
00:52:21,910 --> 00:52:23,270

 

1631
00:52:23,270 --> 00:52:24,790

 

1632
00:52:24,790 --> 00:52:26,150

 

1633
00:52:26,150 --> 00:52:28,470

 

1634
00:52:28,470 --> 00:52:30,549

 

1635
00:52:30,549 --> 00:52:32,549

 

1636
00:52:32,549 --> 00:52:35,109

 

1637
00:52:35,109 --> 00:52:39,030

 

1638
00:52:39,030 --> 00:52:41,109

 

1639
00:52:41,109 --> 00:52:42,870

 

1640
00:52:42,870 --> 00:52:45,670

 

1641
00:52:45,670 --> 00:52:47,750

 

1642
00:52:47,750 --> 00:52:50,950

 

1643
00:52:50,950 --> 00:52:52,950

 

1644
00:52:52,950 --> 00:52:54,390

 

1645
00:52:54,390 --> 00:52:57,270

 

1646
00:52:57,270 --> 00:52:59,589

 

1647
00:52:59,589 --> 00:53:03,109

 

1648
00:53:03,109 --> 00:53:04,390

 

1649
00:53:04,390 --> 00:53:05,670

 

1650
00:53:05,670 --> 00:53:06,950

 

1651
00:53:06,950 --> 00:53:09,109

 

1652
00:53:09,109 --> 00:53:11,670

 

1653
00:53:11,670 --> 00:53:13,670

 

1654
00:53:13,670 --> 00:53:13,680

 

1655
00:53:13,680 --> 00:53:14,390


1656
00:53:14,390 --> 00:53:14,400

 

1657
00:53:14,400 --> 00:53:15,349


1658
00:53:15,349 --> 00:53:15,359

 

1659
00:53:15,359 --> 00:53:16,230


1660
00:53:16,230 --> 00:53:18,150

 

1661
00:53:18,150 --> 00:53:18,160

 

1662
00:53:18,160 --> 00:53:19,349


1663
00:53:19,349 --> 00:53:20,950

 

1664
00:53:20,950 --> 00:53:22,230

 

1665
00:53:22,230 --> 00:53:24,470

 

1666
00:53:24,470 --> 00:53:26,230

 

1667
00:53:26,230 --> 00:53:28,230

 

1668
00:53:28,230 --> 00:53:30,309

 

1669
00:53:30,309 --> 00:53:32,069

 

1670
00:53:32,069 --> 00:53:34,230

 

1671
00:53:34,230 --> 00:53:36,069

 

1672
00:53:36,069 --> 00:53:37,510

 

1673
00:53:37,510 --> 00:53:40,150

 

1674
00:53:40,150 --> 00:53:42,710

 

1675
00:53:42,710 --> 00:53:42,720

 

1676
00:53:42,720 --> 00:53:45,510


1677
00:53:45,510 --> 00:53:47,430

 

1678
00:53:47,430 --> 00:53:49,430

 

1679
00:53:49,430 --> 00:53:50,870

 

1680
00:53:50,870 --> 00:53:53,829

 

1681
00:53:53,829 --> 00:53:56,069

 

1682
00:53:56,069 --> 00:53:58,150

 

1683
00:53:58,150 --> 00:53:58,160

 

1684
00:53:58,160 --> 00:53:59,270


1685
00:53:59,270 --> 00:54:01,349

 

1686
00:54:01,349 --> 00:54:03,750

 

1687
00:54:03,750 --> 00:54:05,750

 

1688
00:54:05,750 --> 00:54:07,910

 

1689
00:54:07,910 --> 00:54:10,390

 

1690
00:54:10,390 --> 00:54:12,150

 

1691
00:54:12,150 --> 00:54:14,069

 

1692
00:54:14,069 --> 00:54:15,750

 

1693
00:54:15,750 --> 00:54:17,190

 

1694
00:54:17,190 --> 00:54:18,549

 

1695
00:54:18,549 --> 00:54:21,109

 

1696
00:54:21,109 --> 00:54:23,829

 

1697
00:54:23,829 --> 00:54:25,270

 

1698
00:54:25,270 --> 00:54:26,630

 

1699
00:54:26,630 --> 00:54:27,750

 

1700
00:54:27,750 --> 00:54:29,990

 

1701
00:54:29,990 --> 00:54:33,349

 

1702
00:54:33,349 --> 00:54:37,430

 

1703
00:54:37,430 --> 00:54:40,950

 

1704
00:54:40,950 --> 00:54:44,309

 

1705
00:54:44,309 --> 00:54:45,829

 

1706
00:54:45,829 --> 00:54:45,839

 

1707
00:54:45,839 --> 00:54:46,870


1708
00:54:46,870 --> 00:54:49,589

 

1709
00:54:49,589 --> 00:54:51,589

 

1710
00:54:51,589 --> 00:54:53,750

 

1711
00:54:53,750 --> 00:54:56,309

 

1712
00:54:56,309 --> 00:54:58,069

 

1713
00:54:58,069 --> 00:54:59,349

 

1714
00:54:59,349 --> 00:54:59,359

 

1715
00:54:59,359 --> 00:55:02,150


1716
00:55:02,150 --> 00:55:04,829

 

1717
00:55:04,829 --> 00:55:07,030

 

1718
00:55:07,030 --> 00:55:09,190

 

1719
00:55:09,190 --> 00:55:10,789

 

1720
00:55:10,789 --> 00:55:13,589

 

1721
00:55:13,589 --> 00:55:13,599

 

1722
00:55:13,599 --> 00:55:15,270


1723
00:55:15,270 --> 00:55:16,789

 

1724
00:55:16,789 --> 00:55:18,150

 

1725
00:55:18,150 --> 00:55:25,990

 

1726
00:55:25,990 --> 00:55:26,000

 

1727
00:55:26,000 --> 00:55:27,270


1728
00:55:27,270 --> 00:55:28,950

 

1729
00:55:28,950 --> 00:55:28,960

 

1730
00:55:28,960 --> 00:55:31,829


1731
00:55:31,829 --> 00:55:33,910

 

1732
00:55:33,910 --> 00:55:36,789

 

1733
00:55:36,789 --> 00:55:38,470

 

1734
00:55:38,470 --> 00:55:41,430

 

1735
00:55:41,430 --> 00:55:43,589

 

1736
00:55:43,589 --> 00:55:45,589

 

1737
00:55:45,589 --> 00:55:46,710

 

1738
00:55:46,710 --> 00:55:49,430

 

1739
00:55:49,430 --> 00:55:51,109

 

1740
00:55:51,109 --> 00:55:53,270

 

1741
00:55:53,270 --> 00:55:55,670

 

1742
00:55:55,670 --> 00:55:57,829

 

1743
00:55:57,829 --> 00:55:57,839

 

1744
00:55:57,839 --> 00:55:58,710


1745
00:55:58,710 --> 00:55:59,829

 

1746
00:55:59,829 --> 00:56:01,349

 

1747
00:56:01,349 --> 00:56:03,589

 

1748
00:56:03,589 --> 00:56:06,150

 

1749
00:56:06,150 --> 00:56:06,160

 

1750
00:56:06,160 --> 00:56:07,510


1751
00:56:07,510 --> 00:56:09,990

 

1752
00:56:09,990 --> 00:56:11,589

 

1753
00:56:11,589 --> 00:56:15,030

 

1754
00:56:15,030 --> 00:56:16,630

 

1755
00:56:16,630 --> 00:56:18,950

 

1756
00:56:18,950 --> 00:56:18,960

 

1757
00:56:18,960 --> 00:56:19,829


1758
00:56:19,829 --> 00:56:21,750

 

1759
00:56:21,750 --> 00:56:23,109

 

1760
00:56:23,109 --> 00:56:25,349

 

1761
00:56:25,349 --> 00:56:25,359

 

1762
00:56:25,359 --> 00:56:25,710


1763
00:56:25,710 --> 00:56:25,720

 

1764
00:56:25,720 --> 00:56:27,349


1765
00:56:27,349 --> 00:56:28,870

 

1766
00:56:28,870 --> 00:56:32,789

 

1767
00:56:32,789 --> 00:56:34,950

 

1768
00:56:34,950 --> 00:56:36,549

 

1769
00:56:36,549 --> 00:56:39,270

 

1770
00:56:39,270 --> 00:56:40,390

 

1771
00:56:40,390 --> 00:56:42,710

 

1772
00:56:42,710 --> 00:56:44,390

 

1773
00:56:44,390 --> 00:56:45,990

 

1774
00:56:45,990 --> 00:56:48,309

 

1775
00:56:48,309 --> 00:56:50,870

 

1776
00:56:50,870 --> 00:56:52,950

 

1777
00:56:52,950 --> 00:56:52,960

 

1778
00:56:52,960 --> 00:56:53,829


1779
00:56:53,829 --> 00:56:56,309

 

1780
00:56:56,309 --> 00:56:57,750

 

1781
00:56:57,750 --> 00:56:59,670

 

1782
00:56:59,670 --> 00:57:01,349

 

1783
00:57:01,349 --> 00:57:03,670

 

1784
00:57:03,670 --> 00:57:05,670

 

1785
00:57:05,670 --> 00:57:07,349

 

1786
00:57:07,349 --> 00:57:09,109

 

1787
00:57:09,109 --> 00:57:10,950

 

1788
00:57:10,950 --> 00:57:10,960

 

1789
00:57:10,960 --> 00:57:11,670


1790
00:57:11,670 --> 00:57:13,829

 

1791
00:57:13,829 --> 00:57:13,839

 

1792
00:57:13,839 --> 00:57:14,950


1793
00:57:14,950 --> 00:57:17,270

 

1794
00:57:17,270 --> 00:57:19,030

 

1795
00:57:19,030 --> 00:57:22,630

 

1796
00:57:22,630 --> 00:57:25,349

 

1797
00:57:25,349 --> 00:57:27,030

 

1798
00:57:27,030 --> 00:57:28,470

 

1799
00:57:28,470 --> 00:57:31,750

 

1800
00:57:31,750 --> 00:57:34,710

 

1801
00:57:34,710 --> 00:57:36,710

 

1802
00:57:36,710 --> 00:57:36,720

 

1803
00:57:36,720 --> 00:57:37,990


1804
00:57:37,990 --> 00:57:40,230

 

1805
00:57:40,230 --> 00:57:42,870

 

1806
00:57:42,870 --> 00:57:44,309

 

1807
00:57:44,309 --> 00:57:47,030

 

1808
00:57:47,030 --> 00:57:48,950

 

1809
00:57:48,950 --> 00:57:50,710

 

1810
00:57:50,710 --> 00:57:52,870

 

1811
00:57:52,870 --> 00:57:55,910

 

1812
00:57:55,910 --> 00:57:58,390

 

1813
00:57:58,390 --> 00:58:00,870

 

1814
00:58:00,870 --> 00:58:03,589

 

1815
00:58:03,589 --> 00:58:05,510

 

1816
00:58:05,510 --> 00:58:07,109

 

1817
00:58:07,109 --> 00:58:08,549

 

1818
00:58:08,549 --> 00:58:09,990

 

1819
00:58:09,990 --> 00:58:11,750

 

1820
00:58:11,750 --> 00:58:13,910

 

1821
00:58:13,910 --> 00:58:16,710

 

1822
00:58:16,710 --> 00:58:19,430

 

1823
00:58:19,430 --> 00:58:21,190

 

1824
00:58:21,190 --> 00:58:23,670

 

1825
00:58:23,670 --> 00:58:26,789

 

1826
00:58:26,789 --> 00:58:29,349

 

1827
00:58:29,349 --> 00:58:31,190

 

1828
00:58:31,190 --> 00:58:33,270

 

1829
00:58:33,270 --> 00:58:34,789

 

1830
00:58:34,789 --> 00:58:36,710

 

1831
00:58:36,710 --> 00:58:39,030

 

1832
00:58:39,030 --> 00:58:41,670

 

1833
00:58:41,670 --> 00:58:43,829

 

1834
00:58:43,829 --> 00:58:43,839

 

1835
00:58:43,839 --> 00:58:45,030


1836
00:58:45,030 --> 00:58:46,950

 

1837
00:58:46,950 --> 00:58:49,030

 

1838
00:58:49,030 --> 00:58:50,309

 

1839
00:58:50,309 --> 00:58:51,670

 

1840
00:58:51,670 --> 00:58:53,190

 

1841
00:58:53,190 --> 00:58:55,910

 

1842
00:58:55,910 --> 00:58:57,589

 

1843
00:58:57,589 --> 00:58:59,190

 

1844
00:58:59,190 --> 00:59:00,630

 

1845
00:59:00,630 --> 00:59:02,630

 

1846
00:59:02,630 --> 00:59:05,190

 

1847
00:59:05,190 --> 00:59:07,030

 

1848
00:59:07,030 --> 00:59:08,549

 

1849
00:59:08,549 --> 00:59:10,630

 

1850
00:59:10,630 --> 00:59:13,910

 

1851
00:59:13,910 --> 00:59:15,349

 

1852
00:59:15,349 --> 00:59:17,750

 

1853
00:59:17,750 --> 00:59:17,760

 

1854
00:59:17,760 --> 00:59:19,190


1855
00:59:19,190 --> 00:59:20,950

 

1856
00:59:20,950 --> 00:59:20,960

 

1857
00:59:20,960 --> 00:59:21,829


1858
00:59:21,829 --> 00:59:23,750

 

1859
00:59:23,750 --> 00:59:23,760

 

1860
00:59:23,760 --> 00:59:24,630


1861
00:59:24,630 --> 00:59:26,470

 

1862
00:59:26,470 --> 00:59:27,829

 

1863
00:59:27,829 --> 00:59:31,589

 

1864
00:59:31,589 --> 00:59:33,589

 

1865
00:59:33,589 --> 00:59:34,789

 

1866
00:59:34,789 --> 00:59:36,870

 

1867
00:59:36,870 --> 00:59:36,880

 

1868
00:59:36,880 --> 00:59:38,069


1869
00:59:38,069 --> 00:59:39,750

 

1870
00:59:39,750 --> 00:59:42,870

 

1871
00:59:42,870 --> 00:59:45,030

 

1872
00:59:45,030 --> 00:59:46,630

 

1873
00:59:46,630 --> 00:59:49,910

 

1874
00:59:49,910 --> 00:59:53,109

 

1875
00:59:53,109 --> 00:59:56,230

 

1876
00:59:56,230 --> 00:59:56,240

 

1877
00:59:56,240 --> 00:59:57,270


1878
00:59:57,270 --> 00:59:59,349

 

1879
00:59:59,349 --> 01:00:01,109

 

1880
01:00:01,109 --> 01:00:04,230

 

1881
01:00:04,230 --> 01:00:06,390

 

1882
01:00:06,390 --> 01:00:08,870

 

1883
01:00:08,870 --> 01:00:08,880

 

1884
01:00:08,880 --> 01:00:09,829


1885
01:00:09,829 --> 01:00:12,150

 

1886
01:00:12,150 --> 01:00:15,109

 

1887
01:00:15,109 --> 01:00:17,910

 

1888
01:00:17,910 --> 01:00:20,309

 

1889
01:00:20,309 --> 01:00:22,390

 

1890
01:00:22,390 --> 01:00:24,549

 

1891
01:00:24,549 --> 01:00:26,390

 

1892
01:00:26,390 --> 01:00:29,030

 

1893
01:00:29,030 --> 01:00:30,950

 

1894
01:00:30,950 --> 01:00:32,789

 

1895
01:00:32,789 --> 01:00:34,390

 

1896
01:00:34,390 --> 01:00:36,870

 

1897
01:00:36,870 --> 01:00:39,349

 

1898
01:00:39,349 --> 01:00:40,789

 

1899
01:00:40,789 --> 01:00:43,750

 

1900
01:00:43,750 --> 01:00:45,750

 

1901
01:00:45,750 --> 01:00:47,990

 

1902
01:00:47,990 --> 01:00:48,000

 

1903
01:00:48,000 --> 01:00:49,430


1904
01:00:49,430 --> 01:00:49,440

 

1905
01:00:49,440 --> 01:00:50,870


1906
01:00:50,870 --> 01:00:53,750

 

1907
01:00:53,750 --> 01:00:55,910

 

1908
01:00:55,910 --> 01:00:59,190

 

1909
01:00:59,190 --> 01:01:01,829

 

1910
01:01:01,829 --> 01:01:03,349

 

1911
01:01:03,349 --> 01:01:05,270

 

1912
01:01:05,270 --> 01:01:08,470

 

1913
01:01:08,470 --> 01:01:11,910

 

1914
01:01:11,910 --> 01:01:15,190

 

1915
01:01:15,190 --> 01:01:17,750

 

1916
01:01:17,750 --> 01:01:19,030

 

1917
01:01:19,030 --> 01:01:19,040

 

1918
01:01:19,040 --> 01:01:20,470


1919
01:01:20,470 --> 01:01:22,710

 

1920
01:01:22,710 --> 01:01:25,190

 

1921
01:01:25,190 --> 01:01:26,870

 

1922
01:01:26,870 --> 01:01:29,109

 

1923
01:01:29,109 --> 01:01:29,119

 

1924
01:01:29,119 --> 01:01:30,069


1925
01:01:30,069 --> 01:01:33,030

 

1926
01:01:33,030 --> 01:01:36,150

 

1927
01:01:36,150 --> 01:01:37,670

 

1928
01:01:37,670 --> 01:01:39,670

 

1929
01:01:39,670 --> 01:01:43,349

 

1930
01:01:43,349 --> 01:01:43,359

 

1931
01:01:43,359 --> 01:01:44,309


1932
01:01:44,309 --> 01:01:47,430

 

1933
01:01:47,430 --> 01:01:47,440

 

1934
01:01:47,440 --> 01:01:48,309


1935
01:01:48,309 --> 01:01:48,319

 

1936
01:01:48,319 --> 01:01:49,270


1937
01:01:49,270 --> 01:01:51,349

 

1938
01:01:51,349 --> 01:01:53,510

 

1939
01:01:53,510 --> 01:01:55,430

 

1940
01:01:55,430 --> 01:01:55,440

 

1941
01:01:55,440 --> 01:01:56,470


1942
01:01:56,470 --> 01:01:58,950

 

1943
01:01:58,950 --> 01:02:02,630

 

1944
01:02:02,630 --> 01:02:04,069

 

1945
01:02:04,069 --> 01:02:05,910

 

1946
01:02:05,910 --> 01:02:08,950

 

1947
01:02:08,950 --> 01:02:10,789

 

1948
01:02:10,789 --> 01:02:13,750

 

1949
01:02:13,750 --> 01:02:13,760

 

1950
01:02:13,760 --> 01:02:17,750


1951
01:02:17,750 --> 01:02:17,760

 

1952
01:02:17,760 --> 01:02:19,430


1953
01:02:19,430 --> 01:02:21,270

 

1954
01:02:21,270 --> 01:02:22,950

 

1955
01:02:22,950 --> 01:02:24,630

 

1956
01:02:24,630 --> 01:02:26,470

 

1957
01:02:26,470 --> 01:02:28,390

 

1958
01:02:28,390 --> 01:02:30,870

 

1959
01:02:30,870 --> 01:02:33,270

 

1960
01:02:33,270 --> 01:02:36,870

 

1961
01:02:36,870 --> 01:02:38,950

 

1962
01:02:38,950 --> 01:02:41,670

 

1963
01:02:41,670 --> 01:02:43,349

 

1964
01:02:43,349 --> 01:02:44,630

 

1965
01:02:44,630 --> 01:02:46,950

 

1966
01:02:46,950 --> 01:02:50,870

 

1967
01:02:50,870 --> 01:02:53,829

 

1968
01:02:53,829 --> 01:02:56,150

 

1969
01:02:56,150 --> 01:02:58,789

 

1970
01:02:58,789 --> 01:03:02,069

 

1971
01:03:02,069 --> 01:03:04,870

 

1972
01:03:04,870 --> 01:03:06,789

 

1973
01:03:06,789 --> 01:03:09,750

 

1974
01:03:09,750 --> 01:03:09,760

 

1975
01:03:09,760 --> 01:03:10,630


1976
01:03:10,630 --> 01:03:13,109

 

1977
01:03:13,109 --> 01:03:14,710

 

1978
01:03:14,710 --> 01:03:16,309

 

1979
01:03:16,309 --> 01:03:18,390

 

1980
01:03:18,390 --> 01:03:18,400

 

1981
01:03:18,400 --> 01:03:19,190


1982
01:03:19,190 --> 01:03:21,190

 

1983
01:03:21,190 --> 01:03:22,789

 

1984
01:03:22,789 --> 01:03:22,799

 

1985
01:03:22,799 --> 01:03:23,670


1986
01:03:23,670 --> 01:03:26,150

 

1987
01:03:26,150 --> 01:03:28,230

 

1988
01:03:28,230 --> 01:03:29,430

 

1989
01:03:29,430 --> 01:03:31,829

 

1990
01:03:31,829 --> 01:03:31,839

 

1991
01:03:31,839 --> 01:03:32,710


1992
01:03:32,710 --> 01:03:32,720

 

1993
01:03:32,720 --> 01:03:34,069


1994
01:03:34,069 --> 01:03:36,230

 

1995
01:03:36,230 --> 01:03:38,549

 

1996
01:03:38,549 --> 01:03:38,559

 

1997
01:03:38,559 --> 01:03:40,309


1998
01:03:40,309 --> 01:03:44,549

 

1999
01:03:44,549 --> 01:03:47,270

 

2000
01:03:47,270 --> 01:03:49,829

 

2001
01:03:49,829 --> 01:03:54,390

 

2002
01:03:54,390 --> 01:03:56,630

 

2003
01:03:56,630 --> 01:03:58,069

 

2004
01:03:58,069 --> 01:04:01,190

 

2005
01:04:01,190 --> 01:04:02,710

 

2006
01:04:02,710 --> 01:04:05,349

 

2007
01:04:05,349 --> 01:04:06,950

 

2008
01:04:06,950 --> 01:04:09,430

 

2009
01:04:09,430 --> 01:04:11,109

 

2010
01:04:11,109 --> 01:04:13,670

 

2011
01:04:13,670 --> 01:04:16,950

 

2012
01:04:16,950 --> 01:04:18,710

 

2013
01:04:18,710 --> 01:04:22,470

 

2014
01:04:22,470 --> 01:04:24,309

 

2015
01:04:24,309 --> 01:04:27,589

 

2016
01:04:27,589 --> 01:04:29,910

 

2017
01:04:29,910 --> 01:04:32,870

 

2018
01:04:32,870 --> 01:04:34,710

 

2019
01:04:34,710 --> 01:04:37,270

 

2020
01:04:37,270 --> 01:04:38,710

 

2021
01:04:38,710 --> 01:04:40,870

 

2022
01:04:40,870 --> 01:04:41,990

 

2023
01:04:41,990 --> 01:04:43,510

 

2024
01:04:43,510 --> 01:04:45,910

 

2025
01:04:45,910 --> 01:04:45,920

 

2026
01:04:45,920 --> 01:04:47,109


2027
01:04:47,109 --> 01:04:49,349

 

2028
01:04:49,349 --> 01:04:51,990

 

2029
01:04:51,990 --> 01:04:53,750

 

2030
01:04:53,750 --> 01:04:56,789

 

2031
01:04:56,789 --> 01:04:57,910

 

2032
01:04:57,910 --> 01:04:59,910

 

2033
01:04:59,910 --> 01:05:01,670

 

2034
01:05:01,670 --> 01:05:03,829

 

2035
01:05:03,829 --> 01:05:05,750

 

2036
01:05:05,750 --> 01:05:09,349

 

2037
01:05:09,349 --> 01:05:13,829

 

2038
01:05:13,829 --> 01:05:16,230

 

2039
01:05:16,230 --> 01:05:17,589

 

2040
01:05:17,589 --> 01:05:20,870

 

2041
01:05:20,870 --> 01:05:23,829

 

2042
01:05:23,829 --> 01:05:25,589

 

2043
01:05:25,589 --> 01:05:27,750

 

2044
01:05:27,750 --> 01:05:29,670

 

2045
01:05:29,670 --> 01:05:30,950

 

2046
01:05:30,950 --> 01:05:32,549

 

2047
01:05:32,549 --> 01:05:32,559

 

2048
01:05:32,559 --> 01:05:33,829


2049
01:05:33,829 --> 01:05:36,789

 

2050
01:05:36,789 --> 01:05:38,630

 

2051
01:05:38,630 --> 01:05:40,309

 

2052
01:05:40,309 --> 01:05:41,589

 

2053
01:05:41,589 --> 01:05:43,109

 

2054
01:05:43,109 --> 01:05:44,710

 

2055
01:05:44,710 --> 01:05:46,150

 

2056
01:05:46,150 --> 01:05:48,789

 

2057
01:05:48,789 --> 01:05:51,670

 

2058
01:05:51,670 --> 01:05:51,680

 

2059
01:05:51,680 --> 01:05:52,870


2060
01:05:52,870 --> 01:05:55,990

 

2061
01:05:55,990 --> 01:05:58,309

 

2062
01:05:58,309 --> 01:06:00,309

 

2063
01:06:00,309 --> 01:06:01,990

 

2064
01:06:01,990 --> 01:06:03,910

 

2065
01:06:03,910 --> 01:06:06,870

 

2066
01:06:06,870 --> 01:06:08,390

 

2067
01:06:08,390 --> 01:06:11,670

 

2068
01:06:11,670 --> 01:06:11,680

 

2069
01:06:11,680 --> 01:06:12,470


2070
01:06:12,470 --> 01:06:14,309

 

2071
01:06:14,309 --> 01:06:14,319

 

2072
01:06:14,319 --> 01:06:16,069


2073
01:06:16,069 --> 01:06:20,549

 

2074
01:06:20,549 --> 01:06:22,630

 

2075
01:06:22,630 --> 01:06:24,549

 

2076
01:06:24,549 --> 01:06:24,559

 

2077
01:06:24,559 --> 01:06:25,349


2078
01:06:25,349 --> 01:06:25,359

 

2079
01:06:25,359 --> 01:06:26,150


2080
01:06:26,150 --> 01:06:28,150

 

2081
01:06:28,150 --> 01:06:30,069

 

2082
01:06:30,069 --> 01:06:31,910

 

2083
01:06:31,910 --> 01:06:34,789

 

2084
01:06:34,789 --> 01:06:37,670

 

2085
01:06:37,670 --> 01:06:37,680

 

2086
01:06:37,680 --> 01:06:38,710


2087
01:06:38,710 --> 01:06:41,510

 

2088
01:06:41,510 --> 01:06:44,069

 

2089
01:06:44,069 --> 01:06:44,079

 

2090
01:06:44,079 --> 01:06:45,270


2091
01:06:45,270 --> 01:06:47,349

 

2092
01:06:47,349 --> 01:06:48,470

 

2093
01:06:48,470 --> 01:06:50,069

 

2094
01:06:50,069 --> 01:06:50,079

 

2095
01:06:50,079 --> 01:06:51,029


2096
01:06:51,029 --> 01:06:51,039

 

2097
01:06:51,039 --> 01:06:52,390


2098
01:06:52,390 --> 01:06:53,910

 

2099
01:06:53,910 --> 01:06:57,029

 

2100
01:06:57,029 --> 01:07:01,670

 

2101
01:07:01,670 --> 01:07:03,349

 

2102
01:07:03,349 --> 01:07:05,510

 

2103
01:07:05,510 --> 01:07:07,270

 

2104
01:07:07,270 --> 01:07:08,309

 

2105
01:07:08,309 --> 01:07:10,230

 

2106
01:07:10,230 --> 01:07:12,069

 

2107
01:07:12,069 --> 01:07:13,670

 

2108
01:07:13,670 --> 01:07:16,230

 

2109
01:07:16,230 --> 01:07:17,670

 

2110
01:07:17,670 --> 01:07:20,470

 

2111
01:07:20,470 --> 01:07:23,430

 

2112
01:07:23,430 --> 01:07:23,440

 

2113
01:07:23,440 --> 01:07:24,390


2114
01:07:24,390 --> 01:07:27,029

 

2115
01:07:27,029 --> 01:07:29,190

 

2116
01:07:29,190 --> 01:07:29,200

 

2117
01:07:29,200 --> 01:07:30,710


2118
01:07:30,710 --> 01:07:32,950

 

2119
01:07:32,950 --> 01:07:32,960

 

2120
01:07:32,960 --> 01:07:33,829


2121
01:07:33,829 --> 01:07:33,839

 

2122
01:07:33,839 --> 01:07:39,349


2123
01:07:39,349 --> 01:07:39,359

 

2124
01:07:39,359 --> 01:07:40,470


2125
01:07:40,470 --> 01:07:43,029

 

2126
01:07:43,029 --> 01:07:44,230

 

2127
01:07:44,230 --> 01:07:45,750

 

2128
01:07:45,750 --> 01:07:47,589

 

2129
01:07:47,589 --> 01:07:47,599

 

2130
01:07:47,599 --> 01:07:48,470


2131
01:07:48,470 --> 01:07:48,480

 

2132
01:07:48,480 --> 01:07:49,100


2133
01:07:49,100 --> 01:07:49,110

 

2134
01:07:49,110 --> 01:07:50,950


2135
01:07:50,950 --> 01:07:53,029

 

2136
01:07:53,029 --> 01:07:53,039

 

2137
01:07:53,039 --> 01:07:53,829


2138
01:07:53,829 --> 01:07:53,839

 

2139
01:07:53,839 --> 01:07:55,670


2140
01:07:55,670 --> 01:07:57,589

 

2141
01:07:57,589 --> 01:07:59,349

 

2142
01:07:59,349 --> 01:08:00,950

 

2143
01:08:00,950 --> 01:08:00,960

 

2144
01:08:00,960 --> 01:08:01,910


2145
01:08:01,910 --> 01:08:04,549

 

2146
01:08:04,549 --> 01:08:04,559

 

2147
01:08:04,559 --> 01:08:05,910


2148
01:08:05,910 --> 01:08:07,910

 

2149
01:08:07,910 --> 01:08:10,470

 

2150
01:08:10,470 --> 01:08:11,910

 

2151
01:08:11,910 --> 01:08:11,920

 

2152
01:08:11,920 --> 01:08:12,870


2153
01:08:12,870 --> 01:08:14,230

 

2154
01:08:14,230 --> 01:08:16,709

 

2155
01:08:16,709 --> 01:08:19,430

 

2156
01:08:19,430 --> 01:08:19,440

 

2157
01:08:19,440 --> 01:08:20,470


2158
01:08:20,470 --> 01:08:23,430

 

2159
01:08:23,430 --> 01:08:26,470

 

2160
01:08:26,470 --> 01:08:28,789

 

2161
01:08:28,789 --> 01:08:30,870

 

2162
01:08:30,870 --> 01:08:34,470

 

2163
01:08:34,470 --> 01:08:35,590

 

2164
01:08:35,590 --> 01:08:35,600

 

2165
01:08:35,600 --> 01:08:36,550


2166
01:08:36,550 --> 01:08:38,789

 

2167
01:08:38,789 --> 01:08:41,030

 

2168
01:08:41,030 --> 01:08:42,870

 

2169
01:08:42,870 --> 01:08:42,880

 

2170
01:08:42,880 --> 01:08:43,829


2171
01:08:43,829 --> 01:08:46,309

 

2172
01:08:46,309 --> 01:08:46,319

 

2173
01:08:46,319 --> 01:08:47,189


2174
01:08:47,189 --> 01:08:50,149

 

2175
01:08:50,149 --> 01:08:53,510

 

2176
01:08:53,510 --> 01:08:57,510

 

2177
01:08:57,510 --> 01:08:59,510

 

2178
01:08:59,510 --> 01:09:01,269

 

2179
01:09:01,269 --> 01:09:04,309

 

2180
01:09:04,309 --> 01:09:07,430

 

2181
01:09:07,430 --> 01:09:10,229

 

2182
01:09:10,229 --> 01:09:13,189

 

2183
01:09:13,189 --> 01:09:13,199

 

2184
01:09:13,199 --> 01:09:14,149


2185
01:09:14,149 --> 01:09:16,149

 

2186
01:09:16,149 --> 01:09:17,990

 

2187
01:09:17,990 --> 01:09:20,789

 

2188
01:09:20,789 --> 01:09:23,510

 

2189
01:09:23,510 --> 01:09:25,189

 

2190
01:09:25,189 --> 01:09:27,829

 

2191
01:09:27,829 --> 01:09:30,709

 

2192
01:09:30,709 --> 01:09:30,719

 

2193
01:09:30,719 --> 01:09:31,749


2194
01:09:31,749 --> 01:09:33,749

 

2195
01:09:33,749 --> 01:09:36,630

 

2196
01:09:36,630 --> 01:09:39,749

 

2197
01:09:39,749 --> 01:09:41,110

 

2198
01:09:41,110 --> 01:09:43,910

 

2199
01:09:43,910 --> 01:09:44,950

 

2200
01:09:44,950 --> 01:09:49,839