MEMO

1. A model abstracts from (a) foundation concepts; (b) details; (c) utility; (d) simplicity; (e) none of these

2. Computing is traditionally viewed as (a) interaction; (b) algebra; (c) intelligence; (d) the execution of algorithms; (e) what the Internet does

3. Top-down theoretical results in computer science use (a) empirical data; (b) testing benchmarks; (c) conjecture and proof; (d) democratic vote; (e) none of these

Logic

1. Predicate logic is a(n) (a) algorithm; (b) language of assertions; (c) language of arithmetic expressions; (d) set of symbols; (e) set of operations

2. An assertion’s value is (a) true; (b) a symbol; (c) a number; (d) true or false; (e) none of these

3. ("x) x = x + 1 is (a) a numeric expression; (b) false; (c) true; (d) an assignment; (e) none of these

4. ($x) x = x + 1 is (a) a numeric expression; (b) false; (c) true; (d) an assignment; (e) none of these

5. Quantifiers ____ variables for meaningful use (a) give values to; (b) take values from; (c) bind; (d) assign; (e) declare

6. Inference rules maintain (a) completeness; (b) consistency; (c) validity; (d) satisfiability; (e) falsehood

7. An inference rule that never produces contradictions is (a) complete; (b) incomplete; (c) inconsistent; (d) sound; (e) useless

8. (p Ù (p ® q)) ® q is (a) false; (b) Modus Ponens; (c) inconsistent; (d) not always true; (e) none of these

9. Predicate calculus extends propositional logic with (a) inference; (b) negation; (c) implication; (d) variables; (e) quantifiers

10. A validity-maintaining procedure for deriving sentences in predicate logic from other sentences is a(n) (a) proof; (b) theorem; (c) algorithm; (d) inference rule; (e) inference chain

11. p iff q means (a) p Þ q Ù q Þ p; (b) p Þ q Ú q Þ p; (c) p Þ q but not necessarily q Þ p; (d) q Þ p but not necessarily p Þ q; (e) none of these

12. Inference rules enable derivation of (a) axioms; (b) other inference rules; (c) new true assertions; (d) percepts; (e) none of these

13. (T-F) If we live on Pluto, then cats have wings.

14. (T-F) If airplanes fly, then 1 + 1 = 2.

15. (T-F) If the earth is flat, then 1 + 1 = 2.

16. (T-F) If the earth is round, then 1 + 1 = 3.

17. (T-F) If trees have ears, then dogs have wings.

18. (T-F) 2 + 2 = 4 only if 1 + 1 = 3.

19. An if-then assertion whose first clause is true is (a) never true; (b) sometimes true; (c) always true; (d) meaningless; (e) none of these

20. A rigorous demonstration of the validity of a theorem or assertion is called a(n) (a) proof; (b) argument; (c) deduction; (d) contradiction; (e) induction

Sets

1. {1,2,3} È {2,4,5} = (a) {}; (b) {1,2}; (c) 2; (d) {2}; (e) {1,2,3,4,5}

2. {1,2,3} Ç {2,4,5} = (a) {}; (b) {1,2}; (c) 2; (d) {2}; (e) {1,2,3,4,5}

3. (T-F) {1, 3} Î ({1, 3, 5} Ç {1, 5})

4. (T-F) Æ Í Æ

5. (T-F) Æ Î Æ

6. (T-F) Æ Í {Æ}

7. (T-F) Æ Î {Æ}

8. {} is a subset of (a) itself only; (b) no set; (c) all sets; (d) only infinite sets; (e) none of these

9. A string is (a) a set of symbols; (b) a sequence of characters; (c) a relation; (d) a set of sequences; (e) none of these

10. A language is (a) a set of symbols; (b) a sequence of characters; (c) a relation; (d) a set of strings; (e) none of these

11. The null set is a (a) member of itself; (b) member of any set; (c) subset of any set; (d) superset of any set; (e) none of these

12. The power set of A is (a) the set of all members of A; (b) a subset of A; (c) the set of subsets of A; (d) the null set; (e) an intersection

13. For all sets A (a) A Í A; (b) A Î A ; (c) A ≠ A; (d) all of these; (e) none of these

Relations

1. A relation on set A is (a) an element of A; (b) a subset of A; (c) an element of A ´ A; (d) a subset of A ´ A; (e) none of these

2. The Cartesian product of two sets is a(n) (a) set of sets; (b) ordered pair; (c) set of ordered pairs; (d) subset of the two sets; (e) union of the two sets

3. A × B means (a) the set containing elements of A and B; (b) the set of ordered pairs of elements chosen from A and B respectively; (c) any relation of elements of A and B; (d) a function from A to B; (e) none of these

4. We may represent a Cartesian product as a (a) linear array; (b) linked list; (c) matrix; (d) tree; (e) none of these

5. A relation is not a (a) set of ordered pairs; (b) set of numbers; (c) subset of a Cartesian product; (d) way to express how two sets relate; (e) it is all of these

6. A relation on set A is a (a) member of A; (b) subset of A; (c) member of A ´ A; (d) ; (e) none of these

7. In a reflexive relation on A (a) each element of A is related to itself; (b) each ordered pair (a, b) is matched by (b, a); (c) if aRb and bRc then aRc; (d) the diagonal of the matrix is empty; (e) none of these

8. In a symmetric relation on A (a) each element of A is related to itself; (b) each ordered pair (a, b) is matched by (b, a); (c) if aRb and bRc then aRc; (d) the diagonal of the matrix is empty; (e) none of these

9. In a transitive relation on A (a) each element of A is related to itself; (b) each ordered pair (a, b) is matched by (b, a); (c) if aRb and bRc then aRc; (d) the diagonal of the matrix is empty; (e) none of these

Functions

1. A function f: {1,2,3} ® {0,1} is a set of (a) integers; (b) ordered pairs; (c) sets; (d) relations; (e) none of these

2. f: {1,2,3} ® {0,1}

3. A function is a relation in which (a) no right-hand member is paired with more than one left-hand member; (b) no left-hand member is paired with more than one right-hand member; (c) every right-hand member is paired with more than one left-hand member; (d) every left-hand member is paired with more than one right-hand member; (e) none of these

4. A function is a(n) (a) sequence; (b) symmetric relation; (c) mapping; (d) intersection; (e) none of these

5. Predicates are (a) transitive relations; (b) sets of integers; (c) sequences; (d) functions on integers; (e) functions that return truth values

6. A relation in which every right-hand member is paired with exactly one left-hand member is (a) transitive; (b) symmetric; (c) reflexive; (d) a function; (e) none of these

7. All algorithms compute (a) sequences; (b) relations; (c) matrices; (d) functions; (e) none of these

8. A function is a set of values (x, y) in which x is chosen from the (a) base case; (b) set of integers; (c) domain; (d) range; (e) none of these

9. A function is a set of values (x, y) in which y is chosen from the (a) base case; (b) set of integers; (c) domain; (d) range; (e) none of these

10. A recursive method (a) always calls itself when it runs; (b) calls itself subject to certain conditions; (c) calls itself not more than once; (d) never calls itself only once; (e) uses while to loop

11. (T-F) In a recursive method, when the base case applies, the method calls itself.

Proofs

1. A proof that begins by asserting a claim and proceeds to show that the claim cannot be true is by (a) induction; (b) construction; (c) contradiction; (d) prevarication; (e) none of these

2. A proof that proceeds by showing the existence of something desired is by (a) induction; (b) construction; (c) contradiction; (d) prevarication; (e) none of these

3. A proof that shows that a certain property holds for all natural numbers is by (a) induction; (b) construction; (c) contradiction; (d) prevarication; (e) none of these

4. Proofs by contradiction (a) dismiss certain rules of logic; (b) misrepresent facts; (c) start by assuming the opposite of what is to be proven; (d) end by rejecting what is to be proven; (e) none of these

5. A rigorous demonstration of the validity of a theorem or assertion is called a(n) (a) proof; (b) argument; (c) deduction; (d) contradiction; (e) inference

6. The principle of mathematical induction states that if zero is in a set A, and if membership of any value x in A implies that (x + 1) is in A, then (a) A is all natural numbers; (b) the proof is invalid; (c) A is the null set; (d) A is x; (e) A is {x}

7. In an inductive proof, showing that P(0) is true is (a) the base step; (b) the inductive step; (c) unnecessary; (d) sufficient to prove P(x + 1); (e) sufficient to prove P(x) for all x

8. In an inductive proof, showing that P(x) implies P(x + 1) is (a) the base step; (b) the inductive step; (c) unnecessary; (d) sufficient to prove P(x) for some x; (e) sufficient to prove P(x) for all x

9. In an inductive proof, showing that P(0) is true, and that P(x) implies P(x + 1), is (a) the base step; (b) the inductive step; (c) unnecessary; (d) sufficient to prove P(x) for some x; (e) sufficient to prove P(x) for all x

10. An inductive proof with graphs might proceed by (a) showing a contradiction; (b) showing a counter-example; (c) considering all graphs one by one; (d) starting with some simple graph and adding one vertex or edge; (e) none of these

11. The base step in an inductive proof might (a) show that P(0) is true, and that P(x) implies P(x + 1); (b) show that P(0) is true; (c) show that that P(x) implies P(x + 1); (d) give a counterexample; (e) assume the opposite of what is to be proven

12. The inductive step in an inductive proof might (a) show that P(0) is true, and that P(x) implies P(x + 1); (b) show that P(0) is true; (c) show that that P(x) implies P(x + 1); (d) give a counterexample; (e) assume the opposite of what is to be proven

13. An entire inductive proof might (a) show that P(0) is true, and that P(x) implies P(x + 1); (b) show that P(0) is true; (c) show that that P(x) implies P(x + 1); (d) give a counterexample; (e) assume the opposite of what is to be proven

Data structures

1. To add to a stack, we carry out a(n) _____ operation. (a) dequeue; (b) enqueue; (c) pop; (d) push; (e) traversal

2. The first-in, first-out structure is the (a) list; (b) array; (c) queue; (d) stack; (e) tree

3. A tree has no (a) edges; (b) vertices; (c) paths; (d) cycles; (e) connectivity

4. To model a hierarchy, it is most convenient to use a(n) (a) simple type; (b) array; (c) linked list; (d) binary search tree; (e) tree

5. A graph is (a) a set of integers; (b) a set of vertices; (c) a set of vertices and a set of edges; (d) a set of edges; (e) a set of paths

6. A set of vertices and a set of edges define (a) a function; (b) a graph; (c) a stack; (d) a binary tree; (e) a path

7. To add to a stack, we carry out a(n) ______ operation. (a) dequeue; (b) enqueue; (c) pop; (d) push; (e) traversal

8. The push operation is carried out on (a) lists; (b) trees; (c) arrays; (d) stacks, (e) queues

9. _________ on a stack is accessible. (a) the top item; (b) the root; (c) the bottom item; (d) the highest-valued item (e) the lowest-valued item.

10. The stack is a _____-in, first-out structure. (a) lowest; (b) highest; (c) first; (d) last; (e) none of these

11. To look at a value in a stack requires (a) random access; (b) dequeueing; (c) enqueueing; (d) push; (e) pop

12. To delete from a stack, we carry out a(n) ______ operation. (a) dequeue; (b) enqueue; (c) pop; (d) push; (e) traversal

13. A series of edges in a graph that connect two vertices is called (a) a path; (b) a cycle; (c) a connection; (d) a tree; (e) a collection

14. A series of edges in a graph that form a path from a vertex to itself is (a) a spanning path; (b) a cycle; (c) a connection; (d) a tree; (e) an edge

Short-answer questions

1. Write “p Þ q Ù q Þ p” another way.

1. Countable sets

1. The set of strings of length k, over a finite alphabet, for given constant k, is (a) countably infinite; (b) finite; (c) uncountable; (d) undecidable; (e) none of these

2. Two sets have the same cardinality if (a) they are both finite; (b) neither is strictly included in the other; (c) a bijection exists between them; (d) they are both infinite; (e) none of these

3. The natural numbers (a) can be paired up with the reals; (b) are countable; (c) are uncountable; (d) are as numerous as any set; (e) none of these

4. S is by convention (a) finite; (b) countable; (c) uncountable; (d) a sequence; (e) none of these

5. S^* is (a) finite; (b) countable; (c) uncountable; (d) an alphabet; (e) none of these

6. S^* is (a) a number; (b) a symbol; (c) an alphabet; (d) a language; (e) none of these

7. An alphabet is (a) finite; (b) infinite; (c) finite or infinite; (d) uncountable; (e) none of these

8. A language is (a) finite; (b) infinite; (c) finite or infinite; (d) uncountable; (e) none of these

9. A bijection is a(n) (a) partition; (b) binary number; (c) one-to-one correspondence; (d) proof; (e) none of these

10. ____ injections are bijections (a) all; (b) some; (c) no; (d) binary; (e) none of these

11. ____ surjections are bijections (a) all; (b) some; (c) no; (d) binary; (e) none of these

12. ____ bijections are injections (a) all; (b) some; (c) no; (d) binary; (e) none of these

13. ____ bijections are surjections (a) all; (b) some; (c) no; (d) binary; (e) none of these

14. ____ surjections are injections (a) all; (b) some; (c) no; (d) binary; (e) none of these

15. ____ injections are surjections (a) all; (b) some; (c) no; (d) binary; (e) none of these

16. A surjection maps (a) from all elements of its domain; (b) no two values to the same result; (c) randomly; (d) to all elements of its range; (e) none of these

17. Two sets have the same cardinality iff there is a ____ between them (a) relation; (b) bijection; (c) function; (d) assertion; (e) injection

18. The cardinality of the set of natural numbers is ____ the cardinality of the set of rational numbers (a) the same as; (b) greater than; (c) less than; (d) not comparable to; (e) none of these

19. The set of natural numbers is (a) indescribable; (b) finite; (c) countably infinite; (d) uncountably infinite; (e) none of these

20. The set of Java programs is (a) small; (b) finite in number; (c) countable; (d) uncountable; (e) none

21. Enumerability is an attribute of ____ sets (a) no; (b) all; (c) all infinite; (d) all countable; (e) none of these

2. Uncountable sets

1. What proof method was used by Cantor to show that the reals are uncountable? (a) inductive; (b) diagonal; (c) constructive; (d) immediate; (e) none of these

2. Which of these sets is countable? i. strings ii. streams iii natural numbers iv real numbers. (a) i and ii; (b) i and iii; (c) ii and iii; (d) ii and iv; (e) none of these

3. Cantor showed that the reals are (a) infinite; (b) countable; (c) uncountable; (d) dense; (e) none of these

4. Cantor’s proof about the cardinalities of real and natural numbers was by (a) induction; (b) diagonalization; (c) construction; (d) statistical methods; (e) none of these

5. A diagonal proof is by (a) induction; (b) contradiction; (c) construction; (d) statistical methods; (e) none of these

6. The cardinality of the set of real numbers is ____ the cardinality of the set of rational numbers (a) the same as; (b) greater than; (c) less than; (d) not comparable to; (e) none of these

7. The set of real numbers is (a) indescribable; (b) finite; (c) countably infinite; (d) uncountably infinite; (e) none of these

8. We can disprove the existence of an enumeration of all the real numbers by assuming an enumeration exists and defining real whose nth digit, for all n, is different from ____ digit of the n the real in the supposed enumeration (a) each; (b) the first; (c) the nth; (d) the (n+1)th; (e) the last

9. The number of predicates on a set of cardinality n is (a) n; (b) 2n; (c) n²; (d) 2ⁿ; (e) none

10. The predicates on natural numbers are (a) few; (b) finite in number; (c) countable; (d) uncountable; (e) none

11. By what proof method was it shown that the real numbers are uncountable? (a) direct; (b) induction; (c) diagonal; (d) counter-example; (e) none of these

3. Incompleteness

1. Gödel’s theorem was proven in the ___ century (a) 18th; (b) 19th; (c) 20th; (d) 21st; (e) none of these

2. A logical system in which no false assertion can be proven is (a) consistent; (b) complete; (c) ambiguous; (d) paradoxical; (e) none of these

3. A logical system in which every true assertion can be proven is (a) consistent; (b) complete; (c) ambiguous; (d) paradoxical; (e) none of these

4. Gödel numbers (a) are cardinalities; (b) are reals; (c) encode assertions; (d) encode programs; (e) none of these

5. Gödel’s incompleteness theorem was proven by (a) induction; (b) diagonalization; (c) construction; (d) statistical methods; (e) none of these

4. Streams and coinduction

1. Induction is used to define (a) branch control structures; (b) finite objects; (c) infinite objects; (d) finite sets; (e) none of these

2. Coinduction is used to define sets of (a) branch control structures; (b) finite objects; (c) infinite objects; (d) finite sets; (e) none of these

3. A coinductive definition has no (a) base case; (b) inductive case; (c) endpoint; (d) purpose; (e) none of these

4. Coinduction may define sets of (a) numbers; (b) programs; (c) proofs; (d) strings; (e) streams

5. The wellfoundedness axiom states that the notion of a set belonging to itself is (a) well-founded; (b) meaningless; (c) doubtful; (d) mandatory; (e) none of these

6. S^¥ is a set of (a) numbers; (b) symbols; (c) strings; (d) streams; (e) none of these

7. S^¥ is (a) finite; (b) countable; (c) uncountable; (d) an alphabet; (e) none of these

1a. Proof of countability

1. What sorts of sets may be uncountable? How can this be shown?

2. Using set notation, define of the set of infinite sequences of

a. decimal digits

b. truth values

c. symbols chosen from the symbol set A

3. Show that the following sets are countable:

a. Binary numerals

b. Pairs of natural numbers

c. Natural numbers that are multiples of 5

d. English-language sentences

e. Java programs

f. Formulas in predicate logic

g. Proofs

h. Rational numbers

i. Finite bit vectors

j. Cells in a 3D grid

k. prime numbers

l. even numbers

m. numbers with an even number of digits

n. Java programs

o. English sentences

4. Describe a bijection f from the set of natural numbers to the set of natural numbers whose decimal representations end in zero. If ENDS_ZERO is this set, you must show that each natural number maps to a member of ENDS_ZERO under f, and also that f maps each member of ENDS_ZERO to some natural number.

1b. Proof of uncountability

1. Consider a mobile robot that at each step of its existence, must decide whether to turn left or right 5 degrees, or go forward, based on its percept and state at that instant. Define a robot’s output behavior as a set of infinite sequences of outputs in the set {left, forward, right}. Use Cantor’s diagonal proof method to show that the set of all possible robot behaviors is uncountable.

2. Show that the power set of the set of strings over a finite alphabet S is uncountable (see proof in handout that the set of sets of natural numbers is uncountable).

3. Consider the following: “Cantor constructed an enumeration of all natural numbers. He showed that a particular value in this list is not a real number. Cantor’s proof is by induction.” Justify this or correct it, if it is in error.

4. Explain what this diagram is used to show.

5.       A predicate on natural numbers, p : N ® {0,1} is a function that may be represented as an infinite sequence seq_p of values in {0,1}, where the jth bit in the sequence is the value of p(j). For example, if p is the predicate odd, then the jth bit of the sequence seq_p is 1 if j is odd, 0 if j is even.
   A Java program computes a certain predicate if, on input of some number x, the program outputs a 1 if p(x) = 1, and outputs a 0 when p(x) = 0. Any program can be described as a finite sequence of symbols, e.g., bits.
   Use Cantor’s proof method to show that some predicates are undecidable by any program; that is, for some predicate p there is no program that computes the function p.
   Hint: Show that no bijection exists between the set of Java programs and the set of predicates.

6. Comment on the following: “The cardinality of the rational numbers is greater than that of the natural numbers, because between any two rational numbers there is another rational number.”

7. Show that the set of predicates over natural numbers is uncountable.

8. Show that the set of predicates over strings is uncountable.

9. Explain why the set L _S of all languages over S is uncountable.

10. In your own words, what does assertion G in the proof of Gödel’s theorem say, and how is that used in the proof?

11. Consider the set of infinite streams of ASCII characters.
(a) Show that it is uncountable.
(b) Name the proof method
(c) For each and every sequence in this set, does there exist a Java program with no input, but with an infinite output loop, that outputs the sequence? Why or why not?

12. Consider the set of sets of natural numbers.
(a) Describe a way to represent a set of natural numbers as a sequence of truth values.
(b) Show the set of sets of natural numbers is uncountable.
(c) Name the proof method

13. Answer the following “refutation” of Cantor’s proof: “Look, you show me a particular ordering of strings and prove that this enumeration omits some real number. So one way to list all real numbers fails by being incomplete. So what? Maybe someone could come up with a different ordering that would include all reals.”

1. For what sets can elements of the set be placed in one-to-one correspondence with the natural numbers?

2. For what category of sets is it true that elements of the set cannot be placed in one-to-one correspondence with the natural numbers?

3. What is the name of the proof method that shows uncountability of sets?

4. What proof method shows countability of sets?

5. What attribute of a set does the diagonal proof method show?

6. What is the term for an infinite sequence? Are any sets of infinite sequences countable? Are any uncountable?

7. What type of definition can define an infinite number of finitely large objects?

8. What type of definition can define an infinite number of infinitely large objects?

9. Godel’s historic proof showed that no system of logic is both _____ and ____.

10. What is a bijection?

11. If a bijection can be defined between set A and the natural numbers, then what can be said about set A?

12. If a bijection cannot be defined between set A and the

13. According to set theory, which of these sets are finite (F)? Countably infinite (C)? Uncountable (U)? For at least one set, explain your result in a phrase.
___ signed integers
___ quotients of two integers
___ integers from 0 to 10¹⁰⁰⁰⁰⁰
___ reals from 4.0 to 5.0
___ reals of the form d.333333…, d is a natural number
___ reals
___ sets of integers
___ functions on integers
___ bitstrings of finite length
___ Java programs
___ infinitely long lectures

1c. Coinductive definition

1. Formally define the set of infinite bit streams.

2. Formally define the set of infinite sequences of pairs of bits.

3. Formally define the set of infinite sequences of pairs of symbols from alphabet S.

4. Formally define the set of infinite sequences of input pairs and output strings.

5. Formally define the set of infinite sequences of pairs of bits.

6. Formally define the set of infinite sequences of symbols from alphabet S.

7. How many infinite sequences of input pairs and output strings exist?

8. Formally define the set of infinite bit streams.

Consider the set of infinite sequences of inputs and outputs, when inputs are pairs of strings of symbols in the set DIGITS, and outputs are strings of DIGITS.

1. Formally define the set of output strings.

2. How many different input pairs exist?

3. How many different output strings?

4. Formally define the set of infinite sequences of input/output pairs of natural numbers.

5. Formally define the set of infinite sequences of input pairs and output strings.

6. What is the cardinality of the set of infinite sequences of input pairs, and why?

7. What is the cardinality of the set of infinite sequences of input pairs and output strings, and why?

8. Distinguish countable from uncountable sets, with examples, and explain how a set can be shown to be uncountable. Name and describe the proof technique. Relate to results by Gödel and Turing.

1d. Formal language notation

1. What is a string?

2. What is l?

3. What is standard notation for a null string?

4. What is a language?

5. What is the name for a set of strings over an alphabet?

6. What is the standard notation for an alphabet?

7. What is S in standard notation?

8. If S is an alphabet, then what is S^k?

9. What is the notation for the set of strings of length k over alphabet S?

1. Deterministic finite automata

1. In our discussion of DFAs, d is (a) a function; (b) an alphabet; (c) a symbol; (d) a string; (e) none of these

2. In our discussion of languages, l represents (a) a function; (b) an alphabet; (c) a symbol; (d) a string; (e) none of these

3. In our discussion of languages, S is (a) a function; (b) an alphabet; (c) a symbol; (d) a string; (e) none of these

4. A transition system is defined by (a) a set of states and a relation on them; (b) a set of points and a mapping among them; (c) a set of symbols and rules for sequencing them; (d) a set of strings; (e) none of these

5. The ____ is a widely-used model of computation (a) PC; (b) Macintosh; (c) operating system; (d) state‑transition system; (e) principle of mathematical induction

6. The reflexive transitive closure of d maps from (a) states to states; (b) states and symbols to states; (c) states and strings to states; (d) states and symbols to symbols; (e) none of these

7. Whether a certain string belongs to the language recognized by a finite automaton is determined by (a) the output; (b) the transition; (c) whether the automaton terminates; (d) whether the automaton terminates in an accepting state; (e) none of these

8. If a finite automaton terminates in an accepting state, then the input string (a) belongs to the FA’s language; (b) is non-null; (c) is finite; (d) contains a repetition of symbols; (e) none of these

9. For each finite automaton there exist(s) ___ corresponding language(s) (a) no; (b) one; (c) two; (d) some finite number of; (e) infinitely many

10. The language specified by (HAA^*)^* contains (a) HHA; (b) AHHAHA; (c) HAHAAHAAA; (d) AHA; (e) HHAHA

2. Regular languages and regular expressions

1. A DFA may be converted to a regular expression using (a) induction; (b) a construction; (c) contradiction; (d) compilation; (e) none of these

2. All ___ languages are regular (a) known; (b) finite; (c) infinite; (d) decidable; (e) none of these

3. The operations that form regular expressions are concatenation, iteration, and (a) selection; (b) inversion; (c) transposing; (d) negation; (e) none of these

4. What is the language of this?

(a) not regular; (b) 0*1*; (c) 1*0*; (d) (1+0)* 1*(0+1)*; (e) (1+0)1*0(0+1)*

5. The operations that form regular expressions are iteration, selection, and (a) concatenation; (b) inversion; (c) transposition; (d) negation; (e) none of these

6. The operations that form regular expressions are concatenation, selection, and (a) iteration; (b) inversion; (c) transposing; (d) negation; (e) none of these

7. A regular expression may be converted to a DFA using (a) induction; (b) a construction; (c) contradiction; (d) compilation; (e) none of these

8. A regular expression (a) is a language; (b) is an alphabet; (c) defines a language; (d) defines an alphabet; (e) none of these

9. The regular-expression meta-symbol ‘+’ stands for (a) concatenation; (b) selection; (c) iteration; (d) addition; (e) reversal

10. The regular-expression meta-symbol ‘*’ stands for (a) concatenation; (b) selection; (c) iteration; (d) addition; (e) reversal

11. The string “1100” is an element of the regular language defined by (a) 0*1*0*; (b) 0(0+1)*; (c) 1*0*1; (d) 1*010; (e) none of these

12. Which is in the language defined by digit digit^*? (a) abc; (b) 2*; (c) 325; (d) 65k; (e) 0.3

13. To group a series of symbols in a regular expression, we use (a) concatenation; (b) +; (c) *; (d) parentheses; (e) none of these

14. The set of all possible Java identifiers may be specified by (a) an inductive proof; (b) an algebraic expression; (c) a regular expression; (d) a regular language element; (e) none of these

15. The regular expressions that define infinite languages contain (a) +; (b) (); (c) |; (d) *; (e) none of these

16. A regular language corresponds to (a) an alphabet; (b) the set of all strings over an alphabet; (c) a regular expression; (d) a DFA but not an NFA; (e) none of these

17. A regular language corresponds to (a) an alphabet; (b) the set of all strings over an alphabet; (c) a DFA only; (d) a DFA or an NFA; (e) none of these

18. Structural induction is used to show properties of (a) sets of integers; (b) real numbers; (c) sets of strings; (d) algorthms; (e) none of these

19. Boolean expressions are (a) free-form; (b) numbers; (c) recursively-defined strings; (d) the same as regular expressions; (e) assertions in predicate logic

20. We may use _____ to prove that all elements of a certain language have equal numbers of left and right parentheses (a) contradiction; (b) enumeration; (c) counter example; (d) structural induction; (e) strong induction

21. Regular expressions may be construc ted by (a) concatenation, selection, and subtraction; (b) addition and iteration; (c) addition, selection, and iteration; (d) concatenation; (e) concatenation, selection, and iteration

22. A regular expression defines (a) an assertion; (b) a language; (c) a set of integers; (d) a truth value; (e) a numeric value

3. Nondeterministic finite automata

1. NFAs accept (a) not as many languages as DFAs; (b) more languages than DFAs; (c) the same languages as DFAs; (d) CFLs; (e) none of these

2. An NFA may be converted to a DFA using (a) induction; (b) a construction; (c) contradiction; (d) compilation; (e) none of these

3. NFAs may allow what kind of transition not accepted by DFAs? (a) a; (b) d; (c) l; (d) p; (e) q

4. An NFA’s transition function returns (a) a Boolean value; (b) a state; (c) a set of states; (d) an edge; (e) a number

5. The proof that the concatenation of regular languages is regular is by construction of a(n) (a) alphabet; (b) DFA; (c) language; (d) NFA; (e) program

6. DFAs recognize ____ languages compared to NFAs (a) fewer; (b) more; (c) the same; (d) no; (e) all

7. The proof that for every NFA there is a DFA that recognizes the same language is by (a) contradiction; (b) induction; (c) construction; (d) diagonalization; (e) none of these

8. The subset construction creates a DFA whose states are (a) Booleans; (b) numbers; (c) strings; (d) sets of NFA states; (e) none of these

9. The subset construction shows that every NFA accepts a (a) string; (b) function; (c) regular language; (d) context-free language; (e) decidable set

4. Proving a language is not regular

1. The Pumping Lemma (a) holds that certain languages are not regular; (b) is used in proofs that certain languages are not regular; (c) is a corollary to theorems about regular languages; (d) is a hypothesis; (e) is an open research question

2. The Pumping Lemma is used to show that a certain language is (a) regular; (b) finite; (c) infinite; (d) not regular; (e) none of these

3. We “pump out” of the possibility that a language is regular using (a) a regular expression; (b) the idea of a loop on a DFA; (c) the fact that the language is finite; (d) the idea of a branch; (e) none of these

4. To show that a language is not regular we may use (a) the Pumping Lemma; (b) diagonalization; (c) induction; (d) construction; (e) NFAs

5. The Pumping Lemma uses repetition of (a) while loops; (b) inputs; (c) substrings that return a DFA to the same state; (d) numbers; (e) none of these

6. The set of regular languages is closed under (a) concatenation but not reversal; (b) union but not concatenation; (c) concatenation but not complement; (d) union and concatenation; (e) complement but not union

7. For any DFA (a) a minimal version does not exist; (b) a minimal version exists but cannot be computed; (c) an algorithm exists to derive the minimal version; (d) a variety of designs for a minimal version exist; (e) minimality is a meaningless concept

8. DFA minimalization uses ___ states (a) unreachable; (b) duplicate; (c) distinguishable; (d) indistinguishable; (e) unique

9. For any regular language there exists (a) an optimal DFA; (b) a unique minimal DFA; (c) a unique maximal DFA; (d) no unique DFA; (e) none of these

5. L.exical analysis

1. DFAs are used to construct (a) symbol tables; (b) lexical analyzers; (c) parsers; (d) optimizers; (e) code generators

2. A lexical analyzer recognizes (a) grammar rules; (b) numbers; (c) tokens; (d) correctness; (e) type errors

3. An identifier is recognized by a (a) parser; (b) lexical analyzer; (c) minimizer; (d) subset construction; (e) pumping lemma

4. Lexical analysis is done by (a) table lookup; (b) parsing; (c) a PDA; (d) a DFA; (e) a Turing machine

2a. Construct FA

For the languages below, diagram a finite automaton that accepts strings that:
do not end with “01”

1. have exactly two '0's (accepts 0110, rejects 011001)

2. have an odd number of zeroes

3. have an odd number of bits (accepts 01100, rejects 011101)

4. have no two consecutive 0s or 1s

5. have at least two consecutive 0s

6. are binary numerals divisible by 4 (accepts 01100, rejects 01101)

7. are unary numerals divisible by 4 (accepts 1111, rejects 111)

8. have all the 0’s following all the 1’s

9. start with a ‘1’ and have an even number of bits

10. are of odd length

11. have an even number of zeros

12. have an odd number of zeros

13. have an even number of ones

14. have an odd number of ones

15. have an even number of zeros

16. have exactly one 1

17. start with 0

18. end with 1

19. have exactly one zero

20. have not more than one 1

21. are of odd length

22. have exactly one zero

23. have not more than one 1

24. start and end with 1 and have an even number of bits.

Miscellaneous

1. Defend or refute: “Nondeterministic automata are of great practical use.” Give examples

2. Explain why a finite automaton does or does not correspond to a graph.

3. What are nondeterministic finite automata used for?

4. What is the union of the following languages?
L₁ = {0, 00, 000}, L₂ = {00, 01, 10, 11 }

5. What is the intersection of the languages listed in the previous problem?

6. What is the intersection of the language whose elements begin with 0 and the language (0+1)1^*?

7. What does an edge in a DFA’s diagram represent? Explain in one sentence.

8. Draw a DFA or NFA that recognizes
(1 + 00^*) (01^*)^*

9. Convert the following NFA to a DFA.

10. (c) prove correctness of your FA by induction on the length of input. (2e)

2b. Regular expression

(1-20) Write a regular expression that generates the language accepted by the FA specified in the corresponding problem under the heading “2a.”

21. Diagram an NFA that recognizes (01)*(0 + 11)

22. Using both a tuple and a diagram, define a finite automaton that recognizes the language (01)^*.

23. Design a finite automaton that recognizes the language (0* + 1)0.

24. Using both a tuple and a diagram, define a finite automaton that recognizes the language
a. (00 + 1)^*
b. (0^* + 1)0
c. 01^*0
d. of Java relational operators
(==, >=, <=, <, >, !=)

25. Design a nondeterministic finite automaton that recognizes the language (0^* + 1)^*0.

26. Design a finite automaton that recognizes the language (01 | 100)*(0 | 1*).

27. Write a regular expression and design a corresponding NFA that accepts strings whose third-last symbol is 1

28. Show a regular expression and an NFA for the language of all strings over {0,1} that contain a 00.

29. Describe in plain English the language associated with the regular expression
(0 + 11)^*

30. Convert to a DFA and give corresponding regular expression:

31. Give the regular expression for a DFA that has two states, loops back to the starting state on a 0, and goes from there to the accepting state on a 1.

32. Using both a tuple and a diagram, define an automaton that recognizes the language (0^* + 1)0

33. Diagram an automaton that accepts the language 1^*((0^* + 1)0)^*

34. Design a finite automaton that recognizes the language (01 | 10) (0 | 1)^*

35. Construct an NFA that recognizes (0 | 1)*10*

36. (a) What is this a diagram of? (b) What language does it accept?.

2c. Pumping Lemma

1. Use the Pumping Lemma to show that the language 0ⁿ1²ⁿ (strings with a certain number of 0’s followed by twice as many 1’s) is not regular. Include a restatement of the Pumping Lemma.

2. Show by the Pumping Lemma that 0ⁿ10ⁿ is not regular.

3. Use the Pumping Lemma to show that the language consisting of strings that are palindromes is not regular.

4. Use the Pumping Lemma to show that the language x01x^R is not regular, where x^Ris x spelled backwards.

5. What proof method is used when Pumping Lemma is used?

6. What is an application of DFAs in program compilation?

2d. Proof of expressiveness

Show that

1. Finite languages are regular

2. NFAs accept at least all the regular languages

3. The union of two regular languages is regular

4. The intersection of two regular languages is regular

5. The reverse of a regular language is regular

6. The concatenation of two regular languages is regular

7. If L is regular, then L* is regular

8. Let A be a DFA and q a particular state of A, s.t. d(q, a) = q for all inputs a. Prove by induction on the length of the input that for all input strings w, d^*(q,w) = q. (Hopcroft et al., p. 54)

1. Pushdown automata

1. Pushdown automata (a) accept the decidable languages; (b) accept the context-free languages; (c) have finite storage; (d) are less expressive than DFAs; (e) none of these

2. The context-free languages are recognized by (a) their alphabets; (b) finite automata; (c) pushdown automata; (d) a Turing machines; (e) random-access machines

3. A pushdown automaton may have (a) more states than a finite automaton; (b) random-access memory; (c) an infinite alphabet; (d) a stack; (e) faster transitions

4. A pushdown automaton has (a) a finite number of configurations; (b) fewer configurations than a DFA; (c) an infinite number of configurations; (d) a queue; (e) a tape

5. In PDAs, d is (a) a state; (b) a set of states; (c) a relation; (d) a function; (e) a stack alphabet

6. In PDAs, S is (a) a state; (b) a set of states; (c) a relation; (d) a function; (e) an alphabet

7. In PDAs, Q is (a) a state; (b) a set of states; (c) a relation; (d) a function; (e) a stack alphabet

8. In PDAs, G is (a) a state; (b) a set of states; (c) a relation; (d) a function; (e) a stack alphabet

9. In PDAs, q₀ is (a) a state; (b) a set of states; (c) a relation; (d) a function; (e) a stack alphabet

10. DFAs are ____ PDAs (a) as expressive as; (b) less expressive than; (c) more expressive than; (d) more complex than; (e) less complex than

11. What does a PDA have that a DFA does not? (a) states; (b) input alphabet; (c) tape; (d) stack alphabet; (e) all of these

12. The standard proof that all RLs are CF is by (a) induction; (b) construction; (c) contradiction; (d) diagonalization; (e) introspection

13. All regular languages are (a) finite; (b) context free; (c) infinite; (d) all of these; (e) none of these

14. The greater expressive power of PDAs compared to DFAs is due to (a) the set of states; (b) recursive productions; (c) the stack; (d) nondeterminism; (e) none of these

2. Context free languages and
context-free grammars

1. Context-free languages are (a) a subset of regular languages; (b) a superset of regular languages; (c) a superset of decidable languages; (d) accepted by DFAs; (e) none of these

2. A CF grammar generates a language (a) requiring a Turing machine to accept it; (b) accepted by a DFA; (c) accepted by a PDA; (d) that is uncountable; (e) none of these

3. The set of all nested sequences of balanced parentheses is (a) a string; (b) a regular expression; (c) a regular language; (d) a context-free language; (e) a finite language

4. A context-free language is characterized by a set of ______ rules (a) regular; (b) regular and irregular; (c) production; (d) alphabets as; (e) terminal and nonterminal

5. An element of a context-free grammar that requires definition in terms of other elements is (a) a leaf; (b) a terminal; (c) a regular expression; (d) a nonterminal; (e) a production

6. Recursiveness is often found in (a) productions in a context-free grammar; (b) regular expressions; (c) pushdown automata; (d) DFAs; (e) none of these

7. PDAs ___ CFGs (a) can be constructed from; (b) are the same thing as; (c) have little relationship with; (d) generate; (e) accept

8. PDAs ___ CFLs (a) can be constructed from; (b) are the same thing as; (c) have little relationship with; (d) generate; (e) accept

3. Derivations and parsing

1. Derivations apply (a) regular expressions; (b) CFG production rules; (c) proof rules; (d) definitions of DFAs; (e) none of these

2. The standard proof that all CFGs generate CFLs is by (a) induction; (b) construction; (c) contradiction; (d) diagonalization; (e) introspection

3. The standard proof that any CFL can generated by some CFG is by (a) induction; (b) construction; (c) contradiction; (d) diagonalization; (e) introspection

4. The start symbol in a CFG (a) is a terminal; (b) is on the left side of a production rule; (c) is on the right side of a production rule; (d) is a production rule; (e) none of these

5. A parse tree is yielded by (a) a grammar; (b) an input string; (c) a PDA; (d) a CF grammar and an input string; (e) a derivation

6. A derivation begins with (a) a parse tree; (b) a string; (c) a terminal symbol; (d) a nonterminal; (e) a PDA

7. A derivation yields (a) a parse tree; (b) a nonterminal symbol; (c) a production rule; (d) a terminal; (e) a PDA

4. Properties of PDAs, CFLs, and CFGs

1. A proof that a language is not context free is often by (a) induction; (b) construction; (c) refutation; (d) diagonalization; (e) the Pumping Lemma for CFLs

2. If S is an alphabet and S is a start symbol, then { w Î S^* | S Þ^*_G w } is (a) a derivation; (b) a PDA; (c) the language generated by a CF grammar; (d) the language generated by a regular expression; (e) a derivation step

3. The set of languages defined by CF grammars is (a) the set of regular languages; (b) finite; (c) the set of PDA-recognized languages; (d) the set of decidable languages; (e) null

4. A ___ may be constructed from any PDA (a) DFA; (b) NFA; (c) CFG; (d) regular expression; (e) none of these

Longer answer

3a. Derivation

For #1-11:

(a) Write a derivation, citing rule at each step, to show that the grammar specified in set braces generates the string indicated.

(b) Show parse tree.

1. {S ® Xa | aX | SX, X ® ab | ba | l | XX}, ‘abaab’

2. {S ® XY | l, X ® 0Y | S1, Y ® 1}, ‘00111’

3. {S ® 00X , Y ® 1X1, Y ® l, X ® Y0}, ‘001101010’

4. {S ® SS | 0S1 | 1S0 | l}, ‘001011’

5. {S ® S2, S ® X, X ® 0X1, X ® l}, ‘00112’

6. {S ® 0S | X, X ® 1X 2 | l}, ‘01122’

7. {S ® X1, S ® 001, X ® 0, X ® X 0 }, ‘00001’

8. {S ® 0S1S, S ® 1S0S, S ® l}, ‘011001’

9. {S ® X, X® 0X | l | Y, Y ® X1}, ‘0001’

10. {S ® 0S, S ® X, X ® 0, X® 11}, ‘00011’

11. {S ® 0X1, X ® 0X1, X ® l}, ‘000111’

12. Given the following grammar:
S ® 1X | 1S
X® 0 | 0X
(a) What type of grammar is this?
(b) What does it define?
(c) What are the components of the grammar called?
(e) Write a derivation and parse tree to show that 1100 is in the set defined by the grammar.

13. Write a derivation and parse tree for
S ® Xa | aX | SX
X ® aY | Ya
Y ® ab | ba | l | YY
and each of the following strings:
(a) abbb; (b) aaba; (c) abab; (d) baab; (e) baaab

14. (a) In plain terms, state what language is generated by the CFG
S ® 0 X 0 | 1 X 1
X ® 0 | XX
(b) Perform a derivation using a 7- or 8-character string that you know is in the language and that is formed using all the productions.

15. Write a derivation and parse tree for the string 10001, citing rules, given the following:
S ® 0X0 | 1X1
X ® 0 | 1 | l

16. Given the following:
S ® 1X | 1S
X® 0 | 0X
(a) What is the above 2-line entity called?
(b) What do these entities define in general?
(c)What are the components of the above entity called and how many are there?
(d) What particular set of (b) does the entity define, precisely?
(e) Write a derivation tree to show that 1100 is in the set defined by the entity.

17. Show that ( ( )( ) ) is in the language defined by the grammar
S ® ( S ) | SS | l
referring at each step to rule 1, 2, 3, or 4.

18. Write a derivation (giving rule numbers) showing that the following grammar generates the string ‘0122’
1. S ® S2
2. S ® X
3. X ® 0X1
4. X ® l

3b. CFG

1. Write a context-free grammar to specify the language consisting of all bit strings that have twice as many 0’s as 1’s.

2. Define a CF grammar for (1^* | (01)^*)

3. Write a grammar to specify the language {0^m1ⁿ | n > m}. Explain.

4. Define a CF grammar for x0x^R, x Î {0,1}^*

5. Define a CF grammar for the following,and explain your design briefly:
(a) { x | n₀(x) = n₁(x) } (equal 0’s and 1’s)
(b) All palindromes
(c) Balanced parentheses
(not only ((())) but also ()(()()) etc)
(d) 0ⁿ1²ⁿ
(e) {xx | x Î å}

6. RPN challenges :
a. Write a CF grammar for the set of all Reverse Polish Notation expressions.
b. Define a PDA that accepts RPN expressions.
c. Is RPN a regular language? If so, write a regular expression for it; otherwise show that it is not regular.
d. Design a finite or pushdown transducer (PDT) that evaluates RPN expressions (OK for output to be in unary notation). A PDT is a PDA that also outputs a string at each transition:
d : Q ´ S_in ´ G È {l} ® Q ´ G È {l} ´ S_out.

3c. PDA model

1. What operations can a PDA perform that a DFA cannot?

2. Explain the relationship between context-free languages and pushdown automata.

3. List differences and similarities between the DFA and the PDA models of computation. Give an example of how a stack is needed to recognize a non-regular language such as 0ⁿ1ⁿ.

4. (a) What are the six lines below, taken together?
S ® X 0
S ® 1Y
X ® 1
Y ® 0
X ® 1XY
Y ® XY0
(b) What model of computation corresponds to this? Write a diagram of a machine that recognizes the language generated
(c) Describe the language in plain terms.
(d) Choose a six-bit string that is in the language and write a derivation for it.
(e) Is the language regular? If not show by pumping lemma, otherwise show regular expression.

3d. Proof of expressiveness

1. Explain why all finite languages are context free. What kind of proof supports this claim?

2. Restate in plain English: (" L Í S^*) Regular(L) Þ Context-Free(L). Describe a constructive proof for this claim and relate to automata models.

3. Prove by construction of a CFG that if L₁, L₂ Î CFL, then (L₁ È L₂) is CF. Discuss.

1. TMs

1. The Turing machine model is said to capture (a) regular languages; (b) interaction; (c) efficient computation; (d) algorithmic computation; (e) all of these

2. A TM is distinguished from DFAs and PDAs by (a) a set of states; (b) a stack; (c) RAM; (d) a tape; (e) a simpler transition function

3. A TM has ____ memory (a) random-access; (b) limited; (c) unbounded; (d) stack; (e) queue

4. A TM (a) lacks an alphabet; (b) has tape instead of states; (c) can compute any mathematical function; (d) stores data on a tape; (e) none of these

5. A Turing machines’ special feature that distinguishes it from finite automata and pushdown automata is (a) a set of states; (b) a stack; (c) RAM; (d) a tape; (e) a simpler transition function

6. A Turing machine (a) has no alphabet; (b) replaces states with a tape; (c) uses tape as storage; (d) has finite memory; (e) can compute any mathematical function

7. An state-transition system with tape is a (a) finite transducer; (b) DFA; (c) NFA; (d) PDA; (e) Turing machine

2. TM computations

1. Each computation step on a TM may (a) read many symbols; (b) make several transitions; (c) move the tape head left or right; (d) push the stack; (e) none of these

2. When does a TM halt? (a) at end of input; (b) when it enters an accept or reject state; (c) in finite time; (d) never; (e) none of these

3. A TM configuration is determined by (a) most recent input; (b) most recent state; (c) tape contents; (d) state and tape symbol under head; (e) state, tape-head location, and tape contents

4. A TM computation is a sequence of (a) tape symbols; (b) states; (c) configurations; (d) transition function values; (e) none of these

5. A TM that halts on all inputs (a) does not exist; (b) computes a partial function; (c) computes a total function; (d) terminates early; (e) none of these

6. A nonstandard variant of the TM has ___ tape(s) (a) no; (b) one; (c) two; (d) an infinite number of; (e) none of these

7. A ____ TM simulates any TM (a) universal; (b) halting; (c) PDA; (d) one-tape; (e) none of these

8. The universal TM corresponds to (a) a PDA; (b) a stored-program computer; (c) a general-purpose DFA; (d) all TMs; (e) none of these

3. Turing decidability

1. Any computable function can be computed on some (a) DFA; (b) NFA; (c) PDA; (d) Turing machine; (e) none of these

2. Decision problems are equivalent to functions that return (a) natural numbers; (b) strings; (c) truth values; (d) Turing machines; (e) none of these

3. Every regular language is (a) finite; (b) uncountable; (c) TM-decidable; (d) undecidable; (e) none of these

4. Every context-free language is (a) finite; (b) uncountable; (c) TM-decidable; (d) undecidable; (e) none of these

5. Any decidable problem is solved by a (a) DFA; (b) NFA; (c) PDA; (d) Turing machine; (e) none of these

6. Algorithmic computation in general is modeled by (a) DFAs; (b) NFAs; (c) PDAs; (d) Turing machines; (e) HTML

7. TMs can solve the problem of (a) accepting a regular language; (b) describing the output of a given Turing machine; (c) telling whether a TM halts; (d) telling whether a Java program is correct; (e) none of these

4. Undecidability

1. The Halting Problem involves (a) testing a TM to see if it halts; (b) determining from the structure of the TM whether it halts; (c) determining how to change the transition function of a TM to cause it to halt; (d) determing what inputs halt a TM; (e) none of these

2. The standard proof that the Halting Problem is undecidable is by (a) induction; (b) indirection; (c) contradiction; (d) indirection; (e) none of these

3. Turing reducibility means (a) two models of computation are equivalent; (b) one model of computation is more expressive; (c) problem B is undecidable if problem A is undecidable and reducible to B; (d) problem B is undecidable if problem A is undecidable and B is reducible to A; (e) none of these

4. The Halting Problem (a) is decidable; (b) provides an example of a language that no TM accepts; (c) is exponential-time; (d) is a machine; (e) none of these

5. Which is decidable? (a) DFA A accepts the language generated by regular expression E; (b) TM M halts on blank input; (c) TM M accepts the language generated by regular expression E; (d) TM M says “arf” on input “meow”; (e) all of these

Longer answer

4a. Describe TM

1. How does a TM differ from a PDA in its input, output, and memory?

2. What are the parameters and return value of the TM’s transition function?

3. In what sense is a TM a decider, and in what sense is it a transducer?

4. Translate to plain English and explain:
d: Q ´ (S È G) ® Q ´ (S È G È {L, R})

5. Distinguish f_M from d of a TM.

6. Translate to plain English and explain:
d: Q ´ (S È G) ® Q ´ (S È G È {L, R})

7. Distinguish f_M from d of a TM.

4a, 4b. TM Construction

Write (as a diagram or table) the definition of the following Turing machine corresponding to your group number. Multitape TMs are OK. Document by describing the purpose of each loop. If you use JFLAP, include as test results JFLAP traces of a few test inputs. Note that unary here refers to a system of numerals where 1 = 1, 2 = 11, 3 = 111, etc. Note that #9-12 need not write to tape, only accept or reject.

1. add a binary numeral to a unary numeral (tally, i.e., 11=2, 111=3, etc.), yielding binary output. Use '+' to separate the two parts of the input. For input 11+100 (3+4), output should be 111 (7).

2. binary doubler (y = 2x)

3. binary inverter

4. unary to binary converter

5. unary to unary adder (e.g., on input of “11 111” should output “11111”)

6. unary to unary subtracter

7. unary equality comparison (on input x₁, x₂, if x₁ = x₂ output 1, else 0)

8. unary greater-than (on input x₁, x₂, if x₁ > x₂ output 1, else 0)

9. logical OR for a two-bit input (outputs 1 on 01, 10, or 11; 0 on 00)

10. logical AND for two 1-bit inputs

11. logical OR for multiple-bit input

12. logical AND for multiple-bit input

13. count 0's in input, display as unary numeral

14. compress bit string to eliminate 0's

15. string equality comparison (on input x₁, x₂, if x₁ = x₂ output 1, else 0)

16. binary greater-than (on input x₁, x₂, if x₁ > x₂ output 1, else 0)

17. equality comparison (on input x₁, x₂, accept iff x₁ = x₂)

18. search (find location of first 1 in a bit string, output its location in unary)

19. bitwise logical OR for multiple-bit input

20. bitwise logical AND for multiple-bit input

21. logical OR for 2-bit input (accepts on 01, 10, or 11; 0 on 00)

22. logical AND for two-bit input

23. unary incrementer

24. unary decrementer

25. output is zero on any input

26. x₁ for (x₁, ..., x_n)

27. x₂ for (x₁, ..., x_n)

28. Explain why any language recognized by a DFA must also be recognized by some TM.

29. Explain how we know all CFLs are decidable.

30. Explain how we know all regular languages are decidable.

31. Show that Turing machines accept a strict superset of the CFLs.

32. Compare the expressiveness of Turing machines and {DFAs, NFAs, PDAs, regular expressions, CF grammars}. Justify your answer rigorously.

33. Refute the following: “Turing machines have no more computational power than finite lookup tables in which inputs and outputs are listed, and in which to find f (x) one just looks up the table entry with x in the left column. A TM may actually be represented as a lookup table: origin state, symbol fetched, destination state, symbol to write, left or right move.

4c. Undecidability

1. Discuss how Rice’s theorem is valid with respect to a model of algorithmic computation. Why is it valid under both models?

2. Prove, by referring to a well-known theorem, that
{P | P is the code of a program whose first
output is “meow” on input “arf” }
is undecidable.

3. Compare and contrast the diagonal proofs by Cantor (cardinality of reals is greater than that of natural numbers) and Turing (some problems are uncomputable). What basic proof method do they share?

4. Briefly explain why no TM can solve the halting problem.

5. Briefly explain why no TM can solve the problem of whether a given TM halts on blank input.

6. Briefly explain why no TM can solve the problem of whether a given TM halts on all inputs.

4d. Reducibility

1. Suppose that if you had a solution to problem P, you could use it to easily construct a solution to problem Q. Also suppose that you know that problem Q is undecidable.
(a) What can you say about problem P?
(b) What is the relationship between P and Q called?
(c) Relate the above to the limits of algorithmic computing.

2. Suppose it were proven that problem P₁ is undecidable. How might this fact be used to show that problem P₂ is undecidable?

3. What is the term for the relationship of problem A to problem B, when we can show that a solution to problem B would provide us with a way to solve problem A?

4. Explain the notion of reducibility of problems. For what proofs is it used in this course?

5. What is the term for the relationship of problem A to the halting problem, when we can show that a solution to problem A would provide us with a way to solve HALT? What can we say about A?

1. Random-access machines
and the S language

1. TM-computable functions are the same as those computable on a (a) DFA; (b) PDA; (c) random-access machine; (d) control device; (e) none of these

2. The S language implements which model? (a) DFA; (b) PDA; (c) RAM; (d) TM; (e) none of these

3. Unlike TMs, random-access machines have (a) tape; (b) stack; (c) queue; (d) addressable storage; (e) hard disk

4. The S language operates on (a) natural numbers; (b) real numbers; (c) symbols; (d) strings; (e) none of these

5. In the S language, input (a) occurs many times during a computation; (b) is the values of X variables at the start of computation; (c) is of string form; (d) may follow output; (e) none of these

6. The RAM model enables use of strings as input via (a) a Java method; (b) a data type; (c) Gödelization; (d) binary encoding; (e) encryption

7. A universal program in the S language (a) compiles to byte code; (b) is an interpreter as seen on a browser; (c) accepts encodings of other S language programs as inputs; (d) is a Turing machine; (e) solves even undecidable problems

2. m-recursive functions

1. TM-computable functions are the same as (a) those computable on a DFA; (b) those computable on a PDA; (c) m-recursive functions; (d) control devices; (e) none of these

2. Recursively definable functions are equivalent to ___ as a model of computation (a) DFAs; (b) PDAs; (c) TMs; (d) all of these; (e) none of these

3. The ___ function is not a basic primitive recursive function (a) factorial; (b) zero; (c) successor; (d) projection; (e) predecessor

4. One computable operation on primitive recursive functions is (a) inverse; (b) search; (c) composition; (d) integration; (e) none of these

5. Obtaining a function by primitive recursion is a way to show that the function is (a) continuous; (b) a predicate; (c) computable; (d) uncomputable; (e) none of these

6. The result of minimalization of a primitive recursive function is (a) primitive recursive; (b) computable; (c) minimal; (d) undecidable; (e) none of these

3. Semidecidability

1. A recursively enumerable set is (a) a recursive function; (b) DFA recognizable; (c) TM recognizable, but no TM necessarily halts to reject non-members of the r.e. set; (d) accepted by a PDA; (e) none of these

2. A semi-decidable language is (a) regular; (b) context-free; (c) recursive; (d) recursively enumerable; (e) none of these

3. Some undecidable languages are (a) regular; (b) context-free; (c) recursive; (d) recursively enumerable; (e) none of these

4. Not all non-elements of a semi-decidable language are ___ by a recognizer TM (a) accepted; (b) rejected; (c) generated; (d) output; (e) none of these

5. If both a language and its complement are recursively enumerable, then the language is (a) regular; (b) decidable; (c) context-free; (d) empty; (e) universal

6. Unrestricted grammars generate languages accepted by (a) Turing machines; (b) linear bounded automata; (c) DFAs; (d) PDAs; (e) random access machines

4. Church-Turing Thesis

1. The Church-Turing thesis associates the TM with (a) regular languages; (b) parsing; (c) lexical analysis; (d) algorithms; (e) interaction

2. The Church-Turing Thesis refers to (a) a formalization of an intuitive notion; (b) a theorem; (c) provable; (d) disprovable; (e) a paper written at Harvard

3. According to the Chomsky hierarchy (a) RL Ì CFL; (b) CFL Ì RL; (c) HALT is decidable; (d) DFAs accept all recursive sets; (e) PDAs can decide the Halting Problem

4. TMs (a) are interactive; (b) always halt; (c) perform input alternating with output; (d) mimic Internet servers; (e) mimic command-line environments

5. According to the Chomsky hierarchy, (a) all recursive sets are context free; (b) CFL Ì RL; (c) HALT is decidable; (d) DFAs accept all recursive sets; (e) regular languages are decidable

6. According to the Chomsky hierarchy (a) CFL Ì RL ; (b) CFLs are decidable; (c) HALT is decidable; (d) DFAs accept all recursive sets; (e) PDAs can decide the Halting Problem

7. The observation that Turing machines and S language programs compute the same functions corresponds most strongly to (a) Cantor’s proof; (b) Gödel’s theorem; (c) the Church-Turing thesis; (d) Rice’s theorem; (e) none of these

8. The proof that any S language program computes a Turing-computable function is (a) diagonal; (b) by construction; (c) by contradiction; (d) inductive; (e) none of these

9. The proof that any Turing machine computes an S language computable function is (a) diagonal; (b) by construction; (c) by contradiction; (d) inductive; (e) none of these

Short and longer answer

5a. Recursive definability and computability*

1. Explain the relationship between primitive recursion and algorithmic computability.

2. With what models of computation is recursive function theory equivalent, and how is this proven?

3. What does computability have to do with primitive recursion plus minimization?

4. What do recursion and computability have to do with each other?

5. Explain what m-recursion has to do with Turing machines.

6. Explain the notion of composition in recursive function theory.

5b. Random access machine model

7. Describe the RAM model of computation.

8. How is the S language similar to two languages, very different from each other, that you have studied in computer science?

9. What statement in the S language enables looping and how?

10. Describe the S language and name the model of computation associated with it.

11. Distinguish primitive recursion from m-recursion.

12. Distinguish primitive recursion from composition.

13. Write a program in the S language that does the following. You may use macros for variable assignment, addition, unconditional jump, jump on zero, addition, and subtraction. Use comments to clarify intention.

a) Input x and output (x + 1)

b) Input x and output (x – 1)

