COMP 590 – Advanced Topics in Comp Sci – Spring 2018

Course Syllabus

Course URL: http://prof.msoltys.com/?page_id=3183
CI Catalogue URL
Instructor: Michael Soltys <michael.soltys@csuci.edu>
Twitter: @MichaelMSoltys
Course Outline: This course presents the foundations of computation. We define the basic elements of computation: alphabets, words and languages. We then study languages through the lens of standard models of computation: Finite Automata (as DFAs, NFAs and Regular Expressions), Context Free Grammars (as grammars and as PDAs), and finally Turing machines. We will look at issues of decidability, and at impossibility results (e.g., Pumping Lemmas, undecidability, the Post Correspondence problem, etc.). At the end of the course the student will have a firm grasp of the foundations of computer science and the limits of computability, as well as deciding what model of computation is suitable for a given problem.
Lectures: Tuesdays, 4-5pm, Location Bell Tower 2372.
Textbook: Chapter 8 in An Introduction to the Analysis of Algorithms, by Michael Soltys.
Grading: One long assignment, to be completed throughout the course, and handed in at the end.
How to avoid plagiarism: The assignment will be worked on individually; verbal discussions of problems among individuals are allowed, but you should not show written notes, and you should not leave such discussions with written notes.
Attendance: Attendance is required.
Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.
Check this web page regularly for announcements.

Announcements and class diary

May 8, 2018: Last lecture, we discussed $latex lambda-text{Calculus}$, recursive functions, register machines, and how all these distinct models of computation describe exactly the same set of recognizable languages as Turing machines. This is strong evidence for the validity of the Church-Turing thesis, and a definitive definition of what it means to be computable by an algorithm.
May 1, 2018: The Post Correspondence problem.
April 24, 2018: Universal Turing machine, and the first example of an undecidable language: $latex A_{\text{TM}}$, with a proof by the diagonal argument that it is undecidable.
April 17, 2018: We discussed problem 10 in the Assignment Problems section below.
April 10, 2018: No class, instructor at the ABET accreditation workshop.
April 3, 2018: We introduce Turing Machines.
Mar 27, 2018: Seminar by Adrian Domanico.
Mar 20, 2018: Spring break
Mar 13, 2018: We introduced Push Down Automata, as the “hardware” corresponding to Context-Free Grammars, and gave a few examples.
Mar 6, 2018: Introduced Context Free Grammar (CFG); gave a brief history, and applications to programming languages and compilers. We posed an interesting problem; given two finite lists of equal length $latex (L_1,L_2)$ of strings, $latex \exists i_1,i_2,\ldots,i_k$ such that $latex i_j\in[|L_1|]$ and $latex w_{i_1}w_{i_2}\ldots w_{i_k}=v_{i_1}v_{i_2}\ldots v_{i_k}$. Is there an algorithm for this problem; there is a $latex O(|L_1|^{N\cdot |L_1|})$ algorithm in the case where we allow at most $latex N$ repetitions of each string; can we do better?
Feb 27, 2018: We looked at the Dynamic Programming algorithm for translating DFAs to Regular Expressions ($latex R_{ij}^{(k)}$).
Feb 20, 2018: How to show that a language is not regular? We introduce the Pumping Lemma, and show examples of applications.
Feb 13, 2018: We discussed Regular Expressions, and the fact that DFAs, NFAs and REs recognize the same class of languages: regular languages. Also, the limitations of these models: if counting is necessary, they cannot do it.
Feb 6, 2018: Definition of a regular language; all finite languages are regular. Extended transition function ($latex \hat\delta$) and Non-deterministic finite automata (NFA).
Jan 31, 2018: This course has a Canvas page: https://csuci.instructure.com/courses/4098 but we will use it minimally.
Jan 30, 2018: We introduced finite automata and saw some examples of languages recognized by them. We posed the following exercise: find a DFA for: $latex \{0,1\}^*001^*00$.
Jan 25, 2018: Please pick up your course materials (at cost of printing) from the Copy Center at the UGlen Town Center (email: copycenter@coast-repro.com) .
Jan 23, 2018: First lecture, alphabets, words and languages; Kleene’s star and concatenation. We discussed the philosophical underpinnings of representing information with strings.

Assignment Problems

Give a DFA for $latex \{0,1\}^*001^*00$ and prove that it is correct.
Let $latex L_n=\{(f_i)_u:i\le n\}$, that is, $latex L_n$ is the language of unary encodings of the first $latex n$ Fibonacci numbers. Design $latex A_n$ with as small a number of states as possible.
Consider the family of languages $latex L_p=\{w\in\{0,1\}^*:\#(w)_0=p\}$, that is, $latex L_p$ is the languages of binary strings where the number of 0s is $latex p$, where $latex p$ is a prime. Give the Regular Expression for $latex L_p$.
Use the Pumping Lemma to show that the language $latex L_{\text{eq}}=\{w\in\{0,1\}^*:\#(w)_0=\#(w)_1\}$ is not regular.
Give an example of a language that is not regular, but nevertheless satisfies the property asserted in the Pumping Lemma. Is this consistent with the Pumping Lemma itself?
Suppose that we are given a DFA with three states $latex \{1,2,3\}$, where state 1 is the starting state, and state 3 is the accepting state. Each state has a self-loop on zero (0) and an arrow to the next state on one (1). Using the $latex R_{ij}^{(k)}$ method for constructing a regular expression from a DFA, provide the corresponding regular expression. Also, simplify as you go using the *algebraic laws* for regular expressions.
Do Problem 8.18 in the notes.
Show that the language $latex L_{\text{eq}}$ in question 4 is Context-Free.
Design a Turing Machine for the following language: $latex L=\{w\in\{0,1\}^*:\text{first }\lfloor |w|/2\rfloor\text{ half of }w\text{ has more zeros than rest of }w\}$.
Consider the following type of Turing machine: states $latex Q=\{q_0,q_1,q_2,q_3,q_{\text{halt}}\}$, that is, it has four states besides a single halting state, and the initial state $latex q_0$. It has the following tape an input alphabet: $latex \Gamma=\Sigma=\{0,1\}$, and the assumption is that initially the tape consists only of 0s (zeros). The machine starts in state $latex q_0$ and and when it halts, the contents of the tape are the output. The contents are understood to be the string consisting of the string between the left-most and the right-most 1, inclusive. If there are no 1s on the tape, the contents are considered to be $latex \varepsilon$. If there is a single 1, it is both the left-most and the right-most, and so the output is 1. Please design such a machine which outputs the longest possible string of 1s.
Suppose $latex L$ is undecidable. Is it possible to have a Turing machine $latex M$ such that $latex M$ is a decider and a regular expression $latex R$ such that if $latex x\in\Sigma^*-L(R)$ then $latex M$ answers correctly whether $latex x\in L$.
Show that PCP is Turing recognizable (while it is not Turing decidable).