# Assignment Goals

The goals of this assignment are:
1. To map the control flow of a program using finite automata

# The Assignment

The purpose of this assignment is to create and implement a finite automata in a computer program.

## Part 1: Defining the Finite Automata

Consider the language S = {0, 1}, L = { w = strings of S* such that count(0) % 2 == 1 and count(1) % 2 == 1 }. In other words, there are an odd number of 0 and 1 characters in a String consisting of 1 and 0 characters of arbitrary length.

We can construct a finite state machine (FSM) from this definition. Specifically, we’ll use a Deterministic Finite Automata (DFA), although Non-Deterministic Fintie Automata (NFA) and regular expressions all recognize the same class of languages (“regular languages”).

Go to the FSM Simulator and define your state machine for the language above. Your accepting staet will be the condition in which you know there are an odd number of 0 characters and an odd number of 1 characters. Paste your resulting DFA into your readme document, or otherwise save and include it with your submission.

## Part 2: Implementing the Finite Automata

Write a program in a language of your choice that reads one character at a time from the terminal. Do not keep track of the actual number of characters that you have read, nor how many of each character you have seen (finite state machines only store their current state, with no additional information!). Instead, keep a variable that is equal to the state number that you are in. You can use an if statement that checks whether each character is a 0 or a 1, and a nested if statement that checks which state you’re in now. The result of these conditionals should be to update the state number to another state. When you’re done reading the string from the console, print out whether or not you are in an accepting state at the end.

## Part 3: Practice Constructing Finite State Machines

Using the FSM Simulator, construct some new finite state machines, which you can save and include with your submission. For each finite state machine, assume a language L consisting of Strings over S* given the alphabet S = {0, 1}.

1. All strings in which the character 0 always appears in pairs. For example: 100111001 but not 1010010. The regular expression is: (1*(00)*1*)*.
2. All strings in which the count of the character 1 is a multiple of 3. For example: 1001001 but not 100100. The regular expression is (0*10*10*1)*.

## Part 4: Limitations of Finite Automata

In your readme, describe why it is not possible to define a finite automata to balance parenthesis? Hint: it has to do with the fact that the FSM can’t store additional state, as we saw in Part 2! This is the same reason why you cannot represent this language with a regular expression.

1. What states would represent each of the conditions in Part 1? Hint: there are four of them - how many combinations of even/odd can you have for each character in the alphabet?

## Submission

• Describe what you did, how you did it, what challenges you encountered, and how you solved them.
• Please answer any questions found throughout the narrative of this assignment.
• If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
• Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
• Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
• Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.