Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Fall 2017 > CSCI 311 Midterm 1 > Flashcards

CSCI 311 Midterm 1 Flashcards

1
Q

set

A

a collection of elements without any structure (except membership)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

set operations

A

union (U), intersection (∩), difference (-), complementation (overbar)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

union (U)

A

S1 U S2 = {x : x ∈ S1 or x ∈ S2}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

intersection (∩)

A

S1 ∩ S2 = {x : x ∈ S1 and x ∈ S2}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

difference (-)

A

S1 - S2 = {x : x ∈ S1 and x ∉ S2}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

complementation (overbar)

A

S overbar = {x : x ∈ U (the universal set), x ∉ S}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

U represents the

A

universal set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

∅ represents the

A

empty set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

S double overbar simply represents

A

S (the complement of the complement is the set)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

DeMorgan’s Law

A

the complement of S1 U S2 is the complement of S1 ∩ the complement of S2;
the complement of S1 ∩ S2 is the complement of S1 U the complement of S2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

subset

A

S1 ⊆ S if every element of S1 is also and element of S (S1 could be the same as S)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

proper subset

A

S1 ⊂ S if S contains at least one element not in S1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

disjoint

A

S1 ∩ S2 = ∅

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

power set

A

the set of all susbsets of S is the power set of S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Cartesian Product of Sets

A

S = S1 x S2 = {(x,y) : x ∈ S1, y ∈ S2}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

partition

A

S = S1 U S2 U … U Sn and for any Si ∩ Sj = ∅, i =/= j, then S1, S2, …, Sn is a partition of S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

functions

A

f : S1 → S2 is a rule that assigns a unique element of S2 to elements in S1 (S1 = domain, S2 = range)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

total function

A

f(x) ∈ S2 ∀ x ∈ S1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

relations

A

a subset of a Cartesian product of sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

a function can be a ? but a ? is not necessarily a function

A

relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

equivalence relations

A

E ] {(x,y) : …} ⊂ S x S is an equivalence relation if it is reflexive, symmetric, and transitive (notation ≡)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

graphs

A

vertices (singular) and edges (pairs > direction specified by pair order [vertex to vertex])

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

walk

A

travel the edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

path

A

no repeated edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

simple path

A

no repeated edge or vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

cycle

A

a walk from vi to itself with no repeated edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

simple cycle

A

a cycle with no repeated vertices except vi

28
Q

tree

A

a directed graph; no cycles; unique root; exactly one path from the root to any other vertices; no out edges (leaf nodes)

29
Q

proof techniques

A

induction (assume true, prove it, so it is true) and contradiction (arrive at conclusion we know is incorrect but we used logical steps)

30
Q

language

A

a set of strings on an alphabet Σ

31
Q

language operation

A

concatenation, reverse, length, empty string, substring

32
Q

alphabet (Σ)

A

a finite, non-empty set of symbols

33
Q

strings

A

a finite set of symbols from Σ

34
Q

concatenation

A

put strings together

e.g. w = ab and v = ba > wv = abba

35
Q

reverse (R)

A

notation: w^R; reverse of the string (e.g. abab > baba)

36
Q

length

A

|w| = n

37
Q

empty string (λ)

A

the string with no characters in it; |λ| = 0, λw = w and wλ = 0

38
Q

substring

A

any string of consecutive symbols in w
w^n : repeating w n times
w^∅ : λ

39
Q

Σ* (closure)

A

the set of strings obtained by concatenating 0 or more symbols from Σ

40
Q

Σ+ (positive closure)

A

Σ* - λ

41
Q

the complementation of a language with respect to Σ*

A

L overbar = Σ* - L

42
Q

the reverse of a language

A

L^R = {w^R : w ∈ L} (reverse of any string in language)

43
Q

concatenation of L1 and L2

A

L1L2 = {xy : x ∈ L1, y ∈ L2}

44
Q

grammars

A 
definted by G = (V, T, S, P) where
V = a finite set of variables
T = a finite set of terminal symbols
S ∈ V = the start variable
P = a finite set of productions/rules

e.g. G = ({S}, {a,b}, S, P) with P given by
S > aSb | λ

45
Q

the language generated by the grammar G

A

L(G) = {w ∈ T* : S *> w}

46
Q

equivalence of two grammars

A

two grammars G1 and G2 are equivalent if L(G1) = L(G2)

47
Q

input

A

string over a given alphabet

48
Q

storage

A

unlimited number of cells; each sell holds a single symbol, read/write

49
Q

control unit

A

in one of a finite number of internal states (can change internal state based on state in, input, and storage in some definite manner - transition function)

50
Q

transition function

A

(current state, input file, storage) > (next state, storage)
or
current configuration > next configuration

51
Q

deterministic automata

A

each move is uniquely determined by the current configuration

52
Q

non-deterministic automata

A

at each point, there may be several possible moves, so we can only predict a set of possible actions

53
Q

accepter

A

binary output response (yes/no)

54
Q

tansduer

A

string of symbols as output

55
Q

a DFA is defined by

A

M = (Q, Σ, δ, q0, F) with
Q = a set of internal states
Σ = a finite set of symbols called the input alphabet
δ = transition function; Q x Σ > Q a total function
q0 ∈ Q = the initial state (only one)
F = a subset of Q; a set of final states

56
Q

the language accepted by the DFA M = (Q, Σ, δ, q0, F) is

A

the set of strings on Σ accepted by M: L(M) = {w ∈ Σ* : δ*(q0, w) ∈ F}

57
Q

δ* : Q x Σ* (is/is not) a total function

A

is

58
Q

the complementation of L(M)

A

{w ∈ Σ* : δ*(q0, w) ∉ F}

59
Q

the DFA for the complementation of a language

A

switch all final states to nonfinal and vice versa

60
Q

regular language

A

a language is regular if and only if there exists some DFA, M, such that L = L(M)

61
Q

NFA defined by

A

M = (Q, Σ, δ, q0, F) with δ = Q x (Σ U {λ}) > 2^Q

62
Q

differences in NFA from DFA

A
  1. the range of δ is in 2^Q (i.e. the value of δ is not a single state, but a set of states
  2. λ can be the second argument of δ (i.e. lambda transitions allowed)
  3. δ(qi, a) = ∅ is possible (trap state)
63
Q

the language of an NFA

A

given M = (Q, Σ, δ, q0, F), L(M) = {w ∈ Σ* : δ*(q0, w) ∩ F =/= ∅}

64
Q

two finite accepters M1 and M2 are equivalent if

A

L(M1) = L(M2)

65
Q

a DFA is a (subset/proper subset/not a subset) of an NFA, meaning ?

A

proper subset; for any NFA you can convert to a DFA

Fall 2017 (24 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions