Fourteen DFA Examples? No Problem!

Опубликовано: 05 Апрель 2026
на канале: Easy Theory

48,662

1.4k

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.

Easy Theory Website: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theor...
Patreon: / easytheoryyt
Fourthwall: https://easy-theory-llc-shop.fourthwa...
Problem Solving channel: ⁠ @easytheoryprobsolve

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: https://www.pexels.com/@stefwithanf-1....

If you like this content, please consider subscribing to my channel: / @easytheory