Here we solve Sipser problem 1.6, which involves 14 DFA (Deterministic Finite Automaton) problems. I give my strategies as well as ways for solving other problems.
Timestamps:
0:00 - Intro
0:19 - DFA for binary strings beginning with 1, end with 0
3:02 - DFA for binary strings with at least three 1s
4:50 - DFA for binary strings that contain 0101
8:39 - DFA for binary strings with third symbol 0
11:01 - DFA for binary strings that start with 0 and odd length, or start with 1 and even length
14:59 - DFA for binary strings that do not contain 110
18:57 - DFA for binary strings of length at most 5
20:51 - DFA for binary strings that are not 11 or 111
23:42 - DFA for binary strings with every odd position 1
26:28 - DFA for binary strings with at least two 0s, and at most one 1
31:29 - DFA for binary strings that are either empty or 0
33:00 - DFA for binary strings with even 0s or exactly two 1s
37:07 - DFAs for emptyset, and all nonempty strings
All of the transition videos are from StefWithAnF: www.pexels.com/@stefwithanf-1....
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
Негізгі бет Fourteen DFA Examples? No Problem!
Пікірлер: 26