Photo from BBC News article by Prof. Jack Copeland

CSC427-F: Introduction to the Theory of Computation

News and Announcements for CSC427 Introduction to the Theory of Computation.

Apr 29:

Final Exam posted.

Apr 14:

Problem set 9 posted.

Apr 12:

Second test date change: now Friday, 21 April.

Mar 31:

Problem set 8 posted.

Mar 26:

Problem set 7 posted.

Mar 9:

Problem set 6 posted.

Feb 17:

Midterm date change: now Friday, March 3.

Feb 17:

Problem set 4 posted.

Feb 13:

Midterm announced: Wednesday, March 1.

Feb 8:

Problem set 3 posted.

Feb 1:

Problem set 2 posted.

Jan 25:

Problem set 1 posted.

Jan 12:

Semester begins. Welcome!

Syllabus for CSC427 Introduction to the Theory of Computation.

General

This is a first course in the theory of computation. The course is of a generally mathematical nature, however it requires no calculus, or other "normal" mathematics. It explores what is computation. This is presented by way of machine models, and also linguistic models.

• The assigned textbook is Introduction to the Theory of Computer, Third Edition by Mike Sipser.
• Please follow us on twitter/csc_517 (same as 317 twitter feed)
• Some course notes will be found on the Csc427 blog.
• The course assigns weekly problem sets, due on Wednesdays. It is very important to do the homeworks.
• There maybe reading assignments from texts other than the class text.
• Our grader is Yinghao Si, y.si@umiami.edu.
• No late homeworks accepted after the last day of classes.
• There were be two tests and a final (updated information as announced in class 13 Feb.)
• First test: Friday, March 3.
• Second test: TBA
• Final: Wednesday, May 3, 2:00-4:30.
• Grades are 30% final, 20% first test, 20% second test, and 30% homework.

Writing Credit

Writing credit is no longer offered for classes without a W designation.

Class notes for CSC427 Introduction to the Theory of Computation.

• Introduction
  • An historical perspective. See the blog posting.
• Finite Automata
  • Deterministic
  • Nondeterministic
  • Regular Expressions
  • Pumping Lemma and non-regular languages
  • The Pumping Argument in the Court of Logic
• Context Free Languages
  • Grammars
  • Ambiguity
  • Push down automatas
  • Deterministic PDA's and ambiguity
  • Closure properties for CFL's
  • Pumping Lemma and non CF languages
• Turning Machines
  • Definition and programming
  • Multitape and nondeterministic
  • Enumerators
  • Turing decidable, a.k.a. recursive
  • Turing recognizable, a.k.a. recursively enumerable
  • Decidability of regular languages and CFL's.
  • Decidability of equality of regular languages and emptiness for a CFL.

Decidability Round Up

Problem	Description	Computability	Notes
AFA	(i,j) ⊆ N × N s.t. FAi accepts j	decidable	run DFA
EFA	i ⊆ N s.t. L(FAi) = ∅	decidable	non-det guess element in complement
EQFA	(i,j) ⊆ N × N s.t. L(FAi) =L(FAj)	decidable	emptiness of symmetric difference
ACFG	(i,j) ⊆ N × N s.t. PDAi accepts j	decidable	Chomsky Normal Form
ECFG	i ⊆ N s.t. L(CFGi) = ∅	decidable	marking algorithm
X	x ∉ X, where X is decidable	decidable
co-EQCFG	(i,j) ∉ EQCFG	RE	∃ x s.t. (x,i) ∈ ACFG etc
EQCFG	(i,j) ⊆ N × N s.t. L(PDAi) = L(PDAj)	co-RE
ATM	(i,j) ⊆ N × N s.t. Mi(j) halts accepts	RE	run j on Mi
co-ATM	(i,j) ∉ HALT	co-RE
HALT	(i,j) ⊆ N × N s.t. Mi(j) halts	RE	run j on Mi
co-HALT	(i,j) ∉ HALT	co-RE
ETM	i ⊆ N s.t. L(Mi) = ∅	co-RE	Rice's theorm
co-ETM	i ∉ETM	RE	∃ x s.t. (x,i) ∈ ATM
EQTM	(i,j) ⊆ N × N s.t. L(Mi)=L(Mj)	non-RE	¬(RE ∪ co-RE)
co-EQTM	(i,j) ∉ EQTM	non-RE

Problem Sets for CSC427 Introduction to the Theory of Computation.

