Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
AUTOMATA M1-2
SA1
| Question | Answer |
|---|---|
| these are a collection of well defined objects, called elements, having certain common property | SETS |
| sets are a collection of well defined objects called what? | ELEMENTS |
| sets are represented by a _____ letter | CAPITAL |
| this symbol states that an element is an element of a set | ∈ |
| this symbol states that an element is not an element of a set | ∉ |
| in a set, the order of elements is ________ | INSIGNIFICANT |
| in a set, it does not matter how _____ the element is listed | MANY TIMES |
| enumerate the three methods of set notation | (1) ROSTER/TABULAR/LIST METHOD, (2) RULE/SET BUILDER METHOD, (3) VENN DIAGRAM [RTL-SR-VD] |
| in this method of set notation, the set is represented by actually listing the elements which belong to it | ROSTER/TABULAR/LIST METHOD |
| this method of set notation separates the elements by comma and encloses them between pair of curly brackets | ROSTER/TABULAR/LIST METHOD |
| A = { 1, 3, 5, 7 } is an example of what method of set notation? | ROSTER/TABULAR/LIST METHOD |
| this method of set notation is only used when the number of elements in the set is finite | ROSTER/TABULAR/LIST METHOD |
| in this method of set notation, the set is defined by stating property (P) which characterizes all the elements of the set | RULE/SET BUILDER METHOD |
| in this method of set notation, the elements must satisfy a given rule or condition | RULE/SET BUILDER METHOD |
| A = { x|x <= 5 } is an example of what method of set notation? | RULE/SET BUILDER METHOD |
| this method of set notation represents relation and operator using the plane geometrical figures such as rectangle, circle, ellipse | VENN DIAGRAM |
| enumerate the ten types of sets | (1) FINITE, (2) INFINITE, (3) EMPTY, (4) UNIT, (5) SUBSET, (6) PROPER SUBSET, (7) FAMILY, (8) POWER, (9) UNIVERSAL, (10) COMPLEMENT [FIEU-SPF-PUC] |
| this type of set has countable elements | FINITE SET |
| this type of set has uncountable elements | INFINITE SET |
| this type of set has no element | EMPTY SET |
| this type of set is also called a null or void set | EMPTY SET |
| what are the other names for an empty set? | NULL SET, VOID SET |
| an empty set is denoted by what symbols? | ∅ and {} |
| this type of set has only one element | UNIT SET |
| what is the other name for a unit set? | SINGLETON SET |
| this type of set is if each element of the set A is also an element of set B | SUBSET |
| what symbol is used to denote a subset? | ⊆ |
| what symbol is used to denote a proper subset? | ⊂ |
| what is the formula for finding the number of subsets of a set? | 2^n |
| this type of set is when set A is a subset of set B and A is not equal to B | PROPER SUBSET |
| set A is a _____ of set B if there is at least one element in B not contained in A | PROPER SUBSET |
| what is the formula for finding the number of proper subsets of a set? | 2^n - 1 |
| this type of set is a class of sets or the set of sets | FAMILY SET |
| A = { ∅, {a}, {a, b} } is an example of what type of set? | FAMILY SET |
| A = { a } is an example of what type of set? | UNIT SET |
| A = { -2, -1, 0, 1, 2, ... } is an example of what type of set? | INFINITE SET |
| A = { -2, -1, 0, 1, 2 } is an example of what type of set? | FINITE SET |
| this type of set is the set of all subsets of a given set | POWER SET |
| this type of set is denoted by P(A) where the number of subsets is equal to 2^|A| | POWER SET |
| this type of set is a set which contains all objects, including itself | UNIVERSAL SET |
| this type of set is denoted by U | UNIVERSAL SET |
| this type of set is a set containing everything that is not in set A | COMPLEMENT SET |
| this type of set is denoted by A' or A^c | COMPLEMENT SET |
| enumerate the three set relations | (1) DISJOINT, (2) EQUAL, (3) EQUIVALENT [DEE] |
| this set relation is two sets having no common elements | DISJOINT SETS |
| this set relation is two sets A and B consisting of the same elements and same cardinality | EQUAL SETS |
| this set relation is two sets A and B having the same number of elements or cardinality | EQUIVALENT SETS |
| this is the number of elements in a set | CARDINALITY |
| the ____ of two sets A and B is the set which contains all the elements of A and all the elements of B | UNION |
| what symbol is used to denote the union of two sets? | ∪ |
| { x|(x ∈ A) or (x ∈ B) } is the formula for what set operation? | UNION |
| the ____ of two sets A and B is a set that contains exactly those elements that are in both A and B | INTERSECTION |
| what symbol is used to denote the intersection of two sets? | ∩ |
| { x|(x ∈ A) and (x ∈ B) } is the formula for what set operation? | INTERSECTION |
| the ____ of set A and set B is the set that contains everything that is in A but not in B | SET DIFFERENCE |
| what symbol is used to denote the set difference of two sets? | - |
| { x|(x ∈ A) and (x ∉ B) } is the formula for what set operation? | SET DIFFERENCE |
| A ∪ ∅ = A and A ∩ U = A demonstrate what law? | IDENTITY LAW |
| A ∪ U = U and A ∩ ∅ = ∅ demonstrate what law? | DOMINATION LAW |
| A ∪ A = A and A ∩ A = A demonstrate what law? | IDEMPOTENT LAW |
| (A^c)^c = A demonstrates what law? | INVOLUTION PROPERTY |
| A ∪ B = B ∪ A and A ∩ B = B ∩ A demonstrate what law? | COMMUTATIVE LAW |
| (A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C) demonstrate what law? | ASSOCIATIVE LAW |
| A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) demonstrate what law? | DISTRIBUTIVE LAW |
| (A ∪ B)^c = A^c ∩ B^c and (A ∩ B)^c = A^c ∪ B^c demonstrate what law? | DE MORGAN'S LAW |
| A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A demonstrate what law? | ABSORPTION LAW |
| A ∪ A^c = U and A ∩ A^c = ∅ demonstrate what law? | COMPLEMENT LAW |
| ∅^c = U and U^c = ∅ demonstrate what law? | COMPLEMENT LAW |
| A computer company must hire 25 programmers to handle systems programming tasks and 40 programmers for applications programming. Of those hired, 10 will be expected to perform tasks of each type. How many will be hired? | (25 - 10) + 10 + (40 - 10) = 55 |
| a ____ on sets S and T is a set of ordered pairs (s, t), where s ∈ S, t ∈ T, S and T need not be different, S is the "domain" and T is the "range" | RELATION |
| in a relation, the set of all first elements is the ____ of the relation | DOMAIN |
| in a relation, the set of all second elements is the ____ of the relation | RANGE |
| R is a relation from A to B is defined how? | a|b, (a, b) ∈ R |
| let A = { 1, 2, 3 }, what is the elements of the relation R = {(a,b)|(a < b)} | R = {(1, 2), (1, 3), (2, 3)} |
| let A = { 1, 2, 3 }, what is the elements of the relation R = {(a,b)|(a = b)} | R = {(1, 1), (2, 2), (3, 3)} |
| let A = { 1, 2, 3 }, what is the elements of the relation R = {(a,b)|(b = 4a)} | R = {} |
| enumerate the three types of relation | (1) IDENTITY, (2) VOID, (3) UNIVERSAL [IVU] |
| an ____ relation is a relation that has all ordered pairs having the same first and second elements | IDENTITY RELATION |
| an ____ relation is a relation that has no ordered pairs | VOID RELATION |
| an ____ relation is a relation that has all possible ordered pairs | UNIVERSAL RELATION |
| let's say R is a subset of A, R is called an _____ relation on A if R is reflexive, symmetric, and transitive | EQUIVALENCE |
| this condition for an equivalence relation states that for all a ∈ A, (a, a) ∈ R | REFLEXIVE |
| this condition for an equivalence relation states that if (a, b) ∈ R, then (b, a) ∈ R | SYMMETRIC |
| this condition for an equivalence relation states that if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R | TRANSITIVE |
| a relation can be represented using these four diagrams | (1) ARROW DIAGRAM, (2) TABLE, (3) MATRIX, (4) DIRECTED GRAPH [ATM-D] |
| this diagram represents a relation as a set of arrows pointing from the set of first elements to the set of second elements | ARROW DIAGRAM |
| this diagram represents a relation with the first elements as rows and the second elements as columns | TABLE |
| this diagram represents a relation with the first elements as row indices and the second elements as column indices and 1 denotes existence and 0 otherwise | MATRIX |
| this diagram represents a relation as a set of nodes connected by arrows | DIRECTED GRAPH |
| this is a way of matching the members of a set A to a set B | FUNCTION |
| in a ____, each element of A should be associated to exactly one element of B, though more A may be associated in B | FUNCTION |
| in a function, every element of A must be associated with ____ element of B | UNIQUE |
| in a function, there may be some elements of set B which are ____ to any element of set A | NOT ASSIGNED |
| for functions and relations, every ____ is a ____ but not every ____ is a ____ | FUNCTION, RELATION; RELATION, FUNCTION |
| an injective correspondence is also called a ____ function | ONE-TO-ONE |
| a function is ____ if no two different elements of A are assigned to the same element of B | ONE-TO-ONE |
| a function is ____ if each element of B is assigned to at least one element of A | ONTO |
| a surjective correspondence is also called a ____ function | ONTO |
| "every B has some A" in a function demonstrates what? | ONTO |
| a function is ____ if there is one element of B which is not assigned to any element of A | INTO |
| a function is ____ if for every y in B, there is exactly one x in A such that f(x) = y | BIJECTIVE |
| a function is ____ if it is both a one-to-one (injective) correspondence between A and B and is onto (surjective) | BIJECTIVE |
| a ____ function is mapped to the same single element of B | CONSTANT |
| a ____ function is where for any two points in the interval, a change in x results in zero change in f(x) | CONSTANT |
| an ____ function is mapped into itself | IDENTITY |
| a function is ____ only if each input has a unique output, meaning we can use the output to re-obtain the input | INVERTIBLE |
| this is a function whose domain is a subset of its codomain, and for which all the elements in its domain are fixed points | INCLUSION FUNCTION |
| this is a bunch of vertices (nodes) which are represented by circles and are connected by edges represented by lines | GRAPH |
| these are acyclic undirected graphs where any two vertices are connected by exactly one simple path only | TREES |
| the ____ of a vertex is the number of edges that are directed towards the vertex | IN-DEGREE |
| the ____ of a vertex is the number of edges that are directed away from the vertex | OUT-DEGREE |
| this is a pair of vertices that determine an edge | ADJACENT VERTICES |
| a vertex with no incident edges is called an ____ vertex | ISOLATED |
| in a graph G, this consists of a pair (V, E) of sequences | PATH |
| this is a path that begins and ends at the same vertex | CIRCUIT |
| a path is called ____ if no vertex appears more than once in the vertex sequence | SIMPLE |
| a graph is called ____ if there is a path from any vertex to any other vertex in it | CONNECTED |
| a graph is called ____ if there exists a pair of vertices without a path between them | DISCONNECTED |
| if the graph is disconnected, the various connected pieces are called the ____ of the graph | COMPONENTS |
| a graph is called a ____ if it is connected and has no simple cycles | TREE |
| a ____ is a cycle that does not repeat any node except for the first and last node | SIMPLE CYCLE |
| this is the study of abstract computing device, or "machines" | AUTOMATA THEORY |
| this deals with the logic of computation with respect to simple machines | AUTOMATA THEORY |
| simple machines are referred to as what? | AUTOMATA |
| this deals with the definitions and properties of mathematical models of computation such as the Turing machine | AUTOMATA THEORY |
| through this, computer scientists are able to understand how machines compute functions and solve problems | AUTOMATA THEORY |
| he conceived the first infinite model of computation in 1936 | ALAN TURING |
| these two were first to present a description of finite automata in 1943 | WARREN MCCULLOCH, WALTER PITTS |
| these two generalized automata theory to a much powerful machine in 1955 | G.H. MEALY, E.F. MOORE |
| knowledge of this is very important in designing compilers | AUTOMATA THEORY |
| ____ in automata provide a thousand and one uses for professional programmers | REGULAR EXPRESSIONS |
| searching for ____ in texts can be carried out efficiently using automata | PATTERNS |
| ___ theory of recognizable language can be developed using automata theory and its languages | ALGEBRAIC |
| this is a finite, nonempty set of symbols | ALPHABET |
| an alphabet is denoted by what symbol? | SIGMA (Σ) |
| the elements inside an alphabet are called what? | SYMBOLS |
| Σ^(+) denotes what? | SET OF ALL NONEMPTY STRINGS |
| Σ^(*) denotes what? | SET OF ALL STRINGS incl. EMPTY STRING |
| an empty string is denoted by what symbol? | ε (epsilon) or λ (lambda) |
| this is a list of symbols from an alphabet joined together | STRING |
| this is an ordered n-tuple of elements of Σ, written without punctuation | STRING |
| there is a unique string of length zero over Σ called what? | NULL/EMPTY STRING |
| say u and v are elements of Σ^(*), uv is the ____ of u and v | CONCATENATION |
| this is the process of joining two strings end-to-end | CONCATENATION |
| this is the number of positions for symbols in the string | LENGTH |
| the length of a string w is denoted how? | |w| |
| z is a ____ of w if z appears consecutively within the string w | SUBSTRING |
| if w = xv for some x, then v is ___ of w | SUFFIX |
| if w = vy for some y, then v is ___ of w | PREFIX |
| this is the way of ordering in the same way as the dictionary ordering, except the shorter strings precede the longer ones | LEXICOGRAPHICAL ORDER |
| a set of ____ of a string w with length n contains all the substrings of w that have length n | FACTORS |
| multiplying two set of strings results in a set of all possible ____ of the strings | CONCATENATIONS |
| this is a set of strings from the same alphabet | LANGUAGE |
| a language is denoted by what? | L(M) |
| L = { w ∈ Σ^(*)|w satisfies property P } is an example of what kind of language? | INFINITE LANGUAGE |
| if L1 and L2 are languages over Σ, their ____ is L = L1 o L2 or simply L = L1L2 | CONCATENATION |
| this is the set of all strings of a certain length from Σ | POWERS OF AN ALPHABET |
| the powers of an alphabet is denoted by what? | Σ^(k) where k is the length |
| its purpose is to remember the relevant portion of the system's history | STATE |
| the initial state is denoted by what? | q0 |
| the basic structure of a proof is just a series of statements, each one being either of these two | (1) ASSUMPTION, (2) CONCLUSION |
| this is a state diagram that comprehensively captures all possible states and transitions that a machine can take while responding to a stream or sequence of input symbols | FINITE AUTOMATA |
| this consists of a finite set of states and a set of transitions from state to state that occur on input symbols chosen from an alphabet | FINITE AUTOMATA |
| these are used in text processors, compilers, and hardware design | FINITE AUTOMATA |
| this serves as a recognizer for regular languages | FINITE AUTOMATA |
| enumerate the two classes of finite automata | (1) DETERMINISTIC FINITE AUTOMATA, (2) NONDETERMINISTIC FINITE AUTOMATA [DFA-NFA] |
| this class of finite automata is when the automaton cannot be in more than one state at any one time | DETERMINISTIC FINITE AUTOMATA (DFA) |
| this class of finite automata is when for each symbol in Σ, there is exactly one transition of each state (possible back to the state itself) | DETERMINISTIC FINITE AUTOMATA (DFA) |
| this class of finite automata does not accept empty strings (ε) | DETERMINISTIC FINITE AUTOMATA (DFA) |
| this class of finite automata is when the automaton may be in several states at once | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| this class of finite automata allows zero, one or more transitions for every input symbol | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| this class of finite automata accepts empty strings (ε) | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| enumerate the three ways of presenting finite automata | (1) STATE DIAGRAM, (2) STATE/TRANSITION TABLE, (3) TRANSITION FUNCTION [SST] |
| this way of presenting finite automata is also called a transition graph | STATE DIAGRAM |
| this is a directed graph in that the vertices represent the internal states of the automaton, and the edges represent the transitions | TRANSITION GRAPH |
| in this way of presenting finite automata, the labels on the vertices are the names of the internal states, while the labels on the edges are the current values of the input symbols | STATE DIAGRAM |
| this way of presenting finite automata is where the columns represent the accepted input symbols, and the rows represent the states of the automaton | STATE/TRANSITION TABLE |
| this way of presenting finite automata is where each transition is represented by a function that takes a state (start) and an input symbol as arguments and returns a state (destination) | TRANSITION FUNCTION (δ) |
| the formal definition of a DFA states that it is defined by the 5-tuple: _____ | { Q, Σ, δ, q0, F } |
| in the 5-tuple definition of DFA, { Q, Σ, δ, q0, F }, what does Q mean? | FINITE SET OF STATES |
| in the 5-tuple definition of DFA, { Q, Σ, δ, q0, F }, what does Σ mean? | FINITE SET OF INPUT SYMBOLS (ALPHABET) |
| in the 5-tuple definition of DFA, { Q, Σ, δ, q0, F }, what does q0 mean? | INITIAL STATE |
| in the 5-tuple definition of DFA, { Q, Σ, δ, q0, F }, what does F mean? | SET OF FINAL STATES |
| in the 5-tuple definition of DFA, { Q, Σ, δ, q0, F }, what does δ mean? | a transition function |
| this is a mapping between Q x ∑ -> Q and takes as arguments a state and an input symbol, and returns a state | TRANSITION FUNCTION (δ) |
| if after all symbols in input stream w are consumed, the current state is one of the final states (F), then we ____ w | ACCEPT |
| these are those non-final state which transits in itself for all input symbol | TRAP/DEAD STATE |
| to describe the behavior of the DFA M on string w, we extend the transition function (δ) to apply to a state and a ____ rather than an input symbol | STRING |
| the extended transition function for M is written as this symbol | δ^(*) |
| the extended transition function for the DFA M has this formula | δ^(*) = Q x Σ^(*) -> Q |
| this extends δ from a single letter to a string | EXTENDED TRANSITION OF DFA (δ^(*)) |
| is a real computer a DFA or a NFA? | DFA since it has a definite/unique state that it goes through after an input |
| in order to write a program on ___, all possible scenarios for the alphabet and all possible transitions should be considered | DFA |
| knowledge of ___ is needed in order to write a program on a DFA | NFA |
| this is a finite automata where there exist a nondeterminism for a given input symbol, which may lead to more than one state or may not go to any state, meaning, empty transition | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| this is the only difference of the 5-tuple of DFA to NFA | the transition function (δ) |
| this is the mapping of sets of states and the alphabet set to the power set (Q x Σ -> 2^Q) | TRANSITION FUNCTION OF NFA (δ) |
| in this type of finite automata, given an input symbol and a state, next step can be more than one | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| in this type of finite automata, there may be or may not be a transition (empty transition) for a given input symbol | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| in this type of finite automata, when we check if w is acceptable by it, we determine all possible next states from all current states | NONDETERMINISTIC FINITE AUTOMATA (NFA) |
| in NFA, when do we reject a string? | if there is no possible path to any of the final states |
| DFA or NFA: great for modeling regular expressions | NFA |
| DFA or NFA: best used for string processing (e.g., grep, lexical analyzer) | NFA |
| DFA or NFA: cannot be implemented in practice | NFA |
| DFA or NFA: probabilistic models (e.g., toss of a coin/dice) could be viewed as extensions of it | NFA |
| DFA or NFA: some transitions could be non-deterministic | NFA |
| DFA or NFA: a transition could lead to a subset of states | NFA |
| DFA or NFA: not all symbol transitions need to be defined explicitly (if undefined, will go to a dead state) | NFA |
| DFA or NFA: accepts input if one of the last states is in F | NFA |
| DFA or NFA: generally easier to construct than the other | NFA |
| DFA or NFA: practical implementation has to be converted to be determinisic or in the form of parallelism | NFA |
| DFA or NFA: all transitions are deterministic and leads to exactly one state | DFA |
| DFA or NFA: for each state, transition on all possible symbols (alphabet) should be defined | DFA |
| DFA or NFA: accepts input if the last state is in F | DFA |
| DFA or NFA: sometimes harder to construct because of the number of states | DFA |
| DFA or NFA: practical implementation is feasible | DFA |
| every ___ is a special case of an ___ where each state has exactly one transition for each symbol in the alphabet | DFA; NFA |
| enumerate the two ways to convert an NFA to DFA | (1) SUBSET CONSTRUCTION, (2) LAZY CREATION [SC-LC] |
| this way of converting an NFA to DFA is when we list all possible states that the NFA can be in, and then we determine the transitions between them | SUBSET CONSTRUCTION |
| this way of converting an NFA to DFA involves listing all elements in the power set of the states of the NFA | SUBSET CONSTRUCTION |
| in this way of converting an NFA to DFA, the states that cannot be reached from the initial state are not included | SUBSET CONSTRUCTION |
| this way of converting an NFA to DFA avoids enumerating all of power set | LAZY CREATION |
| this way of converting an NFA to DFA is when we create a new state for each subset of states of the NFA as we construct the table | LAZY CREATION |
| does the machine ever terminate and stop waiting for the next input symbol? | NO |
| can a transition happen even without really consuming an input symbol? | YES |
| does a machine need to consume a symbol in order to go through a transition? | NO |
| can a single transition consume more than one symbol? | NO |
| this kind of NFA allows explicit epsilon (ε) transitions in finite automata | ε-NFA |
| this kind of NFA allows a transition from one state to another without consuming any additional input symbol | ε-NFA |
| ε-NFA are those NFAs with at least one explicit ____ defined | ε-TRANSITION |
| this is the mapping of sets of states and the union of the alphabet set with an empty string to the power set (Q x (Σ U {ε}) -> 2^Q) | TRANSITION FUNCTION OF ε-NFA (δ) |
| for an ε-NFA, before defining the transition function on a string, it is useful to first define what is known as the ____ | ε-CLOSURE |
| given a set of states S, this will give the set of states reachable from each state in S using only ε-transitions | ε-CLOSURE |
| an ε-closure of a state q can be written as ______ | ECLOSE(q) |
| the ε-closure of a state always includes ____ | itself |
| to find the ε-closure of two states, we just take the ____ of the ε-closures of each of the states | UNION |
| the ε-closure is represented by what symbol? | ε^(*) |
Created by:
user-1791948