You will be given a couple problems to solve using state machines. You can either do this on paper or using a graph editing tool such as yEd. Before you start building, consider your states and transitions in order to try to keep it neat. State machines can easily become very messy, so this planning is usually very important to ensure you don't have a mess.
The first state machine will be a string matcher. It can accept any lowercase alphabetic characters. In our notation, we will use a ? to represent a wild card- if a character matches no other transition, it will default to the transition with a ? label. It should output a 1 upon matching the string, and be implemented as a Moore state machine.
Finite state machines are known to be reducable to a regex for any desired output. This means that given a FSM, a starting state, and a desired output, you can write a regex expression that represents all possible sequences of inputs that would produce that output. This is very intuitive for the string matching problem we just did since regex is already designed for string matching. What regex would represent the first problem? It can accept "dog" prefixed by any sequence of characters, so ".*dog" should be sufficient. The second problem requires at least one character before "og", so ".+og" should work for that (if we wanted to be precise, we would append a $ to the end of our regex expressions to indicate that it should be the end of the string). It has been proven that any finite state machine, no matter how large, can be turned into a regex for any given output. Since the LC3 is a FSM, you can then write a regex that would demonstrate all possible inputs that would result in, for example, R4 = xF6D6 (it would, however, be many terabytes long). The LC3 is deterministic, meaning that for any given state and input, you can determine exactly what the next state would be. However, some finite state machines will have transitions which have a random chance of taking one transition, and will otherwise take a different transition. For some reason, people have made probabilistic reguluar exressions that handle this probability. In other words, this gets extremely complicated, but it's very interesting.
Back to something simple. This next finite state machine will take non-negative integers less than 5 as inputs, i.e. {0,1,2,3,4}. Upon receiving two integers, it will return 1 if the first integer is greater, -1 if the first integer is lesser, and 0 if they are the same. Upon receiving a third digit, there is no output. This one should be implemented as a Mealy machine. Think about if you can build a regex for all inputs that result in the output 0. In this case, it requires that the prefix has an even number of inputs, and then is followed by the same number twice. It's possible at least by listing out all combinations of two characters which aren't the same (there are 20 of them), allowing any number of those using an *, and then specifying the 5 pairs of numbers which are the same. Even a seemingly simple state machine resulted in a long regex.
You do not need to know about regex in-depth, but you should be confident designing a finite state machine by the end of this recitation.
If you've finished early, think about how the previous diagrams would differ if we implemented them as mealy instead of moore or vice versa. Would there be more states or less states? In problem 2, if you implement it as a moore machine, how many times do you use the initial state?