BRAINSCAPE1
CS 3120 Quiz 2 Exam with complete solutions
latest version
1. Non-determinism: a feature of computational models that allows them to exist in multiple states at one
time. The machine can be in any number of it's states simultaneously.
2. epsilon / empty transition: Machine splits into multiple copies of itself (is in multiple states at once)
and the copy transitions to the new state without reading input.
basically once we enter state with epsilon transition out of it immediately follow that transition and spawn ott a new
thread of computation
3. NFA vs. DFA: DFA must always have a path for every input in every state - NFA does not it is allowed for its
threads to "end" when no path possible
4. NFA equivalence to DFA proof: Direction 1: Given a DFA, construct NFA - trivial it is already a valid NFA
Direction 2: Given NFA, construct DFA
basically have a state for every possible subset of states the NFA can be in at once and transition between these
5. Regular language: A language is called a regular language if there exists some DFA that recognizes it
6. A U B: add in dummy start node and epsilon transition to DFAs for A and B, accept if one of them does
7. A B: run DFA for A and epsilon transition to start state of B from every final state of A
8. A^*: add in dummy start node that accepts (empty string), epsilon transition to DFA for A, add epsilons back to
start state from every final state
9. Formal Definition of Regular Expression: 1. a for some aΣ
2. ϵ - set containing only empty string
3. ϕ - empty set
4. (R_1*R _2), where R_1 and R_2 are regular expressions
5. (R_1R_2), where R_1 and R_2 are regular expressions
6. (R_1^), where R_1 is a regular expression
BRAINSCAPE1
CS 3120 Quiz 2 Exam with complete solutions
latest version
1. Non-determinism: a feature of computational models that allows them to exist in multiple states at one
time. The machine can be in any number of it's states simultaneously.
2. epsilon / empty transition: Machine splits into multiple copies of itself (is in multiple states at once)
and the copy transitions to the new state without reading input.
basically once we enter state with epsilon transition out of it immediately follow that transition and spawn ott a new
thread of computation
3. NFA vs. DFA: DFA must always have a path for every input in every state - NFA does not it is allowed for its
threads to "end" when no path possible
4. NFA equivalence to DFA proof: Direction 1: Given a DFA, construct NFA - trivial it is already a valid NFA
Direction 2: Given NFA, construct DFA
basically have a state for every possible subset of states the NFA can be in at once and transition between these
5. Regular language: A language is called a regular language if there exists some DFA that recognizes it
6. A U B: add in dummy start node and epsilon transition to DFAs for A and B, accept if one of them does
7. A B: run DFA for A and epsilon transition to start state of B from every final state of A
8. A^*: add in dummy start node that accepts (empty string), epsilon transition to DFA for A, add epsilons back to
start state from every final state
9. Formal Definition of Regular Expression: 1. a for some aΣ
2. ϵ - set containing only empty string
3. ϕ - empty set
4. (R_1*R _2), where R_1 and R_2 are regular expressions
5. (R_1R_2), where R_1 and R_2 are regular expressions
6. (R_1^), where R_1 is a regular expression
BRAINSCAPE1
