Understanding Nondeterminism in Theoretical Computer Science 🤖

Noson S. Yanofsky. Brooklyn College. Theoretical Computer Science. Topics covered: Nondeterministic Finite automata, Epsilon-moves, Operations on languages (union, concatenation, star), closure of the operations.


0:00 Introduction
04:45 {0,1} L = {w | the third to the last letter of word w is a 1}
18:20 {a,b,c} L = {w | any b is immediately followed by the letter c}
23:00 {a,b,c} (abc)*
24:30 {a,b,c} (abc)+
27:00 {a,b,c} L = (w | abcxcba, x is any word in SIGMA*}
30:00 L = {a}
30:20 L = null set
35:00 0*1*0*
1:02:00 convert epsilon move nfa to dfa
1:22:00 union of regular languages
1:25:00 concatenation of regular languages and Kleene*
1:31:00 closure
1:45:00 concatenation
1:51:00 Kleene*
1:56:00 complement
1:58:00 intersection