c) Input x₁ .. x_nand output x₂

d) Input x and output 1 if x = 0, otherwise 0.

e) Input x and output 1 if x> 0, otherwise 0.

f) Input (x₁, x₂) and output 1 if x₁³ x₂, otherwise output 0.

g) Input (x₁, x₂) and output (x₁-^× x₂) (monus).

h) Input (x₁, x₂), output 2x₁ + x₂

i) Input (x₁, x₂), output 3x₁-^× x₂

j) Input (x₁, x₂), output 1 if 2x₁ < x₂, otherwise 0

k) Input (x₁, x₂) and output (x₁ x₂) (multiplication).

l) Input (x₁, x₂) and output (x₁ ¸ x₂) (division).

m) Input (x₁, x₂) and output (x₁ mod x₂).

n) Input x, output 2x

14. Distinguish the RAM model of computation from the transition system model, with examples and implementations.

15. Describe operations on a RAM and give its expressiveness.

16. Compare the RAM model of computation with the TM model, describing operations on a RAM.

17. Distinguish decidability from semidecidability.

18. What are the recursively enumerable sets?

19. Describe TMs, RAMs programmed in the S language, and primitive recursion. State their most important common feature or property from the point of view of this course. (5a, 5b)

5c. Expressiveness of the RAM model

