2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

MIT 18.404J Theory of Computation, Fall 2020
Instructor: Michael Sipser

Quickly reviewed last lecture. Introduced nondeterministic finite automata (NFA). Proved that NFA and DFA are equivalent in power. Proved that the class of regular languages is closed under concatenation and star. Showed conversion of regular expressions to NFAs.

License: Creative Commons BY-NC-SA

[thhiep]

The teacher explained complicated concepts in a most intuitive, easy to understand way! Thank you.

[molangdraft]

This lecture is super easy to understand. Thank you for this legendary lecture, Michael.
1. Parallelism(Union) shows branching in programming.
2. Sequential process(Concatenation) shows just the process of programming itself.
3. Star (*) means the loop in programming.

[chefi]

Proving closures using NFAs feels like a cheat code

[icenberg]

Its always exciting to understand non determinism.

[williamrubin]

Great lecture. I am learning this material on my own. Reading lectures from another university was confusing but your video clarifies quite a bit. Thanks!

[TheHenrik]

Outstanding lectures this far, thank you! Love how every detail is explained, and with simple examples.

[HamSandwich]

wow this is leaps and bounds better explained than my university teacher

[bowlingfanatikzzz]

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

[augtugu]

HELLO UNCLE SIPSER.... Good to see you ... Keep it up good work ... Stay Fit and take care of yourself... ❤

[programmingwithahmetbilgic]

in the lecture, the Coffee break is the best time to learn 😀😃

[devmahad]

Introduction, outline, mechanics, expectations
2. Finite Automata, formal definition, regular languages
3. Regular Operations and Regular Expressions
4. Proved: Class of regular languages is closed under ∪
5. Started: Closure under ∘, to be continued…

[connorfrankston]

Correct me if I'm wrong, it seems to me that in order to account for the empty transitions in an NFA, the proof that NFA languages are regular would need to utilize the result that a union of regular languages is regular. If so, using the regularity of NFA languages to prove that a union of regular languages is regular is perhaps circular, and perhaps the most important aspect of the proof of regularity for NFA was brushed over.

[ДжонКонэр]

Great lecture! Thanks from Ukraine 🥰🙌🌞❤️

[LogicKaMagic]

For A* we are basically solving palindromic partition kind of leetcode problem where we we find a possible to place to cut the string and check check recursively the rest part I'd accepted or not

[mrgame]

24:00 what does the capital after the transition function stand for? new variable for states (Q)? And is it the same variable as 54:00?

[yuriykochetkov]

16:55 What about transition q2->q1 after reading ab?

[강경진-kq]

In closure in concat, why we don't know where to split?
x is a string in M1, so it has a finite length. Then I think the end of the string x must be the split point.

[austinoquinn]

Is every DFA an NFA? My initial guess was yes but not every DFA accepts the empty string. NFA must accept the empty string.
Thanks in advance.

[sukhjindersingh-hkrl]

what about in qbb time 18:00, the last b can jump to q4 using free one

[zyli-jx]

Why the NFA added the null symbol \epsilon compared to the DFA?