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...
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.
@gorkemgenc344 yeah it's going pretty well. Gonna finish my 5 years of CS degree by next six months, and will be joining a company coming Jan! Thanks for asking!
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 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! ^^
@@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.
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?
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.
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
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!
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.
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.
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.
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
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 UA-cam's comment section asking "who asked".
@@viridianiteThis is THE LuuuZeta of UA-cam's comment section saying "This is THE W0nnaFight of UA-cam'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!!!!
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.
personal index:
def of finite automaton : 20:00
regular lang def : 29:00
how is it going now?
@gorkemgenc344 yeah it's going pretty well. Gonna finish my 5 years of CS degree by next six months, and will be joining a company coming Jan! Thanks for asking!
@@vaalarivan_p happy to hear that
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.
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!
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
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}
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
@@yorgunkaptaan selamlar
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.
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 😮
Amazing lecture, everything clear even though it's mathematical, thanks for sharing
This course helped me during my automata course in my undergrad
is F (which is the set of accept states) the same as saying the set of all final states? @21:54
that is greatness - shows a different level of clarity....
Love OCW. Figured they would have something for this to self study
i love you MIT opencourseware
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.
can I think of the definition at 25:54 as exact match regarding regular expression?
What do you mean by "exact match"?
as someone who has used his text on toc, this is fun to watch. i wonder how i missed this playlist earlier.
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! ^^
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.
Bookmark: 28:00
The slides are so easy on the eyes.
so am i
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
Thanks for publishing this course!! Is there a newer version of it? Is there any news about the material since this course took place?
A Sipser MIT course. :-) :-) :-)
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 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,
Great thanks Mit OCW, the textbook is also great
i am waiting this course for long time☺️☺️☺️ i am very happy
One of the silver linings for covid. Thanks.
16:35 To be honest, you did wake me up
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)
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!
Very helpful to future students! Great work! Thank you!
very helpful, thanks!
Thank you very much for the course
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.
04:30 prerequisites
05:40 role of theory
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
Why, thank you, Sir!
Now I have something to watch on the bus
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
Boring friday night? mit course sounds like a good plan. XD
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.
Thanks
thanks for sharing
Thank you professor
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!
I would have failed this class if it wasn't for these lectures
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!!!!!!!
Thank you very much
Professor, Can we consider that Σ*1 is equal to Σ^1
What operation do you mean by `^` ?
No+ only
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!
Department of Computer Engineering & Informatics
University of Patras, Hellas.
Thank you, it was really helpful!
🤣🤣🤣
where are the ppts?
6:15 COMO FUNCIONA EL CEREBRO HUMANO ....
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.
Great!
i have exam this day, im reviewing today HAHAHA.
isn't there a free legal version for the book
1:00:24 Loudly crying face (copyrighted) Source Unknown
LOL
Thanks sir!
huge thanks from hungary!!
Great course! Thanks a lot!
Here, before GATE 2022
It is so hard to keep track of what he is explaining in the last 3 sections. Lost interest...
Thank you heard my request
No one talks about computability of computer with proper example.
Done ✅
What the Σigma
σκασε
32:00
better than proff sagarmoy
4:06
我是中国人 很感谢🙏
28:18
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.
10:08
Take a drink everytime he AUMM
I really hate I never got to hear anything by Alan Turing
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.
not MOCW ending on a cliff hanger...
I did not understand 70% of the class
Give a try to "Mathematical Logic" by Joseph R. Shoenfield.
Master in engineering here🇺🇸🇺🇸🇺🇸
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.
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
💡
Can be explained by lambda calculus, much more concise and graceful
is there a good course on UA-cam that can help with the basics? I'd love to watch it