20. Show by construction, with respect to the RAM model of computation, that if f and g are computable functions, and ("x) (h(x) = g (f (x))), then h is computable.

21. Use the computability of addition to show that multiplication is S –computable.

22. Use the computability of decrementing to show that subtraction is S –computable.

23. Use the computability of multiplication to show that finding the smallest x such that x³ is odd is
S –computable.

24. Show that
{P Î S | P has an infinite loop on some inputs}
cannot be implemented in S . (4c, 5c)

5d. Chomsky hierarchy*

25. Describe the relationship between recursive (decidable) sets, the set of context-free languages, and the set of regular languages, referring to automata models as well.

26. How do the RAM and TM models compare to two other non-equivalent models studied earlier in the course?

27. What TMs solve semidecidable problems but not decidable ones?

28. Describe the Chomsky hierarchy.

29. Describe a well-known hierarchy of models of computation discussed in this course.

30. How would a Turing machine compute m f (x) for a function f ?

31. Show how the logarithm function may be obtained from subtraction and division by primitive recursion.

5e. Semidecidability

1. Distinguish decidability from semidecidability

2. Describe the languages L for which there exist Turing machines that halt to accept strings in L, but for some strings not in L, these Turing machines loop forever.

3. What are the recursively enumerable languages? Describe the relation between them and Turing machines or RAMs.

1. Algorithms vs interaction

1. Algorithms (a) compute functions; (b) provide services; (c) accomplish missions in multi-agent systems; (d) may execute indefinitely; (e) none of these

2. A feature of algorithmic computation is (a) alternation of input and output; (b) processing before input; (c) output before processing; (d) input, then processing, then output; (e) none of these

3. A feature of interactive computation is (a) alternation of input and output; (b) processing before input; (c) output before processing; (d) input, then processing, then output; (e) none of these

4. A feature of algorithmic computation is finite (a) input; (b) output; (c) processing; (d) input, output, and processing; (e) none of these

2. Sequential interaction

1. Sequential interaction is associated with (a) providing a service; (b) non-termination; (c) dynamic input during computation; (d) persistence of state; (e) all of these

2. Finite transducers extend (a) DFAs; (b) PDAs; (c) TMs; (d) RAMs; (e) none of these

3. A Mealy machine has a (a) regular language; (b) stream language; (c) finite language; (d) context-free language; (e) decidable language

4. Interactive observable behavior is associated with (a) natural numbers; (b) strings; (c) sets of strings; (d) sets of streams; (e) none of these

5. Finite transducers (a) compute the same functions as DFAs; (b) compute the same functions as TMs; (c) have stream I/O behavior; (d) have finite input and output; (e) none of these

6. Reactive systems (a) compute functions; (b) provide services; (c) accomplish multi-agent missions; (d) execute only finitely; (e) none of these

7. I/O in reactive systems is (a) static; (b) dynamic; (c) finite; (d) constrained; (e) none of these

8. Interaction is distinguished from algorithmic computation by the presence of (a) finite input; (b) persistent state; (c) input; (d) processing; (e) none of these

9. A mutual causal effect between two agents occurs in all (a) interaction; (b) algorithms; (c) communication; (d) computing; (e) none of these

10. Synchrony entails (a) communication; (b) taking turns; (c) input; (d) autonomy; (e) none of these

11. Stream I/O characterizes (a) interaction; (b) algorithms; (c) functions; (d) O(1) processes; (e) none of these

12. Persistent state stores (a) parameters; (b) loop invariants; (c) memory of past interactions; (d) algorithmic computation; (e) none of these

13. The form of input/output in interactive computation is (a) static; (b) finite; (c) streams; (d) strings; (e) none of these

14. A service is characteristic of (a) an algorithm; (b) an interactive process; (c) a multi-agent system; (d) a parallel system; (e) none of these

15. UML is required to specify (a) functional problems; (b) services; (c) algorithms; (d) algorithmic inputs; (e) none of these

16. Mutual causality characterizes (a) algorithms; (b) only directly-interacting entities; (c) all interactions; (d) functions; (e) none of these

3. Persistent Turing machines

1. Persistent Turing machines are said to model (a) sequential interaction; (b) multi-stream interaction; (c) parallel computation; (d) distributed computing; (e) none of these

2. The persistent Turing machine is a model of (a) table lookup; (b) algorithmic computing; (c) sequential interaction; (d) multi-stream interaction; (e) adaptation

3. It is claimed in the course material that the persistent Turing machine is ____ the Turing machine (a) less expressive than; (b) as expressive as; (c) more expressive than; (d) more efficient than; (e) less efficient than

4. It is claimed in the course material that the persistent Turing machine is ____ the random-access machine (a) less expressive than; (b) as expressive as; (c) more expressive than; (d) more efficient than; (e) less efficient than

5. The persistent Turing machine augments the Turing machine with (a) algorithmic computational power; (b) storage that lasts between I/O steps; (c) more states; (d) more operations; (e) none of these

6a. Distinguish algorithmic from interactive computation

1. Is interaction more powerful than algorithms? Give reasons why and why not.

2. Give three distinctions between algorithmic and interactive computation

3. What is the term for computation in which more than one computing entity executes at the same time? In which exactly two entities participate? Define more precisely.

6b. Compare and contrast models of algorithmic and interactive computation

1. What is persistent state of a PTM and how does it contribute to the PTM’s expressiveness?

2. Describe the case presented in class that the Persistent Turing machine is a more expressive model of computation than the Turing machine.

3. Describe a model of interactive computation (better, two such models).

4. What is a transducer, and what sort of behavior is associated with one?

5. Distinguish the Persistent Turing Machine from the Turing Machine and from finite transducers.

6. Distinguish the Persistent Turing Machine from Turing’s model and describe the expressiveness claim made for the PTM.

7. Draw a transducer that always outputs a 1 on input 0, and a 0 on input 1.

8. Distinguish the set of configurations of a TM from the set of persistent states of a PTM.

9. Give the cardinality of the following, and explain:

a. The largest language accepted by a Turing machine

b. The simplest PTM stream language, in which the response to every input is “0”

c. The set of PTMs

d. The set of TMs

e. The set of finite transducers

f. The maximum set of bit streams output by a transducer

10. What is meant by “stream I/O”?

11. What kind of computation has stream I/O? Describe.

12. Define a PTM that does the following and state why it is not simulated by any TM.

a. An adder

b. A command-line processor that performs file copy operations

c. An answering machine (see slide)

d. A microwave oven

e. A digital clock

f. A vending machine that accepts $1 and $2 amounts and outputs candy and drinks, respectively

g. A soda machine (see slide) that accepts a dollar bill even when quarters have been inserted.

h. A soda machine that allows pressing a “Coin Return” button

i. A soda machine that accepts dollars, quarters, , and dimes

j. A soda machine that charges $1.25

k. An odometer

1. Models of parallel and distributed computing

1. Serial computing is the same as (a) concurrency; (b) parallelism; (c) distributed computing; (d) single‑core; (e) none of these

2. The Von Neumann architecture is associated with (a) algorithms; (b) interaction; (c) parallelism; (d) serial computing; (e) multi-core computing

3. Parallel computing is a kind of (a) concurrency; (b) Von Neumann architecture; (c) serial paradigm; (d) single-core computing; (e) none of these

4. A thread simulates (a) ownership of all resources; (b) ownership of a CPU; (c) ownership of data; (d) an array; (e) none of these

5. PRAM is (a) a model of serial computing; (b) a kind of memory; (c) a model of parallel computing; (d) a greedy algorithm; (e) none of these

6. Process algebras assume communication by (a) packet; (b) indirect interaction; (c) bus; (d) message passing; (e) none of these

7. PRAM assumes that memory is (a) all distributed; (b) shared; (c) infinite; (d) magnetic; (e) none of these

8. Concurrent write is as opposed to ___ write (a) serial; (b) automatic; (c) shared; (d) exclusive; (e) none of these

9. The standard model for parallel computing is (a) CRCW; (b) RAM; (c) PRAM; (d) Von Neumann; (e) none of these

10. SIMD assumes that all CPUs execute ___ instructions (a) the same; (b) different; (c) pipelined; (d) cached; (e) none of these

11. SIMD assumes that CPUS operate on ___ data (a) the same; (b) different; (c) pipelined; (d) cached; (e) none of these

12. A distributed algorithm runs on (a) a single processor; (b) a parallel-processing system; (c) multiple independent processors; (d) web pages; (e) none of these

2. Multi-stream and indirect interaction

1. Interaction may be sequential or (a) algorithmic; (b) O(n); (c) multi-stream; (d) data-driven; (e) none of these

2. A mission is characteristic of (a) an algorithm; (b) an interactive process; (c) a multi-agent system; (d) a parallel system; (e) none of these

3. Indirect interaction requires (a) mutual causality between entities that do not interact directly; (b) message passing; (c) synchrony; (d) static I/O; (e) none of these

4. Stigmergy is (a) algorithmic computing; (b) direct interaction; (c) indirect interaction; (d) multi-stream interaction; (e) none of these

3. Other models of computation

1. Connectionism is (a) silicon inspired; (b) parallel distributed processing; (c) symbolic; (d) inference based; (e) abductive

2. Connectionist models of computation are based on (a) the bit; (b) the neuron; (c) transition systems; (d) pseudocode; (e) the Ethernet protocol

Short and longer answer

7a. Describe forms of concurrency*

1. Name and describe two forms of concurrent computation with more than two participants.

2. What kind of computation encompasses all the following? Describe each.

a. Parallel computing

b. Distributed computing

c. Multi-agent systems

d. Connectionist systems

e. Self-organization

3. Distinguish parallel computing from multi-stream interaction.

7b. Describe some models of parallel computation

1. Distinguish parallel from distributed computing.

2. Describe the PRAM model, including its assumptions about memory access. Contrast to another model of concurrency.

3. Describe Flynn’s taxonomy.

4. Name and describe the standard model of computation for multiple processors that share access to memory, and what are some of its attributes and variants.

5. What memory-access issues arise in parallel computing?

7c. Describe connectionist and multi-agent models

1. What is a cellular automaton? What does it have in common with the brain?

2. Describe the inputs, outputs, and connectivity of a neuron. How does a neural net learn?

3. Indirect interaction is characteristic of which sort of computing?

4. Describe a model of multi-stream interaction.

5. What is the connectionist model of computation and on what phenomenon in nature is similar?

6. What is self organization and where does it occur?

7. What is emergent behavior and where does it occur?

8. What sort of interaction occurs in multi-stream interaction that does not occur in sequential interaction? Why?

9. Describe a special behavior that occurs in connectionist computing and multi-agent systems that does not occur in sequential interaction or algorithmic computing.

10. Define the following and relate to parallel or distributed computing:

a. Java threads

b. CRCW

c. SIMD

d. Cellular automata

e. Neural networks

f. Sensor networks

g. Mesh architecture

h. PRAM

i. Cache coherency

11. For the terms below, (a) give a definition; (b) give examples of models; (c) distinguish from the other terms in the list; (d) describe the role of synchrony/asynchrony if it applies

a. concurrency

b. parallelism

c. distributed processing

d. sequential interaction

e. multi-stream interaction

f. algorithm execution

g. coordination

1. How has computing been defined in this course? How do you define it?

2. What was shown in the course by
(a) constructive proof?
(b) proof by contradiction?
(c) diagonal proof?

3. Very briefly describe proof methods to show
(a) expressiveness of models
(b) the halting problem to be undecidable
(c) non-regular character of language L
(d) closure properties of languages (2c, 2d, 4b, 4c)

4. Describe two applications of the diagonal proof method.

5. What is the connection among languages, models of computation, and decision problems? Give examples.

6. What are three forms of computation discussed in this course?

7. What sorts of theorems in this course are proven by construction? Give an example, with the proof sketch.

8. What sorts of theorems in this course are proven by contradiction? Give an example, with the proof sketch.

9. Discuss the expressiveness of different models of computing.

10. Describe a hierarchy of increasingly expressive models of computation. How are the containment relationships proven?

11. How are Cantor’s, Gödel’s, and Turing’s proofs similar? Begin by stating very briefly the theorems supported by these proofs. Refer to proof methods. Option: briefly state the proof. (1b, 4c)

12. What were some of the different meanings of d in this course?

13. In the language theory we used, as applied to different automata models, distinguish Æ, l, and b/ (a.k.a. ‘#’).

14. Classify the following sets and name the corresponding automata discussed in this course

(a) {0^m1ⁿ | m ¹ n}

(b) { P | P is the code for an S -language program that has an infinite loop }

(d) {xx | x Î S^*}

(e) balanced parentheses

(f) descriptions of Turing machines that halt

(g) the set generated by a regular expression

(h) bit strings that represent prime numbers

Option: show that one or more are in the language classification you have given. (2c, 2d, 4b, 4c)

15. Describe the model of computation that would correspond best to the work you did in your research project. If your research project was itself about a model of computation, say so and relate it to at least one other model.

16. Describe three increasingly powerful forms of computation discussed in different topics of this course.

17. What are the common elements among the transition-system-based models that we discussed?

18. Suppose you wished to show that there is no one-to-one correspondence between two sets of sequences observable in some computational or mathematical context. What approach would you use? Give an example.

19. (a) What is this? (b) Characterize its observable behavior.

20. Distinguish among S, S^*, and S^¥ as used in the course, with examples.

21. What is a regular expression and what sort of model of computation is associated with it?

22.   Would you use formal proof, simple counter-example, or evidence to argue for the following? Explain.
a. the Church-Turing thesis
b. cellular automata are computationally
    equivalent to Turing machines
c. a given language is not regular
d. the equivalence between deterministic and nondeterministic finite automata
e. a given DFA does not accept the language
   defined by a given regular expression
f. neural nets are computationally equivalent to
   Persistent Turing machines

23. Which of the following are sets, sequences, finite languages, or sets of languages? (The categories may be overlapping) Give examples of each.
a. CFL
b. an alphabet
c. all strings accepted by a particular DFA M
d. a single item accepted by a particular DFA M

24. Give an examples of each of the following and relate it to some model of computation:
a. a finite sequence of symbols
b. a finite sequence of (input, output) pairs
c. a finite set of finite sequences
d. a set of sets of finite sequences
e. an infinite set of finite sequences
f. an infinite sequence
g. an infinite set of infinite sequences

25. The following list of concepts relate to three major models discussed in the course. Arrange the terms into a three-column table, one column per topic, and explain it:
regular expression
pushdown automaton
Turing machine
context-free language
recursive set
deterministic finite automaton
computable function

decidable problem
regular language
stack machine
context-free grammar

26. What does this say?

27. Which is, or is representable by, a (set, graph, language, function, sequence)? Explain in one or two sentences.
a. a DFA
b. a finite transducer
c. what is computed by a DFA
d. what is accepted by a DFA
e. a PDA
f. what is computed by a PDA
g. what is accepted by a PDA
h. what is computed by a TM
i. what is accepted by a DFA

28. Which of the following halt (a)lways, (s)ometimes, or (n)ever? For each category (a, s, n) state the general reason for halting, sometimes halting, or never halting.
___ C++ programs
___ S-language programs
___ DFAs
___ PDAs
___ TMs
___ Transducers
___ Window 2000 GUI

29. State and explain the relationship among transducers, Turing machines, and at least one of the following:

a. Expert systems

b. Cellular automata

c. Video games

d. Neural nets

e. Voice-recognition systems

f. Learning systems

g. Compilers

30. Name two ways in which a finite transducer differs from a DFA, PDA, or TM.

31. Relate the computational power of the S language to the power of DFAs and of Turing machines.

32. What is the range of d, for Turing machines? What does this allow TMs to do that PDAs can’t do?

33. Does a transducer compute an algorithm? Why or why not?

34. What data structure does a PDA have that DFA lacks? Briefly explain.

35. In the context of this course, what does
d : Q ´ G ® Q ´ G È {L, R}
mean and what model uses it?

36. In the context of this course, what does
d : Q ´ S ® Q
mean (break it down) and what model uses it?

37. What is this? S ® SS | a | l

38. What sort of device accepts a language that can be described by a grammar that consists of productions?

39. Distinguish stream languages from languages.

40. What sort of device accepts a language that can be described by an expression that uses the +, *, and concatenation operators?

41. What model of computation is considered equivalent in expressiveness to a programming language such as C++?

42. What language is accepted by this:

43. In terms of discrete-mathematics categories such as sets, sequences, functions, and languages, discuss the formal aspect of transition-system-based models of computation (the classes of automata discussed in our seminar). You may do this by specifying an instance of each model as a tuple, M = á…ñ, saying what set, sequence, function, or language each member of the tuple stands for, and saying what sort of set, sequence, function, or language is accepted or computed by the automaton.

44.   What is this and what model of computation corresponds to it?
                                                                  S ® SS
                                                                  S ® a
                                                                  S ® l

45. What three models that we discussed correspond to the notion of algorithmic computability? Describe them in one or two sentences.

46. Give language-related examples showing contexts in which l (empty string), {} (null set), and b/ or # (blank symbol) are used in this course, showing that they differ.

47. Explain what is meant by
(" L Í S^*) Regular(L) Þ Context-free(L),
and why it is true.

48. If language L is accepted by a Turing machine, then is it necessarily context free? Explain the relationship between CFLs and recursive sets, referring to the respective models of computation.

49. Relate the notions of interaction, Turing machines, and parallel computation.

50. What is the Chomsky hierarchy and what does it assert about models of computation?’

Theory of computing study questions

Contents

T1 Countability

T2 Finite automata

T4 TM

T5 RAM

T6 Interaction

T7 Concurrency

Multiple topics

Study questions on Introduction and Background

Short-answer questions

Study questions on Topic 1: Diagonal proofs, uncountable sets, coinduction

1. Countable sets

2. Uncountable sets

3. Incompleteness

4. Streams and coinduction

Short and longer answer questions for topic 1

1a. Proof of countability

1b. Proof of uncountability

1c. Coinductive definition

1d. Formal language notation

Study questions on Topic 2: Finite automata and regular languages

2. Regular languages and regular expressions

3. Nondeterministic finite automata

4. Proving a language is not regular

5. L.exical analysis

Short and longer answer study questions for topic 2

2a. Construct FA

Miscellaneous

2b. Regular expression

2c. Pumping Lemma

2d. Proof of expressiveness

Topic 3: PDAs and context-free languages

1. Pushdown automata

2. Context free languages and context-free grammars

3. Derivations and parsing

4. Properties of PDAs, CFLs, and CFGs

Longer answer

3a. Derivation

3b. CFG

3c. PDA model

3d. Proof of expressiveness

Study questions on Topic 4: Turing machines and decidable problems

1. TMs

2. TM computations

3. Turing decidability

4. Undecidability

Longer answer

4a. Describe TM

4a, 4b. TM Construction

4c. Undecidability

4d. Reducibility

Study questions on Topic 5: Random-access machines and m-recursive functions

1. Random-access machines and the S language

2. m-recursive functions

3. Semidecidability

4. Church-Turing Thesis

Short and longer answer

5a. Recursive definability and computability*

5b. Random access machine model

5c. Expressiveness of the RAM model

5d. Chomsky hierarchy*

5e. Semidecidability

Study questions on Topic 6: Interactive computation

1. Algorithms vs interaction

2. Sequential interaction

3. Persistent Turing machines

Short and longer answer questions

6a. Distinguish algorithmic from interactive computation

6b. Compare and contrast models of algorithmic and interactive computation

Study questions on Topic 7: Concurrent and multi-stream computation

1. Models of parallel and distributed computing

2. Multi-stream and indirect interaction

3. Other models of computation

Short and longer answer

7a. Describe forms of concurrency*

7b. Describe some models of parallel computation

7c. Describe connectionist and multi-agent models

Study questions on multiple topics

Study questions on Topic 1:
Diagonal proofs, uncountable sets, coinduction

2. Context free languages and
context-free grammars

Study questions on Topic 4:
Turing machines and decidable problems

Study questions on Topic 5:
Random-access machines and m-recursive functions

1. Random-access machines
and the S language

Study questions on Topic 7:
Concurrent and multi-stream computation