1. Introduction, Finite Automata, Regular Expressions

[@leahthegeek9677]

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.

[@zakariatalukdar2552]

Books from telegrams and others can help as well

[@viridianite]

This is THE Michael Sipser of Sipser's Introduction to the Theory of Computation.

[@w0nnafight]

who asked?

[@viridianite]

@@w0nnafight This is THE W0nnaFight of KZbin's comment section asking "who asked".

[@martian0x80]

@@viridianiteThis is THE LuuuZeta of KZbin's comment section saying "This is THE W0nnaFight of KZbin's comment section asking "who asked".".

[@dyinginmyroom-gs2gc]

Holy shit i just noticed that

[@EzraSchroeder]

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...

[@swagatochatterjee7104]

Holy shit! The legendary Michael Sipser is teaching it in video!!!!

[@vaalarivan_p]

personal index: def of finite automaton : 20:00 regular lang def : 29:00

[@gorkemgenc344]

how is it going now?

[@vaalarivan_p]

@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!

[@gorkemgenc344]

@@vaalarivan_p happy to hear that

[@AyushBhattfe]

so this is that Michael Sipser whose book we all read and love

[@EngineersToGoMT]

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.

[@fnaticbwipo1222]

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.

[@mariuszpopieluch7373]

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.

[@chetashreejagtap7585]

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!

[@FR33Willi]

work begins at 9:12

[@MathNerdGamer]

I've been waiting for this ever since I looked at Sipser's page and saw that it was being reviewed for OCW!

[@beelediye6973]

It's always a pleasure listening to lecture of a Legend.

[@mustafaerenkoc886]

teşekkürler geri dönüş melih

[@yorgunkaptaan]

Bakıyorum herkes burda

[@LTG-]

@@yorgunkaptaan selamlar

[@VictorLG-c2d]

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}

[@whitedevil4123]

Thanks to all for making this possible.

[@MinhazulIslamRoyel]

This course helped me during my automata course in my undergrad

[@MrDiglenson]

Woah, it's so cool to see him teaching here 😮

[@vishnusingh4121]

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.

[@persi_dev]

This is the curicullum shared by pretty much every computer science department in my country of Greece... using the same book.

[@shanhuang5886]

that is greatness - shows a different level of clarity....

[@sebon11]

Amazing lecture, everything clear even though it's mathematical, thanks for sharing

[@jolness1]

Love OCW. Figured they would have something for this to self study

[@net.navigator]

as someone who has used his text on toc, this is fun to watch. i wonder how i missed this playlist earlier.

[@doyourealise]

dang just got his book introduction to computation and now i m watching his videos :) amazing video :)

[@thunderingeagle]

Hows the book and the course ? I am planning to start this one....so any thoughts please :)

[@x87-64]

​@@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.

[@maetamonxg7718]

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

[@Joshwism]

The slides are so easy on the eyes.

[@w0nnafight]

so am i

[@lucasmartinsbarretoalves9937]

i love you MIT opencourseware

[@A.K.00]

Is this Mr. Sipser himself? It's been some years that I read his book. Had a love-hate relationship with that subject lol.

[@maximusdecimusmeridius728]

Yup

[@GuitarheroWWEduh]

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! ^^

[@autogrant7020]

A Sipser MIT course. :-) :-) :-)

[@donaldtimpson4320]

One of the silver linings for covid. Thanks.

[@lesegomatsimela2112]

is F (which is the set of accept states) the same as saying the set of all final states? @21:54

[@epictetus__]

Bookmark: 28:00

[@-Mohamed_bayan]

i am waiting this course for long time☺️☺️☺️ i am very happy

[@temtamyassine2292]

Great thanks Mit OCW, the textbook is also great

[@Kenny-nj5te]

micheal is a great explainer,

[@phuditthawatsasom6869]

16:35 To be honest, you did wake me up

[@bowlingfanatikzzz]

Very helpful to future students! Great work! Thank you!

[@SigalnShow]

Thanks for publishing this course!! Is there a newer version of it? Is there any news about the material since this course took place?

[@SandipMukherjee-b6i]

Thank you very much for the course

[@potatoboss5239]

Now I have something to watch on the bus

[@TT-bv2nc]

very helpful, thanks!

[@federicogasparv]

Boring friday night? mit course sounds like a good plan. XD

[@devmahad]

TOC: Basic TOC concepts: FA, Definition, Regular languages & their properties

[@AntorFerdous]

I would have failed this class if it wasn't for these lectures

[@yrthinks6178]

At 23:39 why q2 goes to q1 if the input is zero, why not it has circle above it like q1.

[@viridianite]

That's because there's a transition from q1 to q2 when the symbol is zero.

[@viridianite]

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.

[@jasonpark6381]

can I think of the definition at 25:54 as exact match regarding regular expression?

[@viridianite]

What do you mean by "exact match"?

[@muhammadzuhairaskari7924]

04:30 prerequisites

[@muhammadzuhairaskari7924]

05:40 role of theory

[@ahsanahmad3193]

At 31:20 , I don't think that automaton can be created with two states. If it is possible, please share answer.

[@leonardmohr9450]

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.

[@ahsanahmad3193]

@@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.

[@climbeverest]

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

[@muhammadfaruq1782]

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)

[@uzairakram899]

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

[@aamodvardhanpandey]

Why, thank you, Sir!

[@chaitanyasharma6270]

where can i access the slides?

[@mitocw]

You can find the course materials at: ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/. Best wishes on your studies!

[@josemilian4167]

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?

[@austinoquinn815]

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.

[@x87-64]

Yes, but he said that mostly to be concise, we neglect the braces in singletons.

[@ABHAYKUMAR-kh4ce]

You are right. By (1U0), he meant {{1}U{0}}. He treated {1} as 1, which is not correct.

[@dakshsharma2209]

can someone please let me know of the prerequisites before starting if you have already seen the course.

[@mitocw]

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!

[@yuntaozhao5693]

Thank you professor

[@okaudi]

Professor, Can we consider that Σ*1 is equal to Σ^1

[@x87-64]

What operation do you mean by `^` ?

[@EUROSPORTS4TECH]

No+ only

[@Jonathondelemos]

Thanks

[@danny.math-tutor]

thanks for sharing

[@dattasai8060]

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!!!!!!!

[@AtulKumar-od6tn]

Thank you

[@___Truth___]

What is good homework to test if we clearly understand this lecture? Is there such corresponding homework?

[@nicolasguardado7466]

He wrote the book "Introduction to Theory of Computation" where he provides many exercises that you can use to test yourself.

[@ShubhamSinghYoutube]

Thank you.

[@jluconde3702]

6:15 COMO FUNCIONA EL CEREBRO HUMANO ....

[@SilverlightLantern]

1:00:24 Loudly crying face (copyrighted) Source Unknown

[@x87-64]

LOL

[@NikosXouselas10]

Department of Computer Engineering & Informatics University of Patras, Hellas. Thank you, it was really helpful!

[@ikebipe]

🤣🤣🤣

[@thegodfatheram]

Thank you very much

[@draneolfesoj13]

i have exam this day, im reviewing today HAHAHA.

[@shawonmajid]

Where can I get the slides used in the video?

[@mitocw]

You can get the slides on MIT OpenCOurseWare at: ocw.mit.edu/18-404JF20. Best wishes on your studies!

[@sohailakandil2046]

isn't there a free legal version for the book

[@sirluoyi2853]

Thanks sir!

[@vaishnavijahagirdar3835]

where are the ppts?

[@jayvirsingh2357]

better than proff sagarmoy

[@stardustsong1680]

Great course! Thanks a lot!

[@tamasurban8870]

huge thanks from hungary!!

[@Clory]

What the Σigma

[@manospediaditakis5627]

σκασε

[@vishalcseiitghy]

Here, before GATE 2022

[@grzegorzmajcher9237]

Great!

[@MaxMov-sp8hr]

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.

[@himeyprogramming7221]

Thank you heard my request

[@uditjec8587]

No one talks about computability of computer with proper example.

[@mistersir3185]

It is so hard to keep track of what he is explaining in the last 3 sections. Lost interest...

[@user-ew5vj1sl1u]

Done ✅

[@merry6423]

我是中国人 很感谢🙏

[@monsieurbreakyourpc]

32:00

[@naveenkumard9217]

4:06

[@whywakejha]

not MOCW ending on a cliff hanger...

[@lasranasmalevolas3303]

28:18

[@MasterCivilEngineering]

Master in engineering here🇺🇸🇺🇸🇺🇸

[@deeal5336]

37:03 No BADBADNOTGOOD ?? lol

[@wargreymon2024]

Take a drink everytime he AUMM

[@Iqbal00123]

I did not understand 70% of the class

[@t0wbo2t]

Give a try to "Mathematical Logic" by Joseph R. Shoenfield.

[@monsieurbreakyourpc]

10:08

[@Vickielynnrenegar]

I really hate I never got to hear anything by Alan Turing

[@zainulabideenkhan7218]

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

[@zemm9003]

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.

[@jfsadf784twgfg]

"proofs"

[@imglenngarcia]

💡

[@hussienalsafi1149]

❤️ ❤️ ❤️

[@Eta_Carinae__]

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!

[@moatef1886]

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.