thank you so much for sharing this course, I'm living in a country where buying things from other countries like online courses isn't possible due to sanctions. these free courses are the only things that let me learn, thank you again for your awesome website and courses.
his book is the book for the course this is part of... a course at MIT you can study online for free on MIT OCW... a course at MIT which can count toward degrees (including a PhD in at least one subject) in EECS & Mathematics, also oftentimes taken by physics majors...
for those who want to know Mike Sipser is author of the book that in detail explains those fundamentals of computer science, make sure you watch these playlist they have a huge value for those who want to learn theory of computation.
Just got automata and regular languages at school for computer science. Surprise surpise, i didn't understand a thing. Thank god for this youtube video.
I’ve had professor Sipser’s textbook for over a decade, and now I have also purchased a Polish edition and teach this material in my discrete mathematics course.
thank you MIT OCW for sharing such wonderful knowledge with detail explanation, for those who are not able to get source to learn things, it is really very great and awesome platform. thank you!
31:59 Basically, the reason why you can solve this problem, you can make a finite automaton which recognizes the language B, is because that finite automaton is going to keep track of the parity of the number of 1's it's seen before. This has two states, one of them remembering that it's seen an odd number of 1's so far, the other one remembering it's seen an even number of 1's before. And that's going to be typical for these automata, finite automata. There's going to be several different possibilities that you may have to keep track of as you're reading the input, and there's going to be a state associated with each one of those possibilities. So if you're designing an automaton, you have to think about-- as you're processing the input-- what things you have to keep track of. And you're going to make a state for each one of those possibilities 41:52 Show finite automata equivalent to Regular Expression.
@@thunderingeagle The course and the book both are amazing. The course is pretty much just Sipser repeating whatever is in the book so you can just watch the lectures and do problems from the book.
I really wish my Formal Languages/Theory of Computation (whichever your university calls the course), professor made it easier to understand like how Dr. Sipser does! Ty so much! Because I have my final this week and Dr. Sipser, as the author of my Theory of Computation course-textbook, and now I actually understand as I review for my final! ^^
I have always had trouble making the connection between these regular expressions/ languages and computation which is about solving problems algorithmically and creating a mechanistic process of solving a problem. I really wish that connection was made more clear
Not sure if the professor will alter his opening statement on math and AI, it looks like Q*2 has broken ground on that. Shows how 1 year ago is an eon in CS
PREREQUISITES: 6.042J Mathematics for Computer Science, 18.200 Principles of Discrete Applied Mathematics. For more info, visit the course on MIT OpenCourseWare at: ocw.mit.edu/18-404JF20. Best wishes on your studies!
watched vid to try and see what course was about since course description was bit unclear to me. reminds me of linear algebra a bit but still unclear as to the materials utility. Anyone have more complete understanding of subject that could tell me about where the information is useful?
Hey everyone! Why 'Note that a function may not necessarily use all the elements of the specified range. The function abs never takes on the value −1 even though −1 ∈ Z'? 🤔 This cite taken from 'Introduction to the Theory of Computation Third Edition' by Michael Sipser, FUNCTIONS AND RELATIONS chapter.
When the machine is in q2 and the input is zero, it goes back to q1 because there's an arrow labeled with zero that takes the machine from q2 to q1 when zero is the input. q2 doesn't have a circle labeled with zero because it's not making a transition to itself but a transition to q1. You can also look at the transition function (the table) which describes where the machine makes a transition based on the state it is in and the input symbol.
@@leonardmohr9450 I appreciate your answer but I had forgotten my question. LOL. But don't worry, I have to watch this video again as I don't remember a word about automata but have to study compiler design course which I failed two semesters ago.
These definitions are so retrograde it's amazing. It's a big problem with the Theory of Computation. You will often find yourself doing proofs in Python and other tools that actually work nicely and intuitively and then translate the result into Mathematical jargon so that you can get published.
Is (1U0)* actually supposed to be {{1}U{0}}* ? I might be wrong but we defined the union operation on languages which are sets. 1 and 0 do not appear to be set. This is min 40. Thanks in advance.
Construct NDPDA for the language of all non-palindrome. Construct DPDA for the language of all those strings in which the no. of a’s twice the no. of b’s. anybody help me please
I'm a math major, and my uni only offers theoretical CS as a unit to CS majors (or you'd have to do enough to earn a CS minor at least), which sucks because this really interests me, but I don't care much for the engineering/code-monkey stuff. Thanks for uploading this, I'm gonna follow these closely for sure!
I’ve found the “engineering/code monkey stuff” isn’t what a formal education in CS is about. It’s pretty much mathematics, these theoretical CS courses. Algorithms analysis and design, theory of computation/complexity theory, formal language and automata theory, mathematical cryptography, type theory, etc. A lot of a CS degree is pretty far away from the “engineering/code monkey” stuff, and theoretical computer scientists are mathematicians.
![[DRAGON BALL LEGENDS REVEALS ＆ STUFF] LEGENDS FESTIVAL 2024 Special Edition Part 1](http://i.ytimg.com/vi/mV5bGIswTtQ/mqdefault.jpg)
thank you so much for sharing this course, I'm living in a country where buying things from other countries like online courses isn't possible due to sanctions. these free courses are the only things that let me learn, thank you again for your awesome website and courses.
Books from telegrams and others can help as well
personal index:
def of finite automaton : 20:00
regular lang def : 29:00
This is THE Michael Sipser of Sipser's Introduction to the Theory of Computation.
who asked?
@@w0nnafight This is THE W0nnaFight of RUclips's comment section asking "who asked".
@@viridianiteThis is THE LuuuZeta of RUclips's comment section saying "This is THE W0nnaFight of RUclips's comment section asking "who asked".".
Holy shit i just noticed that
his book is the book for the course this is part of... a course at MIT you can study online for free on MIT OCW... a course at MIT which can count toward degrees (including a PhD in at least one subject) in EECS & Mathematics, also oftentimes taken by physics majors...
so this is that Michael Sipser whose book we all read and love
for those who want to know Mike Sipser is author of the book that in detail explains those fundamentals of computer science, make sure you watch these playlist they have a huge value for those who want to learn theory of computation.
Just got automata and regular languages at school for computer science. Surprise surpise, i didn't understand a thing. Thank god for this youtube video.
Holy shit! The legendary Michael Sipser is teaching it in video!!!!
I’ve had professor Sipser’s textbook for over a decade, and now I have also purchased a Polish edition and teach this material in my discrete mathematics course.
43:10 If the set has the empty string, it is no longer an empty set; it is a set containing the element empty string: A = {epsilon}
This course helped me during my automata course in my undergrad
thank you MIT OCW for sharing such wonderful knowledge with detail explanation, for those who are not able to get source to learn things, it is really very great and awesome platform. thank you!
This is the curicullum shared by pretty much every computer science department in my country of Greece... using the same book.
I've been waiting for this ever since I looked at Sipser's page and saw that it was being reviewed for OCW!
work begins at 9:12
Thanks to all for making this possible.
It's always a pleasure listening to lecture of a Legend.
teşekkürler geri dönüş melih
Bakıyorum herkes burda
31:59 Basically, the reason why you can solve this problem, you can make a finite automaton which recognizes the language B, is because that finite automaton is going to keep track of the parity of the number of 1's
it's seen before. This has two states, one of them remembering that it's seen an odd number of 1's so far,
the other one remembering it's seen an even number of 1's before. And that's going to be typical for these automata,
finite automata. There's going to be several different possibilities that you may have to keep track of as you're reading the input, and there's going to be a state associated with each one of those possibilities. So if you're designing an automaton, you have to think about-- as you're processing the input-- what things you have to keep track of. And you're going to make a state for each one of those possibilities
41:52 Show finite automata equivalent to Regular Expression.
as someone who has used his text on toc, this is fun to watch. i wonder how i missed this playlist earlier.
Amazing lecture, everything clear even though it's mathematical, thanks for sharing
Woah, it's so cool to see him teaching here 😮
Love OCW. Figured they would have something for this to self study
that is greatness - shows a different level of clarity....
The slides are so easy on the eyes.
so am i
dang just got his book introduction to computation and now i m watching his videos :) amazing video :)
Hows the book and the course ? I am planning to start this one....so any thoughts please :)
@@thunderingeagle The course and the book both are amazing. The course is pretty much just Sipser repeating whatever is in the book so you can just watch the lectures and do problems from the book.
I really wish my Formal Languages/Theory of Computation (whichever your university calls the course), professor made it easier to understand like how Dr. Sipser does! Ty so much! Because I have my final this week and Dr. Sipser, as the author of my Theory of Computation course-textbook, and now I actually understand as I review for my final! ^^
TOC: Basic TOC concepts:
FA, Definition, Regular languages & their properties
I have always had trouble making the connection between these regular expressions/ languages and computation which is about solving problems algorithmically and creating a mechanistic process of solving a problem. I really wish that connection was made more clear
Not sure if the professor will alter his opening statement on math and AI, it looks like Q*2 has broken ground on that. Shows how 1 year ago is an eon in CS
i love you MIT opencourseware
41:00 I was thinking this is like RegEx and then I was like hey this IS RegEx .. Fun to learn TOC at a random point in my education
Is this Mr. Sipser himself? It's been some years that I read his book. Had a love-hate relationship with that subject lol.
Yup
micheal is a great explainer,
A Sipser MIT course. :-) :-) :-)
One of the silver linings for covid. Thanks.
Great thanks Mit OCW, the textbook is also great
Boring friday night? mit course sounds like a good plan. XD
I would have failed this class if it wasn't for these lectures
16:35 To be honest, you did wake me up
i am waiting this course for long time☺️☺️☺️ i am very happy
Now I have something to watch on the bus
Thank you very much for the course
Very helpful to future students! Great work! Thank you!
Why, thank you, Sir!
i have exam this day, im reviewing today HAHAHA.
Department of Computer Engineering & Informatics
University of Patras, Hellas.
Thank you, it was really helpful!
🤣🤣🤣
very helpful, thanks!
the S = (a, b)
Is the (a* + b*) equals with (a + b)*
or (ab)* with (a*b*) ??
Pls help me (sorry for my bad english)
Bookmark: 28:00
No one talks about computability of computer with proper example.
Thank you professor
better than proff sagarmoy
is F (which is the set of accept states) the same as saying the set of all final states? @21:54
can someone please let me know of the prerequisites before starting if you have already seen the course.
PREREQUISITES: 6.042J Mathematics for Computer Science, 18.200 Principles of Discrete Applied Mathematics. For more info, visit the course on MIT OpenCourseWare at: ocw.mit.edu/18-404JF20. Best wishes on your studies!
thanks for sharing
Thanks
watched vid to try and see what course was about since course description was bit unclear to me. reminds me of linear algebra a bit but still unclear as to the materials utility. Anyone have more complete understanding of subject that could tell me about where the information is useful?
Thank you
Thank you.
Input letters are a and b, then what is the regular expressions no two a's come together (string may be any length) can anyone plz help plz!!!!!!!
Hey everyone! Why 'Note that a function may not necessarily use all
the elements of the specified range. The function abs never takes on the value
−1 even though −1 ∈ Z'? 🤔 This cite taken from 'Introduction to the Theory of Computation Third Edition' by Michael Sipser, FUNCTIONS AND RELATIONS chapter.
At 23:39 why q2 goes to q1 if the input is zero, why not it has circle above it like q1.
That's because there's a transition from q1 to q2 when the symbol is zero.
When the machine is in q2 and the input is zero, it goes back to q1 because there's an arrow labeled with zero that takes the machine from q2 to q1 when zero is the input. q2 doesn't have a circle labeled with zero because it's not making a transition to itself but a transition to q1.
You can also look at the transition function (the table) which describes where the machine makes a transition based on the state it is in and the input symbol.
Thank you very much
huge thanks from hungary!!
isn't there a free legal version for the book
1:00:24 Loudly crying face (copyrighted) Source Unknown
LOL
where can i access the slides?
You can find the course materials at: ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/. Best wishes on your studies!
Here, before GATE 2022
Great!
What is good homework to test if we clearly understand this lecture? Is there such corresponding homework?
He wrote the book "Introduction to Theory of Computation" where he provides many exercises that you can use to test yourself.
Thanks sir!
Thank you heard my request
Professor, Can we consider that Σ*1 is equal to Σ^1
What operation do you mean by `^` ?
No+ only
can I think of the definition at 25:54 as exact match regarding regular expression?
What do you mean by "exact match"?
not MOCW ending on a cliff hanger...
At 31:20 , I don't think that automaton can be created with two states. If it is possible, please share answer.
The two states are even and odd. The start state is even. The accept state is even. An input of zero wont change the state, and an input of one will.
@@leonardmohr9450 I appreciate your answer but I had forgotten my question. LOL. But don't worry, I have to watch this video again as I don't remember a word about automata but have to study compiler design course which I failed two semesters ago.
Great course! Thanks a lot!
These definitions are so retrograde it's amazing. It's a big problem with the Theory of Computation. You will often find yourself doing proofs in Python and other tools that actually work nicely and intuitively and then translate the result into Mathematical jargon so that you can get published.
"proofs"
I really hate I never got to hear anything by Alan Turing
What the Σigma
σκασε
Can be explained by lambda calculus, much more concise and graceful
is there a good course on RUclips that can help with the basics? I'd love to watch it
where are the ppts?
04:30 prerequisites
05:40 role of theory
6:15 COMO FUNCIONA EL CEREBRO HUMANO ....
我是中国人 很感谢🙏
Master in engineering here🇺🇸🇺🇸🇺🇸
Is (1U0)* actually supposed to be {{1}U{0}}* ? I might be wrong but we defined the union operation on languages which are sets. 1 and 0 do not appear to be set. This is min 40. Thanks in advance.
Yes, but he said that mostly to be concise, we neglect the braces in singletons.
You are right. By (1U0), he meant {{1}U{0}}. He treated {1} as 1, which is not correct.
Done ✅
It is so hard to keep track of what he is explaining in the last 3 sections. Lost interest...
Where can I get the slides used in the video?
You can get the slides on MIT OpenCOurseWare at: ocw.mit.edu/18-404JF20. Best wishes on your studies!
Take a drink everytime he AUMM
I did not understand 70% of the class
Give a try to "Mathematical Logic" by Joseph R. Shoenfield.
Construct NDPDA for the language of all non-palindrome.
Construct DPDA for the language of all those strings in which the no. of a’s twice the no. of b’s.
anybody help me please
1 done
I'm a math major, and my uni only offers theoretical CS as a unit to CS majors (or you'd have to do enough to earn a CS minor at least), which sucks because this really interests me, but I don't care much for the engineering/code-monkey stuff. Thanks for uploading this, I'm gonna follow these closely for sure!
I’ve found the “engineering/code monkey stuff” isn’t what a formal education in CS is about. It’s pretty much mathematics, these theoretical CS courses. Algorithms analysis and design, theory of computation/complexity theory, formal language and automata theory, mathematical cryptography, type theory, etc.
A lot of a CS degree is pretty far away from the “engineering/code monkey” stuff, and theoretical computer scientists are mathematicians.
37:03 No BADBADNOTGOOD ?? lol
💡
❤️ ❤️ ❤️
4:06
32:00
Goood