Theory of Computing

Computer Science 461 - Spring 2025

Week 1 Notes

Mon, Jan 13

Today we talked about proof techniques, particularly proof by induction. We looked at these two examples:

1. Prove that if a set $A$ has $n$ elements, then $A$ has $2^n$ subsets.

The second example had to do with the famous Tower’s of Hanoi puzzle( see https://youtu.be/SMleU0oeGLg).

2. Use induction to prove that it is always possible to move the disks from one peg to another by moving one disk at a time without breaking the rules.

You can also translate many induction arguments into recursive algorithms.

3. Write a Python function sublists(A) that inputs a list A and returns a list containing every sublist of A.

   We did this in class and we came up with something like this:

    def sublists(A):
        if len(A) == 0:
            return [A]
        last = A[-1]
        B = A[0:-1]
        sublists_without_last = sublists(other_elements)
        sublists_with_last = [s + [last] for s in sublists_without_last]
        return sublists_without_last + sublists_with_last

4. Suppose you have three stack variables (implemented as Python lists):

   stack1 = [10 - k for k in range(10)]
   stack2 = []
   stack3 = []

   Write a function move_disks(n, start_stack, temp_stack, final_stack) that recursively moves n disks from the start_stack to the final stack.

Wed, Jan 15

Today we reviewed mathematical notation, including some new notation we will be using. We defined alphabets which are sets of symbols we can use to represent things. The most common alphabet in computer science is the binary alphabet $\Sigma = \{0, 1\}$. We use the notation $\Sigma^*$ to denote the set of all possible finite length strings constructed from $\Sigma$.

A set $S$ can be represented or encoded using an alphabet $\Sigma$ if there is a 1-to-1 function $E: S \rightarrow \Sigma^*$.

We discussed specific encodings such as how to encode the integers $\mathbb{Z}$ and the rationals $\mathbb{Q}$.

• Example: ASCII characters

We also observed another fact:

At the end we considered the set $\{0,1\}^\infty = \{f : f : \mathbb{N}\rightarrow \{0,1\} \}$ which you can think of as the set of all infinitely long strings of zeros and ones. We finished by proving

A corollary of this theorem is that $\{0,1\}^\infty$ is uncountable.

Fri, Jan 17

We talked about Boolean circuits which are formed by AND, OR, and NOT gates. These can be used to implement any Boolean expression formed by the $\wedge$ (AND), $\vee$ (OR), and $\neg$ (NOT) operators.

1. Write a Boolean expression that takes three Boolean inputs, $x, y, z$ and returns true if $x, y, z$ are all the same, and false otherwise.

2. Show that you can construct the function IF x THEN y ELSE z for any Boolean inputs x, y, z using AND, OR, and NOT gates.

   $$(x \wedge y) \vee (\neg x \wedge z)$$

3. Use mathematical induction (and the previous result) to prove the following:

We say that the Boolean operations ($\wedge$, $\vee$, $\neg$) are a universal set of operations since every Boolean function on $\{0,1\}^n$ can be constructed using those operations.

We finished by talking about how the NAND operation is universal all by itself. Using just NAND gates, you can construct any Boolean function on $\{0,1\}^n$.

4. Show that you can use a NAND gate to implement a NOT gate.

5. Show that you can use two NAND gates to implement an AND gate.

6. Use a truth table to confirm that (NOT x) NAND (NOT y) is equivalent to x OR y.

Week 2 Notes

Wed, Jan 22

• Slides: Impossible programs

Fri, Jan 24

Last time we saw that some functions $f: \{0,1\}^* \rightarrow \{0,1\}$ cannot be computed by a computer program. We saw two proofs that seemed very different. One used a cardinality argument and the other used proof by contradiction to show that the program check_if_program_returns_one() is impossible. It turns out that both proofs are actually closely related.

Suppose we make a list of all possible programs on the left column of an infinite table, with a list of all possible input strings at the top of the table. The values in the body of the table are the output of each program on each input (including the possibility that there is no output). The table might look like this:

We can construct a function $f:\{0,1\}^* \rightarrow \{0,1\}$ that cannot correspond to any program by using the same diagonalization argument that proves that there are uncountably many infinite binary sequences. That’s essentially what we did when we tried to construct the function check_if_program_returns_one() last time. We created a function reverse_check() that corresponds to reversing the values on the main diagonal of the table above. So we were using a diagonalization argument, which is the same argument used to prove that there are uncountably many functions $f:\{0,1\}^* \rightarrow \{0,1\}$.

After that, we introduced finite automata. We started with this example: An automatic door at a grocery store has sensors on the front and rear. It opens if the sensor on the front is active. It won’t close until neither of the sensors are active. You can model this with the following state diagram:

This is an example of a finite state machine, also known as a deterministic finite automata (DFA).

1. What are the sets $Q$ and $\Sigma$ for the automatic door example above?

2. Make a table showing the values of the transition function $\delta$ for the automatic door.

3. An automatic toll booth accepts nickles, dimes, and quarters. The gate won’t open until it receives 25 cents. Draw a state diagram for the toll booth. What are the sets $Q$ and $\Sigma$?

4. A combination lock (like the ones at the campus post office) can be modeled as a finite state machine. What are the states and what are the input signals?

5. Describe a DFA that can compute the function $f: \{0,1\}^* \rightarrow \{0,1\}$ which returns 1 when the input string has an odd number of 1’s and 0 otherwise.

Week 3 Notes

Mon, Jan 27

Today we started with these questions about DFAs:

1. For the DFA shown below:
   1. What is the transition function?
   2. Describe the function $f:\{0,1\}^* \rightarrow \{0,1\}$ that this DFA computes.
2. Draw the state diagram for a DFA that computes whether a binary string contains 011.

Conceptually, when we think about a DFA, we understand that it can do two things:

• A DFA can compute a function $f:\Sigma^* \rightarrow \{0,1\}$.
• A DFA can recognize a language $L \subseteq \Sigma^*$.

It’s important to understand that these two interpretations of what a DFA does are equivalent, because there is a simple bijection between the set of all possible languages (the power set $2^{\Sigma^*}$ of $\Sigma^*$) and the set of all possible functions $f: \Sigma^* \rightarrow \{0,1\}$.

3. Construct a bijection from the power set $2^{\Sigma^*}$ to $\{f: f: \Sigma^* \rightarrow \{0,1\}\}$.

Our solution ended up involving the indicator function for a set $L \subseteq \Sigma^*$, where $$f_L(w) = \begin{cases} 1 & \text{ if } w \in L, \\ 0 & \text{ otherwise.} \end{cases}$$

Wed, Jan 29

We started by constructing some more examples of DFAs.

1. Find a DFA that computes whether a binary string ends with 011. (This is similar, but not the same as a DFA we constructed last time).

2. How many states would a DFA need if you wanted to check whether a binary string has a 1 in the third position from the last?

Then we talked about these properties of regular languages.

3. How would you prove this? If I give you a finite set of strings $L$, how could you turn that into a DFA that recognizes $L$?

4. Suppose that $A = \{ \text{big}, \text{small}, \text{pet} \}$ and $B = \{ \text{cat}, \text{dog} \}$. What are the elements of $A \circ B$ and $B^*$?

We proved the first part of the theorem above (regular languages are closed under unions) in class by thinking about how to construct a new DFA $M$ that accepts $A \cup B$ using DFAs $M_A$ and $M_B$ that accept $A$ and $B$ respectively. To prove this, we answered these questions:

1. If the machine $M$ is built by running both $M_A$ and $M_B$ simultaneously, what are the possible states of $M$?

2. What are the initial states for $M$?

3. What is the transition function for $M$?

4. What are the accepting states of $M$?

Fri, Jan 31

1. We started by asking whether regular languages are closed under intersections. Can we adapt the proof we gave last time for unions to intersections?

   Yes, regularly languages are closed under intersections. The proof is almost exactly the same as the proof for unions, the only difference is that the DFA to recognize $A \cap B$ has final states $F_A \times F_B$ while the DFA to recognize $A \cup B$ has final states $(F_A \times Q_B) \cup (Q_A \times F_B)$, that is, any pair of states from $Q_A \times Q_B$ where at least one of the two is final.

To prove that regular languages are closed under concatenation, we introduced a new idea: non-deterministic finite automata (NFAs).

We looked at this example:

An NFA can have more than one arrow exiting a state with the same input. When that happens, the machine splits into multiple copies, one for each possible next state.

If an NFA enters a state that has exiting arrows labeled with $\epsilon$, then the NFA immediately splits into multiple copies, one where the current state stays the same, and one where the current state moves along each branch labeled $\epsilon$. This can happen several times, if there is a sequence of branches labeled $\epsilon$.

If there is no arrow leaving a state for a given input signal, that means that the current copy of the machine is a dead end and it does not need to be continued.

The NFA accepts a string if any of the parallel computations is in an accepting state after the string is read. We answered these questions:

2. Which states are active at each step as we read the input string 01010?

3. Does this NFA accept the string 01010?

4. Describe the set of all strings in $\{0,1\}^*$ that this NFA will accept.

Here is the technical definition of an NFA.

The only change from the definition of a DFA is that the transition function for an NFA can return a set of states at each step (including, possibly, the empty set). Think of these multivalued transitions as creating multiple branching computations that run in parallel. If the transition function returns the empty set, that means that that branch of the parallel computation is a dead end and does not continue.

5. Let $A, B \subseteq \Sigma^*$ be regular languages recognized by DFAs $M_A$ and $M_B$ respectively. Describe an NFA that uses the $M_A$ and $M_B$ to check if a string is in the union $A \cup B$. Note that every DFA is an NFA that has a transition function that only ever returns a single state at a time.

6. Describe an NFA that can check whether or not the 3rd to last digit of a binary string is 1 using fewer states than the DFA we described last time. Hint: What if the NFA “guesses” every time it sees a 1 that that might be the third to last entry. What should it’s states be from that point on?

Week 4 Notes

Mon, Feb 3

Today we continued talking about NFAs. We’ve been following the textbook by Meshwari & Smid pretty closely this week, so I recommend reading skimming Section 2.6 which is what we covered today.

1. We described an NFA that recognizes the concatentation $AB$ of two regular languages by running DFAs $M_A$ and $M_B$ in parallel. We answer these questions about the NFA:

   1. What are the states of the NFA?
   2. What are the final states of the NFA?

2. We also described an NFA that recognizes the Kleene star $A^*$ of a regular language. The idea is similar to the previous construction, but you need a way to accept the empty string (if it isn’t part of $A$).

To complete the proof that regular languages are closed under these two operations, we need to prove this:

The proof is surprisingly simple. An NFA with states $Q$, transition function $\delta: Q \times \Sigma \rightarrow 2^Q$ can be turned into a DFA that has states $2^Q$ and transition function $\delta_2: 2^Q \times \Sigma \rightarrow 2^Q$.

3. Describe specifically what $\delta_2(S, \sigma)$ returns for any subset $S \subseteq Q$ using $\delta$.

4. If $F$ denotes the accepting states of the NFA, then what are the corresponding accepting states of the DFA?

5. If $q \in Q$ is the initial state of the NFA, what is the initial state of the DFA?

We applied the idea of this proof to Exercise 5 from Homework 3.

Wed, Feb 5

We introduced regular expressions (regex).

Regular expressions are used to match sets of strings (i.e., languages over $\Sigma$).

• $e_1e_2$ matches any concatenation of a string matched by $e_1$ with a string matched by $e_2$.
  
• $e_1|e_2$ matches anything matched by $e_1$ or $e_2$.
  
• $e_1*$ matches any finite concatenation of strings that $e_1$ matches (including zero matches).

1. Describe what the following regular expressions represent:

   1. (0|1)0*
   2. Σ*1Σ*
   3. (0|1)*

2. Write a regular expression that recognizes the base-10 decimal form of any integer that is a multiple of 5.

Most programming languages use Perl compatible regular expressions which have several additional features to make it easier to work with regular expressions. Here are some examples we talked about in class.

Here is a simple Python regex example:

import re 

s = "My pet dog likes to go to the park."
expr = "pet\s(dog|cat|bird)"
match = re.search(expr, s)
print(match)

3. Write a regular expression that would match any e-mail address of the form name@domain.extension.

4. Find a regular expression over the alphabet $\Sigma = \{0,1\}$ that matches all strings that start with a 1, end with a 1, and have an even number of zeros between.

We stated, but did not prove the following theorem.

5. Find an NFA that recognizes the same language as the regular expression (ab|a)*. Use the ideas from the previous classes about how to build NFAs to find the union, concatenation, and Kleene star of languages.

Fri, Feb 7

Today we talked about the proof of the theorem from last time that regular languages and regular expressions are equivalent. One direction is easy: every language described by a regular expression is regular. This is because we already know that regular languages are closed under the union, concatenation, and Kleene-star operations and we also know that any finite set of strings is a regular language.

Therefore, we should be able to solve this example, which we didn’t have time for on Wednesday.

1. Find an NFA that recognizes the same language as the regular expression (ab|a)*. Use the ideas from the previous classes about how to build NFAs to find the union, concatenation, and Kleene star of languages.

To prove the converse, we described an algorithm for converting NFAs to regular expressions. Note that the Maheshwwari & Smid textbook describes a different approach to convert an NFA into a regular expression in Section 2.8. Our approach is to use a generalized NFA:

To finish the proof, we make two observations:

First, you can convert any NFA to a GNFA by adding a special start state that has an epsilon transition to the original start state and a new accept state that has an epsilon transition from any old final state.

Second, if you have a GNFA with $n > 2$ states, there is an equivalent GNFA with $n-1$ states, because you can remove any state (other than the initial and final states) and replace incoming/outgoing transitions with transitions described by a regex.

We did the following example to illustrate.

2. Let Σ={A,C,G,T}. Convert the following NFA to a GNFA, and then remove states until there are only 2 (the start and accept states).

3. What regular expression is equivalent to the NFA above?

We finished by talking about languages which are not regular. One simple language that is not regular is the following:

$$A = \{w \in \{0,1\}^* : w \text{ has an equal number of } 0 \text{s and } 1 \text{s} \}.$$

Week 5 Notes

Mon, Feb 10

Here is a picture that helps to understand what is going on. It also gives a clue about why this theorem is true.

The proof is really simple. If a finite state machine reads a long enough string, eventually it has to loop back to the same state twice. The input signals that caused the machine to take that loop make up the substring $y$ in the theorem.

The pumping lemma is a useful tool to prove that some languages are not regular. You can use the pumping lemma to give a proof by contradiction. Be careful, the pumping lemma cannot be used to prove that a language is regular.

We applied this technique to prove that the following languages are not regular.

1. $L = \{w : w \text{ has an equal number of 0 and 1's}\}$

2. $L = \{0^{n^2} : n \in \mathbb{N}\}$.

Here is a nice meme proof using the pumping lemma from Barak textbook.

Wed, Feb 12

Today we looked at more examples of regular and non-regular languages.

1. $L = \{w \in \{0, 1\}^* : w \text{ is a palindrome} \}$.

2. $L = \{w : w \text{ contains an equal number of } 01 \text{ and } 10 \text{ substrings}\}$.

The converse of the pumping lemma is not true. So you can’t use the pumping lemma to prove that a language is regular. In fact, here is a language that is non-regular, but every string in the language is pump-able!

$$L = \{a^i b^j c^k : i, j, k \ge 0 \text{ and if } i = 1 \text{ then } j = k\}.$$

3. Explain why there is a pumping number $p$ (in fact $p=1$ works) such that any string $w \in L$ can be “pumped”.

4. Despite this, explain why $L$ is not a regular language. Hint: if there was a DFA that recognizes $L$, what other DFAs could you construct?

Many programming languages, including Python & Javascript allow backreferences to previous groups in a regular expression. A group is a part of the regular expression inside parentheses. The special symbol \1 refers to anything matched by the first group in the regular expression. Similarly \2 refers back to anything matched by the second group, and so on. For example: the regular expression "(\w\w*) \1" would match any repeated word like “word word” or “dog dog”. I tried to demonstrate this in class, but I got tripped up because Python requires the regular expression to be entered as a raw string.

import re

regex = r"(\w\w*) \1" # need the r before the quotes to indicate that this is a raw string

print(re.search(regex, "Did I type the the same word twice?"))

5. Explain why regular expressions with backreferences are not really regular expressions (at least not according to our definition). Show that they can match non-regular languages.

Fri, Feb 14

Today we went over some of the problems from homework 4 and the midterm 1 review problems.

Week 6 Notes

Wed, Feb 19

Class canceled because of snow.

Fri, Feb 21

Today we introduced context-free grammars.

1. We explained how the context free grammar

   S         →  aSb
   S         →  ε

   generates the (non-regular) language $$L = \{a^n b^n : n \in \mathbb{N}\}.$$

2. We looked at the example of a CFG and used it to identify the parts $(V,\Sigma, R, S)$ in the formal definition.

   S         →  <subject> <verb> <object>
   <subject> →  <article> <noun>
   <article> →  a | the
   <noun>    →  boy | girl | dog
   <verb>    →  runs | walks | talks
   <object>  →  <prep> <subject>
   <prep>    →  to |from

   Draw a parse tree that shows how to derive the sentence “The boy talks to the girl.”

3. Find a CFG for the language of matched parentheses.

   Seth suggested this CFG:

        S         →  (S)
        S         →  ()S
        S         →  ε

   This isn’t correct, but it is a good first guess. Explain why this grammar cannot be used to construct the string (())().

4. Find a context-free grammar for the language $$L = \{w \in \{0,1\}^* : w \text{ has an equal number of } 0\text{'s and } 1 \text{'s} \}.$$

We didn’t get to this example, but it is good practice too.

5. Describe how to generate the string (a + a) * a using the context free grammar below:

   <expr>    →  <expr> + <term> | <term>
   <term>    →  <term> * <factor> | <factor>
   <factor>  →  (<expr>) | a

We finished by looking at this example that gives the idea of how a programming language can be though of as a context-free language.

• https://en.wikipedia.org/wiki/File:C_grammar_stmt2_svg.svg

Week 7 Notes

Mon, Feb 24

Last time we used parse trees, but didn’t define them.

Today we looked at some more examples of Context Free Grammars. Lisp is a family of programming languages that have a particularly simple syntax. Lisps are built around S-expressions, which are defined by the following CFG rules:

S → (L) | A
L → S | S L
A → <number> | <string> | <symbol>

For the variables above, S represents any S-expression, L represents a list, and A represents an atom, which can be a number, a string, or a symbolic expression like a variable name or operator (among other things).

1. Draw a parse tree for the S-expression (* (+ 5 6) (- 4 2)). Each node in the parse tree should be labeled with a variable (or symbol if it is a terminal node).

2. Is it possible to draw a different parse tree for this expression? Why or why not?

The S-expression grammar is unambigious, every expression has only one possible parse tree. Unfortunately, many CFGs are ambiguous, i.e., they allow strings with more than one parse tree. Here is a simple example.

E → E + E 
E → E * E 
E → (E) 
E → a

3. Use this CFG to derive the string a+a*a two different ways.

In some (but not all cases) it is possible to find two CFGs that generate the same set of strings, but one is ambiguous and the other isn’t. For example, if we change the grammar above to distinguish between expressions that are terms (T), or factors (F) or sums of terms (E), then we can make an equivalent CFG that is unambiguous:

E  →  E + T | T
T  →  T * F | F
F  →  (E) | a

We say that a language is context-free if it can be generated by a CFG. We use the shorthand CFL to denote a context-free language.

We’ll prove this later by showing that context-free grammars correspond to a special kind of automata with a (potentially infinte) stack called a pushdown automata. But today, we talked about how you can prove this theorem using the three operations (union, concatenation, and Kleene star) for regular expressions.

4. If $A$ and $B$ are both context-free languages, explain why the union $A \cup B$ is context free.

5. If $A$ and $B$ are both context-free languages, explain why the concatenation $A \circ A$ is context free.

6. Explain why the Kleene star of a CFL is context-free.

Wed, Feb 26

This is a little more complicated than the pumping lemma for regular languages. We drew some pictures of parse trees to give an intuitive explanation for why this new pumping lemma is true (see page 126 in Maheshwari & Smid).

We started by looking at two examples:

1. Show that the language $L = \{a^n b a^n : n \in \mathbb{N}\}$ is context-free but not regular.

2. What is the pumping length for the language $L$ above?

3. Show that $L = \{w = w : w \in \{a, b\}^* \}$ is not context-free.

4. Show that $L = \{a^{n^2} : n \in \mathbb{N}\}$ is not context-free.

We didn’t have time for this last problem, so I left it as an exercise to consider:

5. $A = \{a^n b^n c^n : n \in \mathbb{N}\}$ is not context-free. What about the language $B \subset \{a,b,c\}^*$ that consists of all strings with an equal number of a’s, b’s, and c’s? Is that context-free?

Fri, Feb 28

Today we talked about pushdown automata (PDA) which are basically just NFAs with a stack. Note that the book calls these nondeterministic pushdown automata. There are also deterministic pushdown automata, but those turn out to be more complicated, and only the nondeterministic pushdown automata are actually equivalent to CFGs. So, we will always assume that our PDAs are nondeterministic, unless specifically mentioned otherwise. We started with this example:

This PDA accepts the language $L = \{a^n b^n : n \in \mathbb{N}\}$. Notice that each arrow has three parts, for example the first loop is labeled $a, \epsilon/a$ which means you can take this loop if you read an $a$ from the input string, and pop $\epsilon$ (i.e., nothing) from the stack, and then push $a$ onto the stack. We will always use this notation (read, pop/push) for each arc.

PDAs work just like NFAs, except they have this extra rule: You only accept a string if you finish in an accepting state and the stack is empty.

Some things to note:

1. Since the machine is nondeterministic, you can have more than one state (and more than one stack) branching off whenever you have a choice about which arrow to take.

2. If you are in a state and there is no valid arrow to take, then that state dies.

Here is the formal definition.

We looked at these questions:

1. For the PDA below, describe the language that it accepts.
   

   

2. Describe an PDA that accepts the language $L = \{ a^n b^m : n \ge m \}$.

3. Describe an PDA with just one state that accepts the language of balanced parentheses.

4. How many distinct PDAs with 5 states, and $\Sigma = \Gamma = \{0,1\}$ are possible (assuming you only push at most one variable onto the stack at each step), according to the definition?

Week 8 Notes

Mon, Mar 3

Today we talked about the equivalence between CFGs and PDAs.

We sketched the proof of one direction: that if you have a CFG, then there is an PDA that accepts the same language. The other direction is harder to prove, so we skipped it, but you can find the details in more advanced theory of computing textbooks.

The idea of the proof for the forward direction is to create an PDA with three states. In state $q_0$ you immediately transition to $q_1$ reading nothing and push S$ on the stack (where $ is a special symbol to mark the bottom of the stack and S is the symbol for the start variable). Then in state $q_1$ you have two different types of transitions that loop back to $q_1$:

• (Red loops - one for each rule )
  1. Read nothing
  2. Pop a variable off the stack
  3. Push the output of one of the grammar rules for that variable back onto the stack.
• (Blue loops - one for each input alphabet symbol)
  1. Read a symbol from the input
  2. Pop that symbol off the stack.
     
  3. Push nothing

Finally, you have a final transition to the accepting state $q_2$ which involves reading nothing and popping the $ off the stack. If you have finished reading the input when you do this, you will accept the string.

We illustrated how this idea works using the grammar and the input string aabbbb.

    S →  AB
    A →  aAb | ε
    B →  bB | b

After this example, we talked briefly about normal forms for context-free grammars. One important normal form is the Chomsky normal form, which we will talk about next time.

For a context-free grammar $G$, we write $L(G)$ to denote the language generated by $G$.

1. A variable $A$ in a context-free grammar $G$ is useless if there are no strings in $L(G)$ that have a parse tree with $A$ as one of the nodes. Prove that if $G$ has any useless variables, then there is another context-free grammar $H$ that generates the same language, but does not have any useless variables.

   Let $H$ be the CFG obtained by removing all useless variables from $G$ and all rules that reference those useless variables. We have to show that $H$ and $G$ both generate the same language. If $w \in L(G)$, then there is a parse tree for $w$ that doesn’t contain any useless variables. Therefore the same parse tree is a parse tree for generating $w$ using $H$, so $w \in L(H)$. If $w \in L(H)$, then all of the variables and rules for the parse tree to generate $w$ are also variables and rules of $G$. Therefore $w \in L(G)$ which proves that $L(H) = L(G)$. $\square$

Wed, Mar 5

One nice feature of Chomsky normal form is that it makes it easier to check whether a string can be generated by a grammar.

It turns out that there is no general algorithm to check whether or not two CFGs are equivalent. But all CFGs can be converted to Chomsky normal form.

The proof is the following algorithm to convert any CFG into Chomsky normal form.

• Step 1 (Preliminaries).

  1. If any rule has $S$ on the right-hand side, then add a new start variable $S_0$ and rule $S_0 \rightarrow S$ so that the start variable never appears on the right side of a rule. If the grammar can generate the empty string, then add the rule $S_0 \rightarrow \epsilon$.
  2. Remove any $\epsilon$-rules. If $A \rightarrow \epsilon$ is a rule (where $A$ is not the start variable), then for any rule with $A$ on the right-hand side, add an alternative version without the $A$.
  3. Remove any unit rules. Replace any rule $A \rightarrow B$ with rules that directly transition from $A$ to any string that $B$ can transition to.

• Step 2 (Add terminal variables). For each terminal symbol $a \in \Sigma$, create a variable $T_a$ and add the rule $T_a \rightarrow a$. If a rule has more than one symbol in its output, then replace any terminal symbols with their corresponding terminal variables.

• Step 3 (Break up long rules). For any rule of the form $$A \rightarrow X_1 X_2 \cdots X_n$$ where $n > 2$, create new variables $U_1, \ldots, U_{n-2}$ and so that you can replace the long rule with the following shorter rules: $$U_1 \rightarrow X_1 U_2$$ $$U_2 \rightarrow X_2 U_3$$ $$\cdots$$ $$U_{n-2} \rightarrow X_{n-1} X_n$$

At the end of this process your grammar will be in Chomsky normal form.

1. Convert the following CFG to Chomsky normal form.

   S → ABa
   A → aab
   B → Ac

2. Convert the following CFG to Chomsky normal form.

   S → aSa | A
   A → abA | b

3. Explain why the following algorithm won’t work to check if any two CFGs are equivalent:

   • Step 1 - Convert both CFGs to Chomsky normal form.
   • Step 2 - Check to see if the two Chomsky normal forms are the same.

We didn’t have time for it today, but here is one more practice example:

4. Convert the following CFG to Chomsky normal form.

   S → ASA | A | ε
   A → aa | ε

Fri, Mar 7

Today we introduced Turing machines (TMs) which are the most general model of computation that we will discuss. Turing machines are deterministic finite state machines, with an infinite tape that the machine can move along, and both read and write from. Like DFAs and PDAs, Turing machines can accept or reject an input string, but Turing machines also have a third possibility: they might loop forever and neither accept nor reject.

Here are some differences between finite automata and Turing machines:

• The input string is initially written on the tape and the Turing machine is initially pointed at the first symbol of the input string.

• Aside from the input string, the tape is initially filled with special blank symbols (which we’ll denote □).

• The Turing machine can read and (optionally) replace one symbol on the tape at a time before moving left or right.

• The TM can have both accept and reject states. When the Turing machine enters one of these states, it immediately halts and the program is complete.

• A TM might loop forever without ever accepting or rejecting a string.

We looked at these examples of TMs:

1. Describe an algorithm that a Turing machine could implement to check if a string in $\{a,b,=\}^*$ is in the language $\{w=w : w \in \{a,b\}^* \}$. Use the tape alphabet $\{a,b,=,x, □\}$, where you can use an $x$ to mark symbols that have been dealt with. Hint: How could you check that the first character of the string matches the first character after the equals sign?

2. Draw a state diagram for the Turing machine above. Use the notation $$\text{read} \rightarrow \text{write}, \text{move}$$ to label transitions. The move can be either $L$ or $R$, and you can use regular expressions for the character to read. The character to write is optional, you can move without writing anything.
   

3. Describe an algorithm that a TM could use to accept the language $\{a^{2^n} : n \ge 0\}.$ Hint: Try moving from left to right, crossing out every other $a$ as you go. How will you know if there were an even number of a’s? Could you repeat the process? When should you stop?

We didn’t get to it in class, but here is a state diagram for a TM that can accept the language $$L = \{a^{2^n}: n \ge 0\}.$$

Week 9 Notes

Mon, Mar 17

Here is the formal definition of a Turing machine.

Because Turing machines can loop forever, there is a difference between recognizing/accepting a language and deciding a language.

A Turing machine that only recognizes a language $L$ might loop forever when you give it a string that is not in $L$.

Both of the example Turing Machines above actually decide their languages, since they will successfully reject any input that doesn’t match a valid string (they won’t get stuck looping forever without halting). We’ll see examples later of Turing machines that accept but don’t decide a language.

Another thing that Turing Machines can do is compute functions by leaving the output on the tape when it halts.

1. Construct a Turing machine that reads an input string $w \in \{a\}^*$ and leaves $ww$ on the tape when it halts.

This wasn’t to hard to describe the algorithm, but it got a little complicated when we made the state diagram. Once we did that, we defined Turing computable functions.

2. Explain why the function $f(w) = wwww$ is Turing computable.

3. Explain why the function $$f(w) = \begin{cases} 1 & \text{ if length of } w \text{ is even.} \\ 0 & \text{ otherwise.} \end{cases}$$ is Turing computable. Hint: Every regular language is Turing decidable.

We finished by describing how this function (which comes up in the Collatz-Conjecture) is Turing computable: $$f(n) = \begin{cases} n/2 & \text{ if } n \text{ is even,} \\ 3n+1 & \text{ if } n \text{ is odd.} \end{cases}$$

Wed, Mar 19

Today we looked at multi-tape Turing machines.

Proof idea. For every tape symbol of the k-tape TM, we need a “dotted” symbol and we also need a special separator symbol (#). Then we can put the contents of the k tapes onto a single tape if we add separators and dotted symbols to mark the which symbols are currently pointed to by the TM.

For each step of the k-tape TM, the 1-tape TM follows these rules:

• Starting from the left, it reads the dotted symbols for each of the k-substrings. Then it returns to the leftmost position.

• Then it makes a 2nd pass, updating the contents at each dotted symbol, and then moving the dot to the left or right.

• If it reaches the end of a substring but needs to add a character, it first prints a special-blank then shifts every other character to the right by one, before returning to the special-blank and proceeding.

Another variation on a standard TM is a nondeterministic Turing machine (NTM). At each step, these can split into more than one possible next state. The transition function has form: $$\delta: Q \times \Gamma \rightarrow 2^{Q \times \Gamma \times \{L, R \}}.$$ The nondeterministic TM accepts a language as soon as any of its parallel versions reaches an accept state.

We talked about how you can use a 3-tape TM to used a breadth first search through the branching possibilities of a NTM to see if any accept.

We also talked about other things that a TM can do:

1. If $f: \Sigma^* \rightarrow \{0,1\}$, and $g, h: \Sigma^* \rightarrow \Sigma^*$ are Turing computable, then so is the function

   IF f(x) THEN g(x) ELSE h(x).

2. What about a while-loop?

   while(f(x)):
       x = g(x)

We didn’t have time for this last example:

3. Can a Turing machine have a for-loop, where it repeats some function $n$ times? Something like this Python example where function $f$ is applied $n$ times?

   for i in range(n): 
       x = f(x)

Fri, Mar 21

We started with this example:

1. Suppose that $f: \Sigma^* \rightarrow \Sigma^*$ is a Turing computable function. Describe a 2-tape TM that inputs a string $x \in \Sigma^*$ on one tape and a number $n$ (encoded with $n$ 1’s) on the second tape, that computes $$f^{k}(x) := \underbrace{f(f(\cdots f(}_{k\text{-times}}x)))).$$

In mathematics, there are many algorithms, which are step-by-step procedures that can be carried out to solve problems. Prior to the work of Turing and other computer scientists, no one ever tried to define exactly what an algorithm is. It turns out to be hard to give a precise definition of an algorithm. Computer scientists have settled on the following:

The idea is that Turing machines can do all of the things (like looping, and conditionals, storing variables) that we think of algorithms as doing, so we use TMs to give a precise definition for algorithms.

There are many other models of computing that can be proven to be Turing complete, that is, they can compute the same functions as Turing machines. But it is believed that there is no effective method of computation that can solve problems that Turing machines cannot solve.

We finished by discussing Hilbert’s 10th problem: Is there an algorithm to determine whether or not a multivariable polynomial with integer coefficients has an integer root? We looked at some example polynomials like

$$p(x,y) = 3x^2 - 2xy + y^2 - 2$$ and $$q(x,y) = x^2 + y^2 + 1.$$ The pair $(1,1)$ is a root for the first polynomial, since $p(1,1) = 0$, but the second polynomial has no integer roots.

2. Describe an algorithm that we could implement using a TM or computer program to try to find out if a polynomial has a root.

The algorithm we described will accept any polynomial that has a root. But it doesn’t reject polynomials that don’t, instead it loops forever looking for a root. It wasn’t until 1970 that Hilbert’s 10th problem was solved, when it was proved that there is no Turing machine that can decide the language of integer multivariable polynomials with integer roots. We’ll look at other examples of undecidable languages after the midterm.

Week 10 Notes

Mon, Mar 24

Today we reviewed context-free languages for the midterm exam. We also talked about the Chomsky hierarchy of languages.

Fri, Mar 28

Today we introduced universal Turing machines. We used them to consider this language:

$$\text{Accept} = \{ \langle M, w \rangle : M \text{ is a Turing machine and } w \text{ is a string that } M \text{ accepts}\}.$$

1. Explain why Accept is Turing recognizable.

Then we gave a diagonalization proof that Accept is not Turing decidable. Suppose there was a decider for Accept. Then we could make a table with rows for each Turing machine $M_i$ and columns every Turing machine encoding $\langle M_j\rangle$ and entries 1 or 0 depending on whether $M_i$ accepts $\langle M_j \rangle$.

2. What would happen if we created a TM $N$ inputs any TM encoding $\langle M \rangle$ and then does the opposite of what $D$ does on $\langle M, \langle M \rangle \rangle$. What would $N$ do when you input $\langle N \rangle$ into $N$?

3. Why is that a contradiction?

We finished by observed that there are only a countably infinite number of possible Turing machines, but there is an uncountable infinite number of languages, so there must be lots of languages that are not decidable!

Week 11 Notes

Mon, Mar 31

We started by explaining why our proof from last time that the language Accept is undecidable was a diagonalization argument. Suppose there were a Turing machine $D$ (call it a decider) that can decide whether or not any other TM will accept any string.
$$D(\langle M, w \rangle) = \begin{cases} 1 & \text{ if }M \text{ accepts } w. \\ 0 & \text{otherwise}. \end{cases}$$

Imagine we make a table with columns corresponding to different Turing machine encodings and rows corresponding to different Turing machines showing the output of $D$ on each pair.

But what happens if we create a new TM $N$ that always returns the opposite of $D$? Why is there a contradiction if we try to look up the diagonal entry where $N$ is given itself and its encoding string as inputs?

By proving that no TM can decide the language Accept, we get the following corollary about the halting problem.

We gave a proof by contradiction for this theorem.

• Question. Suppose we had a Turing machine $H$ that can decide the halting problem. Describe a clever algorithm we could use with $H$ to determine whether any other Turing machine $M$ accepts any string $w$. Why would that algorithm lead to a contradiction?

It turns out that not only is the halting problem undecidable, but lots of other questions about Turing machines are undecidable. A powerful theorem known as Rice’s theorem says that every nontrivial semantic property of a Turing machine is undecidable.

Fix an encoding method and let $L_{TM}$ be the set of all strings that are encoded Turing machines, i.e., $$L_{TM} = \{ \langle M \rangle : M \text{ is a Turing machine} \}.$$ For any Turing machine $M$, let $$L(M) = \{w \in \Sigma^* : M \text{ accepts } w \}.$$

Here are some examples of properties. For each example, determine whether it is a syntactic or semantic property.

1. $\text{INFINITE} = \{\langle M \rangle : L(M) \text{ is infinite} \}.$
2. $\text{REGULAR} = \{\langle M \rangle : L(M) \text{ is a regular language} \}.$
3. $\text{HAS-THREE-STATES} = \{\langle M \rangle : M \text{ has 3 states} \}.$

We proved Rice’s theorem using a proof by contradiction (see below). Our book also has a different proof in Section 5.3 if you are interested.

Proof. Suppose $M_1$ is a Turing machine with property $P$ and $M_2$ is a Turing machine that doesn’t have $P$. We can assume without loss of generality that $L(M_2) = \varnothing$. Then for any Turing machine $M$ and string $w$, construct a new Turing machine $T_{Mw}$ that starts by running $M$ on $w$ until that halts, then it runs $M_1$ on the actual input, returning whatever $M_1$ returns. So $$L(T_{Mw}) = \begin{cases} L(M_1) & \text{ if } M \text{ halts on } w \\ L(M_2) = \varnothing & \text{ if } M \text{ doesn't halt on } w. \end{cases}$$ Therefore $T_{Mw}$ has property $P$ if and only if $M$ halts on $w$.

• Question. Why would this lead to a contradiction if there were a Turing machine that could decide $P$?

Wed, Apr 2

Today we introduced big-O notation and used it to talk about running times of algorithms.

Note that there are lots of important examples in Barak Chapter 12 of algorithms and their running times.

• Question. Which is true? $(\log n)^3 \in O(n)$ or $n \in (\log n)^3$?

We proved the following facts about big-O notation:

• Question. Does the base of an exponential function matter in O-notation? What about for logarithms?

We get this hierarchy of functions:

$$\underbrace{\text{logarithms}}_{\text{base doesn't matter}} \ll \underbrace{\text{polynomials}}_{\text{dominant power matters}} \ll \underbrace{\text{exponentials}}_{\text{base matters}} \ll \text{factorials}$$

We used these ideas to find the dominant term for these expressions:

1. $n^4 + n^3 \log n + (\log n)^5$.

2. $n^{100} + 2^n$.

So why do we use big-O notation? It makes it easier to talk about a lot of formulas. For example, an algorithm that requires $7(n+3) \dfrac{n!}{k!(n-k)!}+167$ steps can be described simply as being $O(n^{k+1})$.

Caution 1. Big-O notation only gives an upper bound for how fast functions grow. Functions in $O(f)$ don’t have to grow at the same rate as $f$, they can also grow much slower.

Caution 2. You should always write the simplest possible expression inside big-O notation. For example $O(5n^3 + \log n) = O(n^3)$, so just write $O(n^3)$.

We finished by talking about how we use big-O notation to describe the runtime of algorithms. We did this example:

• Question. We (previously) described a very simple Turing machine algorithm for deciding if a string is in $L = \{ a^n b^n : n \in \mathbb{N}\}$. Estimate the worst-case number of steps it will take to decide if a string with $n$-characters is in $L$ with this algorithm. Use big-O notation to express the answer.

Week 12 Notes

Week 13 Notes

Week 14 Notes