Finite Automata (Discrete Mathematics: Formal Languages and Automata) скачать в хорошем качестве

Finite Automata (Discrete Mathematics: Formal Languages and Automata)

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This is the first video in a series on Formal Languages and Automata that forms the last part of the Discrete Mathematics course for first year computer scientists. In this video I introduce finite automata, which you may already be familiar with from Digital Electronics. The automaton has a set of states, represented by blobs, of which exactly one is labelled as the start state and zero or more of which are marked as accepting states. The automaton is associated with an input alphabet: a transition between states is labelled with the input symbol that triggers it. The automaton defines a language: the set of strings of input symbols obtained by starting in the start state, following any path to an accepting state and listing the input symbols encountered on the transitions thus traversed. Going beyond the Deterministic Finite Automata seen in Digital Electronics, we define the more general Non-deterministic Finite Automata in which, given a state and an input symbol, the next state is not uniquely determined; and also the Non-deterministic Finite Automata with epsilon-transitions, in which the machine may move from one state to another without consuming an input symbol. I show with an example that the non-determinism may allow us to describe the intended behaviour more clearly and succintly than with a DFA. Interestingly, though, it is not the case that the NFA and NFA-epsilon are more expressive than the DFA. In the next couple of videos we'll see that they can all be converted into each other. So it's OK to use the NFA-epsilon to describe the intended behaviour more easily, but then to use the equivalent DFA as a practical way to recognize the corresponding strings. Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it. Course web page: https://www.cl.cam.ac.uk/teaching/cur... Course handout: https://www.cl.cam.ac.uk/teaching/202... My home page: http://stajano.com