CSCI 311 Midterm 1

Question 1

set

Answer 1

a collection of elements without any structure (except membership)

Question 2

set operations

Answer 2

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

Question 3

union (U)

Answer 3

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

Question 4

intersection (∩)

Answer 4

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

Question 5

difference (-)

Answer 5

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

Question 6

complementation (overbar)

Answer 6

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

Question 7

U represents the

Answer 7

universal set

Question 8

∅ represents the

Answer 8

empty set

Question 9

S double overbar simply represents

Answer 9

S (the complement of the complement is the set)

Question 10

DeMorgan’s Law

Answer 10

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

Question 11

subset

Answer 11

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

Question 12

proper subset

Answer 12

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

Question 13

disjoint

Answer 13

S1 ∩ S2 = ∅

Question 14

power set

Answer 14

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

Question 15

Cartesian Product of Sets

Answer 15

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

Question 16

partition

Answer 16

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

Question 17

functions

Answer 17

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

Question 18

total function

Answer 18

f(x) ∈ S2 ∀ x ∈ S1

Question 19

relations

Answer 19

a subset of a Cartesian product of sets

Question 20

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

Answer 20

relation

Question 21

equivalence relations

Answer 21

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

Question 22

graphs

Answer 22

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

Question 23

walk

Answer 23

travel the edges

Question 24

path

Answer 24

no repeated edges

Question 25

simple path

Answer 25

no repeated edge or vertices

Question 26

cycle

Answer 26

a walk from vi to itself with no repeated edges

Question 27

simple cycle

Answer 27

a cycle with no repeated vertices except vi

Question 28

tree

Answer 28

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

Question 29

proof techniques

Answer 29

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

Question 30

language

Answer 30

a set of strings on an alphabet Σ

Question 31

language operation

Answer 31

concatenation, reverse, length, empty string, substring

Question 32

alphabet (Σ)

Answer 32

a finite, non-empty set of symbols

Question 33

strings

Answer 33

a finite set of symbols from Σ

Question 34

concatenation

Answer 34

put strings together | e.g. w = ab and v = ba > wv = abba

Question 35

reverse (R)

Answer 35

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

Question 36

length

Answer 36

|w| = n

Question 37

empty string (λ)

Answer 37

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

Question 38

substring

Answer 38

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

Question 39

Σ* (closure)

Answer 39

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

Question 40

Σ+ (positive closure)

Answer 40

Σ* - λ

Question 41

the complementation of a language with respect to Σ*

Answer 41

L overbar = Σ* - L

Question 42

the reverse of a language

Answer 42

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

Question 43

concatenation of L1 and L2

Answer 43

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

Question 44

grammars

Answer 44

``` 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 | λ

Question 45

the language generated by the grammar G

Answer 45

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

Question 46

equivalence of two grammars

Answer 46

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

Question 47

input

Answer 47

string over a given alphabet

Question 48

storage

Answer 48

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

Question 49

control unit

Answer 49

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)

Question 50

transition function

Answer 50

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

Question 51

deterministic automata

Answer 51

each move is uniquely determined by the current configuration

Question 52

non-deterministic automata

Answer 52

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

Question 53

accepter

Answer 53

binary output response (yes/no)

Question 54

tansduer

Answer 54

string of symbols as output

Question 55

a DFA is defined by

Answer 55

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

Question 56

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

Answer 56

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

Question 57

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

Answer 57

is

Question 58

the complementation of L(M)

Answer 58

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

Question 59

the DFA for the complementation of a language

Answer 59

switch all final states to nonfinal and vice versa

Question 60

regular language

Answer 60

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

Question 61

NFA defined by

Answer 61

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

Question 62

differences in NFA from DFA

Answer 62

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)

Question 63

the language of an NFA

Answer 63

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

Question 64

two finite accepters M1 and M2 are equivalent if

Answer 64

L(M1) = L(M2)

Question 65

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

Answer 65

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