Skip to content
Hallway
0:00 / 0:00

#finiteautomata#regularexpressions#regularlanguages

1. Introduction, Finite Automata, Regular Expressions

MIT OpenCourseWare

6.5M subscribers • 34 videos on Hallway • University channel

YouTube
  • Recommended by 4 people: 4 on Hacker News.
  • Presented by Michael Sipser, MIT Professor

Intermediate. Assumes working knowledge.

626K views5 years ago4 recommendations

Computer scienceComputation and complexityAlgorithmsCompilers and interpreters

Michael Sipser introduces the theory of computation, covering finite automata, regular languages, regular expressions, and proofs of closure properties.

MIT 18.404J Theory of Computation, Fall 2020 Instructor: Michael Sipser View the complete course: ocw.mit.edu/18-404JF20 YouTube Playlist: youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY Introduction; course outline, mechanics, and expectations. Described finite automata, their formal definition, regular languages, regular operations, and regular expressions. Proved that the class of regular languages is closed under union. Started proving closure under concatenation. License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.edu Support OCW at ow.ly/a1If50zVRlQ We encourage constructive comments and discussion on OCW’s YouTube and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/comments.

Why it's here

4 people recommend this

What people say. Highly recommended as an exceptionally clear and accessible introduction to the theory of computation and formal languages.

sky2224on Hacker News • Recommends

On “Recommended Books on Computational Complexity Theory”

As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory. Sipser also has corresponding lectures that are available for free on YouTube here: link to this video .
View on Hacker News

trod123on Hacker News • Recommends

On “Making AI better at math tutoring”

…isinform others about the risks (by those parties actions removing legitimate and valid information). For those with the cajones to actually learn this stuff. Here is a link. It seems very jaron laden but it provides a true understanding of how computers actually work which is sorely lacking in the youth of today. MIT 18.404J Theory of Computation link to this video…
View on Hacker News

etermon Hacker News • Recommends

On “The Princeton INTERCAL Compiler's source code”

> if you require your parens to be balanced, that's no longer a regular language. TIL: link As someone who has only recently learned the formal definition of regular language ( Thanks to link to this video as mentioned on this board recently ), I'm interested in the formal proof for this? It feels intuitively true, but I haven't finished the course yet and therefore haven't come across it and can't yet reason well about it. Is the problem then in trying to "encode" whether brackets are balanced, that we would need infinite "levels" of how many more brackets we've opened rather than closed, (i.e a stack) and that violates the finite nature of finite automota? So I've googled it now, and I've found the…
View on Hacker News

skydhashon Hacker News • Recommends

On “Traps to Developers”

It's half a chapter in most books I know. Or a subset of this 1h MIT videos 0, but the instructor also explains Finite Automata which is the basic mechanism that does all the stuff. 0: link to this video
View on Hacker News

kjhugheson Hacker News • Mentions

On “MIT 18.404J – Theory of Computation [video]”

He addresses prerequisites specifically in the first lecture at this timestamp: link to this video (You're expected to be comfortable understanding mathematical theorems and producing proofs.)
View on Hacker News