Brainscape's Knowledge GenomeTM

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


See full index

Software Douchebags > SE3310 Final > Flashcards

SE3310 Final Flashcards

1
Q

What is a set?

A

An unordered collection of unique elements

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

What is a language?

A

A set of strings

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

What is computation?

A

Finding answers to yes/no questions (such as, is s in L?)

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

What is the range of a function?

A

The set of all outputs

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

What is a Finite State Transducer?

A

A DFA with outputs defined (for each transition)

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

What is the domain of a function?

A

The set of all possible inputs

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

What is a regular language?

A

A language where there exists a finite automaton that recognized it

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

What are the 2 interpretations for how NFAs function?

A
  • Parallel computation (execute all paths concurrently)

- Lucky guess (Always picks the correct path)

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

T/F: Every NFA has an equivalent DFA

A

T

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

T/F: Every DFA has an equivalent NFA?

A

T - a DFA is an NFA silly

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

T/F: Regular languages are closed under kleene star

A

T

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

T/F: Regular languages are closed under complement

A

T

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

What are the 6 steps in the pumping lemma for regular languages proof?

A
  1. Assume L is regular
  2. Let p = pumping length
  3. Pick string s (s must be in L, and size of s >= p)
  4. Examine all cases for dividing s = xyz
  5. For each case, find value i such that s’=x y^i z
  6. Conclude that there is no way to divide s into 3 parts xyz such that y can be pumped. Therefore L is not regular.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

T/F: All context free languages are regular

A

F : regular languages are a subset of context free languages

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

T/F: All DFA’s have an equivalent CFG

A

T

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

What are the restrictions on the size of y in the pumping lemma for regular languages proof?

A

|y| > 0

|xy| <= p

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

What is a pushdown automaton?

A

Essentially an NFA with ability to read/write from a stack

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

What are the components of a turing machine?

A
  • tape
  • head
  • control
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the requirements for an algorithm / effective method?

A
  1. Finite # steps
  2. Always produces results
  3. Result is always correct
  4. Could in principle be done by human
  5. Only needs to follow instruction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What does the church-turing thesis declare?

A

Every effectively calculable function is a computable function (i.e. A problem can only be solved by an algorithm if it can be solved by a TM)

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

What is a recursive language?

A

A decidable language: M decides L if it halts and accepts all s in L AND halts and rejects for all s NOT in L

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

What is a recursively-enumerable languages?

A

A recognizable language: M recognizes L if it halts and accepts all s in L

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

T/F : All recognizable languages are decidable?

A

F: all decidable languages are recognizable

24
Q

What is required for a system to be Turing complete?

A

Must be able to simulate any turing machine

25
What is required for a system to be capable of universal computation?
- read/write from memory - if statements - go to statements
26
What is the Halting problem?
HALT consists of all TM's that always halt. If you could decide HALT, you could prevent ever entering into an infinite loop
27
Why does the halting problem matter?
1. Proves existence of undecidable problems 2. Proves you cannot solve the entshiedungsproblems (decision problem) 3. Invented notion of stored program computer
28
T/F: Atm is recognizable
T
29
T/F: Atm is decidable
F
30
T/F: The complement of Atm is recognizable
F
31
What is U?
The universal TM. I recognizes , the set of accepting TM/string combos (Atm)
32
What is running time?
t(n) : The max number of steps that a TM takes on an n-character string
33
What is DTIME?
The time complexity class of all languages decidable by a DTM (Deterministic TM)
34
What is P?
The class of all problems solvable by a DTM in polynomial time
35
What is NP?
The class of all problems solvable by a NTM in polynomial time
36
What is the running time of a NTM?
Maximum number of steps M takes in every computational path on any n-character string
37
Does NP=P?
Probably not
38
What is NP-complete?
Sub-class of NP, problems are at least as hard as all others in NP
39
How can you prove that a language is NP-complete?
1. B e NP | 2. For all A e NP, A <= B where B is NP-complete
40
What does the Cook-Levin theorem propose?
Proved that SAT is NP-complete, so proving SAT <= B is enough to prove B is NP-Complete
41
What is NP-Hard?
Class of problems that are as hard or harder than any NP problem
42
How do you prove a problem is NP-Hard?
Prove X <= B , where X is NP-Hard
43
What class of problems contains optimization problems?
NP-Hard
44
What is a probabilistic turing machine?
A PTM uses random bits to pick exactly one path to follow at each branch
45
What is BPP?
Bounded-Error probabilistic polynomial-time: Class of problems solvable by a PTM in polynomial time with error probability <= 1/3
46
T/F: P = BPP
Maybe
47
What is BQP?
BQP (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3
48
T/F: All context-free languages are recursive
T
49
T/F: All recursively enumerable languages are recursive?
F
50
T/F: All regular languages are decidable?
T
51
T/F: All problems in P are also in BPP
T
52
T/F: All problems in NP are in NP-Hard
F
53
T/F: All NP-complete problems are also in NP
T
54
Can a turing machine contain just one state?
No: must contain at least 2 distinct states: accept and reject
55
Can the tape alphabet of a TM be the same as the input alphabet?
No - tape alphabet must contain the empty symbol |_| while the input alphabet cannot contain it
56
Can a Turing machine's head ever be in the same location in two successive steps?
Yes - if the TM attempts to move its head off the left-hand end of the tape, it remains in the same tape cell

Software Douchebags (15 decks)

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