Chapter 0, 1.1, 1.2, 4.2

Question 1

Define the objective of the Complexity Theory.

Answer 1

Classify problems as easy ones and hard ones.

Question 2

Define the objective of the Computability Theory.

Answer 2

The classification of problems is by those that are solvable and those that are not.

Question 3

Define Finite Automata.

Answer 3

Used in text-processing, compilers, and hardware design.

Question 4

Define Context-Free Grammar.

Answer 4

Used in programming languages and A.I.

Question 5

Define A ⊆ B.

Answer 5

A is a subset of B if every member of A is a member of B.

Question 6

Define A ⊂ B.

Answer 6

A is a proper subset of B of A is a subset of B and not equal to B. (If A ⊆ B and A ≠ B)

Question 7

Define A U B.

Answer 7

The union of A and B is when we combine all the elements in A and B into one set.

Question 8

Define A ∩ B.

Answer 8

The intersection of A and B is the set of elements both in A and B.

Question 9

Define A^c.

Answer 9

The complement of A is the set of all elements under consideration that are NOT in A.

Question 10

Define the Cartesian Product.

Answer 10

A x B is the set of all ordered pairs.

Question 11

Define the term Power Set.

Answer 11

The power set of A is the set of all subsets of A.

Question 12

Define Lemmas.

Answer 12

It is the proof statements that assist in the proof of another more significant statement.

Question 13

Define Corollaries.

Answer 13

The theorem or its proof can help us conclude that other statements are true.

Question 14

What is Proof by Construction?

Answer 14

We demonstrate how to construct the object. ex. We define a graph to k-regular if every node in the graph has degree k.

Question 15

What is Proof by Contradiction?

Answer 15

We assume that the theorem is false and then show that this assumption leads to an obviously false consequence. (refer to the Jack and Jill example)

Question 16

What is Proof by Induction?

Answer 16

Show that all the elements of an infinite set have a specified property.

Question 17

What is the purpose of the Diagonalization Method?

Answer 17

It is to show enumerations that cannot be complete.

Question 18

What is the theorem of Undecidability?

Answer 18

Computers are limited in a fundamental way (algorithmically unsolvable). i.e You are given a program and a precise specification of what it is supposed to do. You need to verify that the program performs as specified, but with the program AND specification are precise, it is unsolvable.

Question 19

Is a Turing Machine recognizable? If so, why?

Answer 19

Yes, recognizers are more powerful than deciders.

Question 20

If we have two infinite sets, how can we tell whether one is larger than the other or whether they are of the same size?

Answer 20

We use the Diagonalization Method. Two sets are the same size if the elements of one set can be paired with the elements of the other set.

Question 21

When is the function ƒ one-to-one?

Answer 21

It is one-to-one when it never maps two different elements to the same place that is if ƒ (a) ≠ ƒ(b) whenever a ≠ b.

Question 22

When is the function ƒ onto?

Answer 22

It is onto if it hits every element of B, that is if for every b ∈ B there is an a ∈ A such that f(a) = b.

Question 23

A set A is ______ if either it is finite or it has the same size as N.

Answer 23

countable

Question 24

List the steps for designing a DFA

Answer 24

1. Determine the # of states required. Define M = (Q (finite set of states), Σ (finite set of alphabet), δ (transition function), q0 (start state), F (set of accept states).
2. Create a transition table for the rules listed.
3. Draw the DFA according to the table.

Question 25

What are the regular operations in the regular languages?

Answer 25

1. Union: A ∪ B = {x| x ∈ A or x ∈ B}.
2. Concatenation: A ◦ B = {xy | x ∈ A and y ∈ B}.
3. Star: A∗ = {x1x2 . . . xk | k ≥ 0 and each xi ∈ A}.

Question 26

The class if regular languages is closed under what operation?

Answer 26

Union. If A1 and A2 are regular languages, so is A1 U A2.

Question 27

What is the difference between a deterministic finite automaton (DFA) and a nondeterministic finite automaton (NFA)?

Answer 27

Every state of a DFA always has exactly one exiting transition arrow for each symbol in the alphabet.

Question 28

How does an NFA compute?

Answer 28

Suppose we run an NFA on an input string and come to a state with multiple ways to proceed. For example, if we are in state q1 in N1 and that the next symbol is a 1, then the machine splits into multiple copies of itself and follows all the possibilities in parallel. If the next input symbol doesn’t appear on the exiting arrows, then the machine copy dies. If any of them are in an accept state, then the NFA accepts the string.

Question 29

What does forking do in NFA’s?

Answer 29

When the NFA splits to follow several choices, that corresponds to a process “forking” into several children, each proceeding separately. If at least on of these processes accepts, then the entire computation accepts.

Question 30

Define Unary Alphabet.

Answer 30

An alphabet containing only one symbol.