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...
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.
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.
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.
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!
@@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! ^^
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.
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
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?
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.
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!
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.
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
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.
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.
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
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...
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.
personal index:
def of finite automaton : 20:00
regular lang def : 29:00
so this is that Michael Sipser whose book we all read and love
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.
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.
I've been waiting for this ever since I looked at Sipser's page and saw that it was being reviewed for OCW!
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!
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
work begins at 9:12
Love OCW. Figured they would have something for this to self study
This is the curicullum shared by pretty much every computer science department in my country of Greece... using the same book.
Woah, it's so cool to see him teaching here 😮
that is greatness - shows a different level of clarity....
Amazing lecture, everything clear even though it's mathematical, thanks for sharing
as someone who has used his text on toc, this is fun to watch. i wonder how i missed this playlist earlier.
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! ^^
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.
TOC: Basic TOC concepts:
FA, Definition, Regular languages & their properties
The slides are so easy on the eyes.
so am i
i love you MIT opencourseware
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
micheal is a great explainer,
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
Thank you very much for the course
One of the silver linings for covid. Thanks.
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
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
very helpful, thanks!
A Sipser MIT course. :-) :-) :-)
Why, thank you, Sir!
Great thanks Mit OCW, the textbook is also great
Very helpful to future students! Great work! Thank you!
i am waiting this course for long time☺️☺️☺️ i am very happy
Bookmark: 28:00
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)
thanks for sharing
Boring friday night? mit course sounds like a good plan. XD
Thank you professor
Thank you.
Thank you
16:35 To be honest, you did wake me up
Department of Computer Engineering & Informatics
University of Patras, Hellas.
Thank you, it was really helpful!
🤣🤣🤣
Thank you very much
Now I have something to watch on the bus
is F (which is the set of accept states) the same as saying the set of all final states? @21:54
04:30 prerequisites
05:40 role of theory
I would have failed this class if it wasn't for these lectures
Great!
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?
Thanks sir!
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!
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.
Professor, Can we consider that Σ*1 is equal to Σ^1
What operation do you mean by `^` ?
No+ only
isn't there a free legal version for the book
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.
Thank you heard my request
huge thanks from hungary!!
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!!!!!!!
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!
where are the ppts?
i have exam this day, im reviewing today HAHAHA.
can I think of the definition at 25:54 as exact match regarding regular expression?
What do you mean by "exact match"?
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.
Great course! Thanks a lot!
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.
better than proff sagarmoy
我是中国人 很感谢🙏
1:00:24 Loudly crying face (copyrighted) Source Unknown
LOL
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!
6:15 COMO FUNCIONA EL CEREBRO HUMANO ....
No one talks about computability of computer with proper example.
Done ✅
Here, before GATE 2022
It is so hard to keep track of what he is explaining in the last 3 sections. Lost interest...
Master in engineering here🇺🇸🇺🇸🇺🇸
42:32
I really hate I never got to hear anything by Alan Turing
32:00
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
1 done
0:09
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
4:06
not MOCW ending on a cliff hanger...
💡
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'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.
Take a drink everytime he AUMM
❤️ ❤️ ❤️
Goood
I did not understand 70% of the class
Give a try to "Mathematical Logic" by Joseph R. Shoenfield.
10:08
저자직강
37:03 No BADBADNOTGOOD ?? lol