Finals

Question 1

Set of strings of length exactly k

Answer 1

Powers of an alphabet

Question 2

The objects and notions

Answer 2

Definition

Question 3

Expresses that some objects

Answer 3

Mathematical statement

Question 4

Convincing logical argument

Answer 4

Proof

Question 5

Statement proved true

Answer 5

Theorem

Question 6

Another more significant statement

Answer 6

Lemma

Question 7

Concluded from a theorem

Answer 7

Corollaries

Question 8

Assume that the theorem is false

Answer 8

Proof by contradiction

Question 9

Proving statements

Answer 9

Proof by induction

Question 10

Proves that it is true

Answer 10

Basis

Question 11

how efficiently problems can be solved on a model of computation using algorithm

Answer 11

Theory of computation

Question 12

3 major branches

Question 13

Set of allowable operations

Answer 13

Model of computation

Question 14

Study of abstract machine

Answer 14

Automata theory

Question 15

Self acting machine

Answer 15

Automata

Question 16

Recognized by an automaton

Answer 16

Formal language

Question 17

Different kinds of automata

Answer 17

Finite
Push down
Turing

Question 18

Finite automata examples

Answer 18

Elevators
Vending machine
Lexical analyzers

Question 19

3 central areas

Question 20

Fundamental mathematical properties

Answer 20

TOC

Question 21

Problems computationally hard

Answer 21

Complexity

Question 22

Efficiently solvable

Answer 22

Easy

Question 23

Can’t be solved easily

Answer 23

Hard

Question 24

degree of computational difficulty

Answer 24

Motivation of complexity theory