[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:05.00,Default,,0000,0000,0000,,Well, once again, I recommend getting started by drawing the finite state machine.
Dialogue: 0,0:00:05.00,0:00:09.00,Default,,0000,0000,0000,,So on a or on b, we go over to state 2,
Dialogue: 0,0:00:09.00,0:00:11.00,Default,,0000,0000,0000,,and we could end there because this is optional,
Dialogue: 0,0:00:11.00,0:00:16.00,Default,,0000,0000,0000,,or on c or d, we could go to state 3 and end there.
Dialogue: 0,0:00:16.00,0:00:22.00,Default,,0000,0000,0000,,Here at the top, I've encoded the edges from state 1 on a we go to state 2.
Dialogue: 0,0:00:22.00,0:00:25.00,Default,,0000,0000,0000,,From state 1 on b, we go to state 2 as well--a or b.
Dialogue: 0,0:00:25.00,0:00:28.00,Default,,0000,0000,0000,,From state 2 on c, we go to state 3.
Dialogue: 0,0:00:28.00,0:00:31.00,Default,,0000,0000,0000,,From state 2 on d, we go to state 3.
Dialogue: 0,0:00:31.00,0:00:33.00,Default,,0000,0000,0000,,And both states, 2 and 3, are accepting.
Dialogue: 0,0:00:33.00,0:00:36.00,Default,,0000,0000,0000,,Then down here, I have 3 test cases.
Dialogue: 0,0:00:36.00,0:00:39.00,Default,,0000,0000,0000,,"ac" which should be accepted.
Dialogue: 0,0:00:39.00,0:00:42.00,Default,,0000,0000,0000,,"aX" which should not. X has no business in this regular expression.
Dialogue: 0,0:00:42.00,0:00:47.00,Default,,0000,0000,0000,,And just "b" alone, which should be fine because the c - d part is optional.
Dialogue: 0,0:00:47.00,0:00:48.00,Default,,0000,0000,0000,,Let's go see.
Dialogue: 0,0:00:48.00,0:00:51.00,Default,,0000,0000,0000,,And we get exactly the output we were expecting--true, false, true.
Dialogue: 0,0:00:51.00,0:00:57.00,Default,,0000,0000,0000,,Now you might have been tempted to have a c - d self-loop back to 2,
Dialogue: 0,0:00:57.00,0:01:00.00,Default,,0000,0000,0000,,instead of this right-hand side of the finite state machine.
Dialogue: 0,0:01:00.00,0:01:05.00,Default,,0000,0000,0000,,However, this self-loop changes the meaning to "[a - b][c - d]*".
Dialogue: 0,0:01:05.00,0:01:11.00,Default,,0000,0000,0000,,If you have this self-loop, acc is accepted--a-c-c, and it shouldn't be,
Dialogue: 0,0:01:11.00,9:59:59.99,Default,,0000,0000,0000,,so the self-loop is not the right way to go.