Automata & Python - Computerphile

so I want to look today out as an automata I was teaching a python module but this has stopped and I teach a module on on formal languages and automata Theory which is theoretical computer science this is like State machines and things like that yeah the final State machines yeah and regular expressions but today I think we just look at a deterministic finite automata but what I what yeah I I don't want to give up this python thing altogether so what I'm going to do is we're going to implement automata in Python what is the language well it's a set of words I suppose yeah the language is a set of words that's very good well done um what is a bird sets of characters no it's a sequence of characters a sequence of symbols actually a sequence of symbols and actually this is the same as a list a special list of symbols what's the symbol uh alphabet yeah it's an element of an of an alphabet and we we usually use a big letter Sigma for for the alphabet it's a final set of symbols and often in in when we do Theory we often have very small alphabets and one symbol or two symbols but uh yeah that's very good for examples so let's start with an alphabet with Sigma you see if you do if you do some math we need to have some Greek letters that already shows and then some math is coming and let's just say we have a and b our symbols and our language is a set of words and it's all the words so let me write L are all the words the A's come before bees very simple language okay so that's some example so let's say a a is this okay yeah okay [Music] he's definitely before bees okay what about ba well no no okay and what about a b a no that can't be and what about Epsilon Epsilon is the empty word oh okay yeah so that's okay though that's okay okay so let's now build an automaton so I'm talking today about d f a which is short for deterministic finite automaton we will see in other types of our terminals or for example the NFA is the non-deterministic ones and we also see regular Expressions which are related to the same class of languages which are called irregular languages but today look at the simplest case of an automaton a DFA and an what's a DFA so we have a finite set of states then we have transitions between states which are labeled by the by the symbols have some initial States we have one initial State and then we have some final States so I start with the state 0 and since this is a start state okay throw an arrow that's when I start it's like a very simple game right but it's also a final State because if I if you've seen if the empty word is in the language so let me do a double circle to say that this is like a ghoul you know final step now if we see an a we stay in this state we have just seen Ace if we see a b we go into a new state one which also is a final step we have some seen some E's and one B so let me do this turns into a final State I may have seen more bees that's fine I stay in the state but it could happen I see an A in which case I'm unhappy so I go into State 2 which is not a final state but it's my error State and now I can have transition for a I stay in my unhappy State be I also stay in my unhappy State now actually but look at the examples we have so how does this work so a a so yeah we start here a candle with a finger once we go to the non-deterministic one I need several fingers and I think I'm going to do with markers but I'm here I see an a I stay here I mean I continue I go back here a and now I'm finished I let my a and I'm in a final state automata says yes now a a b b what is this a a now I have a b another B another B I mean the final state I'm happy now ba what happens I start here B I go there a I go there and I finish and I'm not on a final state so I have lost okay and now let's try this one a B a bad state and this one the empty word I start I'm already done on an empty State okay so the language of this automaton is exactly what I wanted to describe the words where the A's come into before B's so here we are in in Python and The Spider and I want to define a class of DFAS and I do the usual boilerplate so I Define an init method which says okay what is the DFA we have to have a set of States so I'm going to use the set type of of python there is a set of symbols which is called Sigma I don't know how to do Greek letters in in Python I think it's possible but I haven't yet figured it out there's another Greek letter the Delta which I also spelled out which is the transition function which gives tells us if you understate and you have a you have a symbol what is the next state and I'm going to use a dictionary for this transition function as a dictionary so we have an initial state which is the one where the L goes in and we have a set of final States and I also have a simple print function so let me Define our first automaton so this is the one whereas all the A's are before the B's and the set of state is 0 1 2 the set of symbols it's just a b and here is our table if I find the automotive which implements exactly this automaton so it says okay from zero if you've seen a you get to get a zero from zero if you set a b you're going to State one and so on from one if you've seen a you go to two and so on the left just encoded this little graph as a dictionary in Python now when I say 0 is the initial state and 0 1 is a set of final States okay so now we have to do something versus automaton so let's Implement a run function has a one function so I say here's a word which I will just use a string to represent it so initially my state is the initial state and then I'm going to eat the word so why the word is not empty I'm using my my Delta to say okay I'm in state q I see the first symbol of the string and I'm going to go into the new state and assign it to Q again and then also cut off the first symbol and when I finish this I return a Boolean which says there's a q is in set of final symbols okay I did something wrong oh I did my indentation level okay okay now it works let's try our examples if I find them again so here we run a two that's one d0 a a b b so this is two and now let's run ba oh d0 I mistyped okay as false oh let's do the the empty it's doing which is fine okay ended up with one more let's let's be complete it will test sweet thoughts so it seems to look bed stairs is red and football is green right it's a terrible example because Hill's already the most likely there could be many hundreds of words we could I'm happy again but now I have to say oh what happens if I if I see a b here

Channel: Computerphile

Views: 82,327

Keywords: computers, computerphile, computer, science

Id: 32bC33nJR3A

Length: 9min 27sec (567 seconds)

Published: Thu Mar 16 2023