• Problem Set 1: Exercises 1.4, 1.5 and 1.6. Due: Wed, 1 Feb, class time.
• Problem Set 2: Exercises 1.7, 1.8, 1.9 and 1.10. Due: Wed, 8 Feb, class time.
• Problem Set 3: Exercises 1.16, 1.17 and 1.18. Due: Wed, 15 Feb, class time.
• Problem Set 4: Exercises 1.19, 1.20 and 1.21 and 1.29 Due: Wed, 22 Feb, class time.
• Problem Set 5:
  • Exercises 1.24, 1.37.
  • The next problems refer to the court of logic.
  • Show the complete "trial transcript" in the court of law convicting:
    • {aⁱba²ⁱ} of not being regular.
    • {w # w^R} of not being regular, where w is a string of 0, 1's, and # is itself, and the superscript R means "string in reverse".
  • Show a complete "trial transcript" in the court of law acquitting:
    • The set of strings (abc)* of the alphabet {a,b,c}.
    • The set of strings {aⁱ | i is a multiple of 10}.
  • Use the closure properties of regular languages to show:
    • The language { 0^i (10)^j 1^i | i, j ≥ 0 } is not regular.
    • The language { 0^i 1^j 0^k | i,j,k ≥ 0, and either i = j or j = k } is not regular.
  • Show the argument that acquits { 0^i 1^j 0^k | i,j,k ≥ 0, and either i = j or j = k } in the court of logic.
  Due: Wed, 1 Mar, class time.
• Problem Set 6: Exercise 2.1, 2.4, 2.5, 2.6, 2.16 and 2.17. Due: Fri, March 24th, class time. (Note Friday due date.)
• Problem Set 7: Exercises 2.36, 2.46, 2,47, 3.1 and 3.2. Due: Fri, March 31, class time.
• Problem Set 8:
  • Exercise 2.14, 3.8
  • Give the digram for TM that can increment by one a binary number. Started with in the configuration ⊣ ␣ s where s is a 0,1 string, ends with ⊣ ␣ t where t is a 0,1 string, and as a value (in binary representation), t is one more than s.
  • Give the digram for TM that can decrement by one a binary number. Started with in the configuration ⊣ ␣ s where s is a 0,1 string, ends with ⊣ ␣ t where t is a 0,1 string, and as a value (in binary representation), t is one less than s.
  • Using increment and decrement, give a TM that can add, using increment and decrement. That is, started with ⊣ ␣ s ␣ t, where s and t are 0,1 strings, ends with ⊣ ␣ u, where u us a 0,1 string, and as values (in binary representation) u is the of s and t.
  • Note: In these problems, the head is started over the start of tape.
  Due: Wed, 12 April, class time.
• Problem Set 9: Show the workings of a Multitape Turing Machine for the language A_DFA, the set of all pairs B,x, such that the DFA B accepts x, the precise DFA that is M₁ of problem 1.1 in the book (page 83).
  Assume a multitape machine where the input tape as B,x, a "current state tape" contains the current tape, and "x" is copied down to a new tape, for convenience of not having to run back and forth over the input tape.
  Also assume:
  • B is presented in the form where: states are numbered in binary (leading zeros allowed) and the letter "Q" appended (e.g. state of index 4 is "Q0100");
  • tape symbols are numbered in binary (leading zeros allowed) and the letter "S" is appended (e.g. the symbol "a" is "S01" and symbol "b" is "S10");
  • Transitions are a concatenation of a state, a tape symbol, and a state (i.e. "Q01S10Q10" would say from state 1 on symbol 2 go to state 2);
  • the entire B is "R" followed by the starting state, then "F" followed by a concatenation of final states, then "D" followed by a concatenation of transitions;
  • and the entire input B,x is written on the input tape as B as described, followed by a blank, followed by x, which is encoded also using the "S" form of symbols.
  Illustrate the computation on M₁ of problem 1.1 in the book (page 83) on the input "bbaaa".
  Be sure to show the encoding as B; the multiple tapes at each of the steps of the computation; including the copy of the initial state on the the state tape and the check of the final state in the state tape for acceptance against the description B.
  E.g. For the DFA pictured as Figure 1.4 page 34,
  • B = RQ01FQ10DQ01S0Q01Q01S1Q10Q10S1Q10Q10S0Q11Q11S0Q10Q11S1Q10
  
  Due: Wed, 19 April, class time.

References for CSC427 Introduction to the Theory of Computation.

• History of Computing Hardware at wikipedia