front 1 Deterministic Finite Automata notation | back 1 A = {Q, Σ, δ, q_0, F} Σ - alphabet δ - transition function q_0 - start state F - finale state |
front 2 δ(current state, character) = state you would have transitioned to | back 2 δ(current state, character) = state you would have transitioned to |
front 3 How do you reverse a language represented as a DFA | back 3 - Change start state to final state - Change finale state(s) to start state(s) - Reverse the transitions (optional) - create a new state that λ transitions to all the start states |
front 4 How to tell if something is a Regular Language? | back 4 A DFA or NFA can recognize it |
front 5 Difference between DFA and NFA | back 5 DFA due to its deterministic nature must have a transition out of every state for every character in the alphabet, and NO λ transitions. Also note every DFA is technically also an NFA NFA doesn't have to have a transition for every alphabet character and can have λ transitions. Also note every NFA has an equivalent DFA |
front 6 some primitive notation | back 6 Φ = {} λ = {λ} a means where 'a' is in Σ denotes {a} |
front 7 Closure properties for R and S | back 7 R · S R + S R* |
front 8 ![]() convert this to a reg ex using (R_ij)^k method | back 8 in 1-16 notes |
front 9 ![]() convert this to a reg ex using state ripping | back 9 in 1-16 notes |
front 10 ![]() convert this to a reg ex using Arden's | back 10 in 1-21 notes |
front 11 Show the relation between the following family of languages. Regular,
Deterministic Context-Free, Context- | back 11 ![]() |
front 12 Show the relation between models of computation | back 12 ![]() |
front 13 True or False: Every NFA does not have an equivalent DFA | back 13 true, you can turn an nfa into usually a nasty much larger dfa with stuff like trap states. |
front 14 Does an algorithm exist for determining if a grammar is considered ambiguous? | back 14 no, ambiguity is undecidable |
front 15 Whenever a new problem is created, what is it considered inherently? | back 15 solvable and unsolved |
front 16 solved is temporal or inherited | back 16 temporal |
front 17 unsolvable/undecidable is temporal or inherited | back 17 temporal |
front 18 unsolved is temporal or inherited | back 18 inherited |
front 19 if we solve that new problem it moves from solvable and unsolved to? | back 19 solvable and solved |
front 20 if we find that new problem is unsolvable it moves from solvable and unsolved to? | back 20 unsolved and solved |
front 21 Can the CYK parsing algorithm take any type of grammar as input? | back 21 CYK operates only on context-free grammars given in Chomsky normal form |
front 22 ![]() Find the minimal equivalent DFA using the method that was shown in class. | back 22 1-23 slides |
front 23 True or False: The reversal operation is closed under regular languages. | back 23 true earlier card says how |
front 24 ![]() Express the following FSA as a regular expression using Arden's Theorem.. | back 24 1-21 slides |