← All notes

Automata Theory

Contents
  1. Overview
  2. Chomsky Hierarchy
  3. Regular Expressions
  4. Representation of Push-Down Automata
  5. Non-determinism
  6. Non-determinism
  7. Properties of Languages
  8. Regular Expressions
  9. RE ≡\equiv≡ NFA-ϵ\epsilonϵ
  10. Decision Properties
  11. Pumping Lemma
  12. NFA ≡\equiv≡ DFA
  13. DFA Minimization
  14. Context-Free Grammar
  15. Grammars
  16. Push Down Automatons
  17. Simplifying grammars
  18. Pumping Lemma for CFG
  19. Ogden’s Lemma
  20. Closure properties
  21. Pushdown Automata
  22. Greibach Normal Form
  23. Equivalence of PDA and CFG
  24. Ogden’s Lemma revisited
  25. Closure properties of CFLs
  26. Decision properties of CFLs
  27. Additional closure properties of CFLs
  28. CYK algorithm
  29. Satan-Cantor Game
  30. Enumerability in Languages
  31. Turing Machines
  32. Definitions from set theory
  33. Dovetailing
  34. Cantor’s diagonalization
  35. Turing Machines (2)
  36. Type-0 Grammars
  37. Recursive Function Theory
  38. Limitations of primitive recursion
  39. Partial Recursive functions
  40. Equational Logic
  41. Term-rewriting
  42. Encoding Turing machines
  43. Variants of TM
  44. Universal Turing Machine
  45. Undecidability
  46. Reduction Technique
  47. Post Correspondence Problem
  48. Properties of Recursive Languages
  49. NP-Completeness

Overview

Theory of Computation discusses what can and cannot be done with computers. Moreover, how "hard" or "easy" a given problem is. For instance, consider the problem of determining whether a given multivariate polynomial with integer coefficients has integer roots. This problem is undecidable - we cannot write a deterministic algorithm which halts in finite time that always gives the correct answer for a given polynomial. Through the course, we will explore various techniques and theorems through the course to answer questions like these.

Example. Given a language L1={anbm:n,m≥0}L_1 = \{a^nb^m: n,m \geq 0\}, decide whether a word is present in this language or not. We will see that such a language can be written using a DFA.

Example. Suppose we have L2={anbn:n≥0}L_2 = \{a^nb^n: n \geq 0\}. Can we construct a DFA for the same?

It can be shown that such a language cannot be represented using a DFA. Instead, we use an instrument known as pushdown automaton.

A pushdown automaton has a stack associated with a DFA. Every transition in the automaton describes an operation such as "push" and "pop" on the stack. A string is accepted by the automaton if the stack is empty at the end of the string. The languages accepted by such automatons are known as context-free grammar.

Example. Extending the previous example, consider the language L3={anbncn:n≥0}L_3 = \{a^nb^nc^n:n \geq 0\}. Turns out, a pushdown automaton cannot represent this language.

We have a Turing machine that represents the ultimate computer that can perform any computation (not all). This machine has a 'tape' associated with it along with different decisions at each section of the tape. The languages associated with these machines are known as unrestricted grammar.

These machines and the associated languages can be represented using a diagram known as Chomsky hierarchy. We will also prove that adding non-determinism affects the expressive power of PDAs but not of DFAs and TMs.

Definition. A finite state automaton is defined as a tuple (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F), where

  • QQ is a finite non-empty set of states,
  • Σ\Sigma is the alphabet with a set of symbols,
  • δ:Q×δ→Q\delta: Q \times \delta \to Q is the state-transition function,
  • q0∈Qq_0 \in Q is the initial state, and
  • F⊆QF \subseteq Q is the set of accepting states.

A language LL is a subset of strings over Σ\Sigma, whereas Σ∗\Sigma^* represents the set of all possible strings that can be constructed with the alphabet. The ∗* operator is known as Kleene-star operator representing 00 or more repetitions of symbols from an alphabet.

Is the set Σ∗\Sigma^* countable?

Example. Let us consider the language L2={anbn:n≥0}L_2 = \{a^nb^n:n\geq 0\} we saw before. How do we write the context-free grammar for this language? We write a set of base cases and inductive rules as follows -

S→ϵS→aSb\begin{align} S &\to \epsilon \\ S &\to aSb \end{align}
Typically, we use $$S \to \epsilon$$ as the base case. We start out with the string $$S$$, and then use the above rules to keep replacing the $$S$$ until we obtain a string consisting only of *terminals*. Here, the symbols $$a, b,$$ and $$\epsilon$$ are terminals whereas $$S$$ is a non-terminal.

Example. Consider the grammar of matched parentheses. This is given by -

S→()S→(S)S→SS\begin{align} S &\to ()\\ S &\to (S)\\ S &\to SS \end{align}
***Definition.*** A *context-free grammar* is defined as a tuple $$(V, \Sigma, R, S)$$, where
  • VV is a set of non-terminals or variables,
  • Σ\Sigma is the alphabet,
  • R:V→(V∪Σ)∗R: V \to (V \cup \Sigma)^* is the finite set of rules, and
  • S∈VS \in V is the start symbol.

The language of a given grammar is the set of all strings derivable using the rules.

Example. Consider the language {anbncn:n>0}\{a^nb^nc^n: n > 0\}. This can be represented by the unrestricted grammar as -

S→abcS→aAbcAb→bAAc→BbccbB→BbaB→aaaB→aaA\begin{align} S &\to abc \\ S &\to aAbc \\ Ab &\to bA \\ Ac &\to Bbcc \\ bB &\to Bb \\ aB &\to aa \\ aB &\to aaA \end{align}
These set of rules are very similar to CFG except for the fact that, now, we have strings on the LHS too. Notice how $$A, B$$ are used to convey information across the string when new $$a$$'s or $$b$$'s are added.

Homework. Write the unrestricted grammar rules for the language L={an2:n∈Z+}L = \{a^{n^2} : n \in \mathbb Z^+\}

Definition. An unrestricted grammar is defined as a tuple (V,Σ,R,S)(V, \Sigma, R, S), where

  • VV is a set of non-terminals or variables,
  • Σ\Sigma is the alphabet,
  • R:(V∪Σ)∗→(V∪Σ)∗R: (V \cup \Sigma)^* \to (V \cup \Sigma)^* is the finite set of rules, and
  • S∈VS \in V is the start symbol.

Definition. Regular expressions are defined by the following set of rules -

  1. ϕ,{ϵ},{a}\phi, \{\epsilon\}, \{a\} (for any a∈Σa \in \Sigma) are regular expressions.

  2. If E1,E2E_1, E_2 are regular expressions,

    1. E1+E2E_1 + E_2 (union),
    2. E1E2E_1E_2 (concatenation)
    3. E1∗E_1^* (Kleene star), and
    4. (E1)(E_1) (parenthesis)

    are all regular expressions.

Example. Consider L={strings with even number of a’s}L = \{\text{strings with even number of a's}\}. This can be represented using the regular expression b∗(ab∗ab∗)∗b^*(ab^*ab^*)^*.

Homework. Suppose LL is restricted to have only an odd number of bb's. How do we write the regular expression for this language?

In general, PDAs are represented as a Finite State Machine. That is, we have an action associated with each transition. An empty stack is denoted using the symbol Z0Z_0. That is, the stack begins with a single symbol Z0Z_0. Each transition is represented as l,Al, A, where ll is a letter and AA is an action such as

  • X∣aXX \vert aX - push
  • aX∣XaX \vert X - pop
  • W∣WaW\vert Wa - not sure what this is

Now, a string is rejected by the FSM in two scenarios -

  1. There is no transition defined at the current state for the current symbol in the string, and
  2. The stack is not empty, i.e. popping the stack does not yield Z0Z_0 at the end of the string input.

Chomsky Hierarchy

image-20220106090455841

Regular Expressions

We define these languages using a base case and an inductive rule. Empty string is not the same as the empty set. The base case to be considered is L={ϵ}L = \{\epsilon\}?

Inductive Rules

Lemma. If E1,E2E_1, E_2 are regular expressions, then so are

  • E1+E2E_1 + E_2 - Union
  • E1.E2E_1.E_2 - Concatenation
  • E1∗E_1^* - Kleene star
  • (E1)(E_1) - Parentheses

"Nothing else" is a regular expression. That is, we must use the four rules mentioned above to construct a regular expression.

The fourth rule can be used as follows - L((ab)∗)={ϵ,ab,abab,ababab,...}L((ab)^*) = \{\epsilon, ab, abab, ababab, ...\}. The parentheses help us group letters from the alphabet to define the language.

Example. Construct a language with only even number of a's'. Good strings include {aba,baabaa}\{aba, baabaa\}, and bad strings include {abb,bbabaa}\{abb, bbabaa\}.

The automata can be easily drawn as -

image-20220106085034344

How do we write a regular expression for this? Consider the expression R=(ab∗ab∗)∗R = (ab^*ab^*)^*. However this expression does not include strings that start with bb.

Homework. Try and fix this expression -

R=b∗.(ab∗ab∗)∗R = b^*.(ab^*ab^*)^*

Example. Construct an expression for defining the language L={all strings with even number of a’sand odd number of b’s}L = \{\text{all strings with even number of a's} \text{and odd number of b's}\}

The following automaton would work for this language -

image-20220106085649521

Homework. Find a regular expression for the above language.

Example. What language does the regular expression b∗ab∗(ab∗ab∗)∗b^*ab^*(ab^*ab^*)^*?

It represents the language with an odd number of aa's. How do we check this? Start with the base cases - It has ϵ\epsilon, and it also has {ab,ba}\{ab, ba\}. Try to check the pattern and use induction.

We will soon learn how to derive relations such as "Is L=ϕL = \phi?", "Is ∥L∥=∞\|L\| = \infty?", "Is L1⊂L2L_1 \subset L_2?"... All we are doing right now is exploring all the topics in the course using a BFS approach.

Representation of Push-Down Automata

The bottom of the stack contains a special character that indicates the bottom of the stack. We design a Finite State Machine which knows the special characters (for bottom of the stack or other purposes) and also the top element in the stack. This FSM can pop or push on the stack to go to the next state.

Example. Represent L={anbn}L = \{a^nb^n\} using a FSM.

image-20220106091221465

This is how a FSM is represented. A string is accepted iff the stack is empty. Note the transition from q0q_0 to q1q_1. It says that the top of the stack must be aa. In case it isn't the case, the string is rejected.

In a FSM, the string is rejected due to one of the two reasons -

  • No transition for the given input symbol or we reach the top stack symbol (in the case of finite length languages)
  • Input is over, and the stack is not empty.

Example. Try the same for L={equal #a′s and b′s}L = \{\text{equal \#}a's \text{ and } b's\}.

image-20220106092231128

Does this work?

Non-determinism

Example. Represent L={wwR∣w∈(a+b)∗}L = \{ww^R \mid w \in (a + b)^*\}. Here, "R" represents reverse. That is, this language is the language of palindromes. Here, we keep pushing and then we keep popping after a decision point. The decision point is a non-deterministic guess. If there is a correct guess, then the algorithm will work.

Example. Is nn composite? How do we design a non-deterministic algorithm for this problem?

  1. Guess for a factor p<np < n
  2. Check if pp divides nn. If the answer is "yes" then it is composite, else repeat.

How do we reject empty strings in PDA?

Does adding accepting states in the FSM increase the representation power? Does using the special symbol in between the stack increase the representation power?

The reference textbook for this course is "Hopcroft Ullman Motwani."

Homework. Find the number of binary strings of length 10 with no two consecutive 1's.

Answer. ff considers bit strings starting with 00 and gg considers bit strings starting with 11.

>>f(1)=1;f(2)=2;>g(1)=1;g(2)=1>f(n)=f(n−1)+g(n−1);>g(n)=f(n−1);>>> \begin{align} > f(1) &= 1; f(2) = 2; \\ > g(1) &= 1; g(2) = 1 \\ > f(n) &= f(n - 1) + g(n - 1); \\ > g(n) &= f(n - 1); > \end{align} >
>f:{1,2,3,5,8,… }>g:{1,1,2,3,5,… }>> f: \{1, 2, 3, 5, 8, \dots\} \\ > g: \{1, 1, 2, 3, 5, \dots \} >

Therefore, there are 144144 such required strings.

Example. How do we construct an automata which captures the language of binary strings with no two consecutive 1's? We use something known as a trap state. All the bad strings will be trapped in that state, and no transition from the trap state will lead to a final state. Consider the following automaton.

image-20220111114750638

Here, the 3rd state is the trap state.

Extended transition function

δ^:Q×Σ∗→2Q\hat \delta : Q \times\Sigma^* \to 2^Q is defined as

δ^(S,aW)={δ(S,a)w=ϵδ^(δ(S,a),W)otherwise\hat \delta(S, aW) = \begin{cases} \delta(S, a) & w = \epsilon \\ \hat \delta(\delta(S, a), W) & \text{otherwise} \end{cases}

For the sake of convenience we drop the hat and use δ\delta for the extended function (polymorphism).

Homework. Read the proof for showing the equivalence of language sets in DFA.

Non-determinism

Non-determinism basically refers to the procedures where we get the same output from the same input through multiple runs. In don’t care non-determinism, we get the same output with different algorithms/procedures. However, in don’t know non-determinism, a single stochastic algorithm goes through many runs (scenarios) to get the answer.

A deterministic automaton has a single choice of transition from a given state for a given symbol from the alphabet. However, in the case of a non-deterministic automata, such guarantee does not exist. The next state for a given symbol from a given state of the NFA is a set of states rather than a single state. There are two types of NFA as discussed previously.

  • Don't know NFA - Guess the right choice
  • Don't care NFA - All choices give the same result

One might ponder if NFAs are more expressive than DFAs. The answer is surprisingly no. Non-determinism can be introduced to an automaton in two ways -

  • Choice of subset of states for each transition
  • ϵ\epsilon-transitions

Example. Construct an automaton to represent the language L={abc}∪{all strings ending in b}L = \{abc\} \cup \{\text{all strings ending in b}\} whose alphabet is {a,b,c}\{a,b,c\}

image-20220113085632353

Note. We have introduced ϵ\epsilon-transitions in this automaton.

As we shall see later in the course, the three models - DFA, NFA, and NFA with ϵ\epsilon-transitions; are all equivalent in terms of expressive power.

Properties of Languages

We mainly check two properties of languages - decision and closure.

  • Decision - Is w∈Lw \in L? (Membership Problem) - decidable for regular languages.

    Decidable problems - Problems for which we can write a sound algorithm which halts in finite time.

    We can also consider problems like - Given DFA(M1)DFA(M_1) and DFA(M2)DFA(M_2), Is L(M1)=L(M2)L(M_1) = L(M_2)? or L(M1)⊂L(M2)L(M_1) \subset L(M_2)?

    Is L=ϕL = \phi? Is LL finite? Is LL finite and has an even number of strings? We can also ask questions about the DFA - Can L(M)L(M) be accepted by a DFA with k<nk < n states (minimalism)?

    Example. Can we build a DFA whose language is L={bit strings divisible by 7}L = \{\text{bit strings divisible by } 7\} with less than 7 states? Turns out, the answer is no.

    Finally, we can ask a very difficult question such as - Show LL cannot be accepted by any DFA. The technique for solving such a question is known as the Pumping Lemma. This lemma is based on the Pigeonhole principle.

  • Closure - closure using Union, Intersection, Kleene Star, and Concatenation. The question we ask is if L1,L2L_1, L_2 belong to class CC, then does L1 op L2L_1 \texttt { op } L_2 belong to CC?

We plan to show the equivalence of the following models -

  • DFAs
  • NFAs
  • NFA-ϵ\epsilon
  • Regular Expressions

Homework. Draw a DFA for the language L1∪L2L_1 \cup L_2 where L1L_1 is aa followed by even number of bbs and L2L_2 is aa followed by odd number of ccs.

Regular Expressions

They are defined using base cases and inductive cases. Before we discuss this, we define closed-world assumption. It is the presumption that a statement that is true is also known to be true. Therefore, conversely, what is not currently known to be true, is false. More info regarding this topic can be found here. The base cases for regular expressions are given as follows.

L(a)={a}L(ϵ)={ϵ}L(ϕ)=ϕ (An empty set)\begin{align} L(a) &= \{a\} \\ L(\epsilon) &= \{\epsilon\} \\ L(\phi) &= \phi \text{ (An empty set)} \end{align}

The inductive cases are

L1,L2→L1∪L2L1,L2→{uv∣u∈L1,v∈L2}L→L1∗\begin{align} L_1, L_2 &\to L_1 \cup L_2 \\ L_1, L_2 &\to \{uv \vert u \in L_1, v \in L_2\} \\ L &\to L_1^* \end{align}

RE ≡\equiv NFA-ϵ\epsilon

To begin with, we convert the base cases of regular expressions to NFA-ϵ\epsilons. Here are the automatons

image-20220131011047071

Now, for the inductive cases -

  • For union of L1L_1 and L2L_2, consider the NFAs of both languages. Create a new start state ss and final state ff. Connect ss to the start states of both NFAs with ϵ\epsilon transitions and the final states of both NFAs to ff with the same transitions.

    How do we prove that this construction represents the union?

  • For concatenation of L1L_1 and L2L_2, connect all the final states of L1L_1’s NFA to all the start states of L2L_2’s NFA using ϵ\epsilon transitions.

  • For L∗L^*, connect all the final states of the NFA to the start states of the NFA using ϵ\epsilon transitions. However, this does not accept ϵ\epsilon. Fix it. Think.

Decision Properties

Membership Problem

Does w∈Lw \in L? How do we show that this problem is decidable? The algorithm is well-known.

Emptiness Problem

Is L(M)=ϕL(M) = \phi? This problem can be solved using reachability in graphs. One can check if the final states are reachable from the start state. It can be achieved using fixed point. This method is essentially propagating the frontier from the start state. We add neighbors of all the states in the current frontier and keep expanding it. We do this until our frontier does not change. This frontier is the fixed point.

Infiniteness Problem

Is L(M)L(M) finite? We need to search for a loop in the graph to answer this question. Suppose our DFA has NN states. If the DFA accepts a string whose length is greater than or equal to NN, then a state has to repeat while forming this string. This observation is a result of the Pigeonhole principle.

This check is both necessary and sufficient. If a language is infinite, then it means that it has a string of length greater than NN. How are we going to use this property to check the infiniteness of the language? Is there a decidable algorithm?

Claim. If there is a string of length ≥N\geq N in LL, then there is a string of length between NN and 2N−12N - 1. Think about the proof. Clue. You can use at the most N−1N - 1 self loops.

It is sufficient to test for the membership of all strings of length between NN and 2N−12N - 1.

Pumping Lemma

Problem. Show that L={anbn}L = \{a^nb^n\} is not regular.

We use proof by contradiction. Assume that a DFA(M)DFA(M) with NN states accepts LL.

Theorem. Pumping Lemma. For every regular language LL, there exists an integer nn , called the pumping length, where every string w∈L w \in L of length ≥n\geq n can be written as w=xyzw = xyz where

∣xy∣≤n∣y∣>0∀i≥0, x(y)iz∈L\begin{align} \vert xy \vert &\leq n \\ \vert y\vert &> 0\\ \forall i \geq 0,\ & x(y)^iz \in L \end{align}

Let us understand this by proving L={anbn∣n>0}L = \{a^nb^n \vert n > 0\} is not regular using contradiction. Assume there is a DFA(M)DFA(M) with NN states that accepts LL.

Now, consider w=aNbNw = a^Nb^N. Since ∣xy∣≤N\vert xy \vert \leq N, write x=ajx = a^j and y=aky = a^k with j≥0j \geq 0, k≥1k \geq 1, and j+k≤Nj + k \leq N. Pumping down with i=0i = 0 gives aN−kbN∉La^{N-k}b^N \notin L, contradicting the pumping lemma.

Homework. Prove that the language with equal number of aa‘s and bb’s is not regular.

The idea is to use closure properties.

Homework. Prove the pumping lemma.

Answer. Consider a DFA(Q,Σ,Q0,δ,F)(Q, \Sigma, Q_0, \delta, F) with NN states, and a word ww such that ∣w∣=T≥N\vert w \vert = T \geq N belongs to LL. Now, let (Si)i=0T(S_i)_{i =0}^T (0 - indexed) be the sequence of states traversed by ww. The state STS_T is an accepting state as w∈Lw \in L. Also, there exist 0≤i<j≤N0 \leq i < j \leq N such that Si=SjS_i = S_j as there are only NN states in the DFA (Pigeonhole principle). Now, define the string formed by S0,…,SiS_0, \dots, S_i as xx, the one formed by Si,…,SjS_i, \dots, S_j as y, and that formed by Sj,…,STS_j, \dots, S_T as zz. We have w=xyzw = xyz. Also, ∣y∣>0\vert y \vert > 0 as i<ji < j and ∣xy∣≤N\vert xy \vert \leq N as j≤Nj \leq N.

Since Si=SjS_i = S_j, we can pump the string yy as many times as we wish by traversing cycle Si,…,SjS_i, \dots, S_j. Now, since ST∈FS_T \in F, the string formed by the sequence S0,…,{Si,…,Sj}t,…,STS_0, \dots, \{S_i, \dots, S_j\}^t, \dots, S_T (t≥0t \geq 0) also belongs to LL. This word is equivalent to xytzxy^tz. ■\blacksquare

NFA ≡\equiv DFA

We convert a NFA to DFA using subset construction. That is, if QQ is the set of states in the NFA, then 2Q2^Q will the set of states in the DFA. Initially, we construct the start states using the subset of start states in the NFA. Then, we build the following states in the DFA by tracing all the states reached by each character in the NFA into a single subset. If any of the subset consists of a final state, then that subset state is made into a final state in the DFA.

This equivalence can also be extended to show the equivalence of NFA-ϵ\epsilon and DFADFA.

DFA Minimization

All DFAs with minimal number of states are isomorphic.

Distinguishable states

Consider a DFA (Q,Σ,Q0,δ,F)(Q, \Sigma, Q_0, \delta, F) . States qi,qj∈Qq_i,q_j \in Q are said to be distinguishable iff there exists a word w∈Σ∗w \in \Sigma^* such that δ(q1,w)∉F\delta(q_1, w) \not \in F and δ(q2,w)∈F\delta(q_2, w) \in F or vice versa.

One can merge indistinguishable states to minimize a DFA.

Context-Free Grammar

Let us try to write the grammar for the language L={aibjck∣i=j or j=k}L = \{a^ib^jc^k \vert i = j \text{ or } j = k\}. Consider the following rules

S→S1∣S2S1→aS1bC∣CS2→AbS2c∣ϵC→cC∣ϵA→aA∣ϵ\begin{align} S &\to S_1 \vert S_2 \\ S_1 &\to aS_1bC \vert C \\ S_2 &\to AbS_2c \vert \epsilon \\ C &\to cC \vert \epsilon \\ A &\to aA \vert \epsilon \end{align}

In general, union is straightforward to write in CFG due to rules like rule 1. However, there is an ambiguity in the above rules. For example, the word a3b3c3a^3b^3c^3 can be generated using different derivations. We’ll discuss this later in the course.

As we discussed before, a context free grammar GG is defined by (V,Σ,R,S)(V, \Sigma, R, S). A string is accepted by the grammar if w∈Σ∗w \in \Sigma^* and R→∗wR \xrightarrow{*} w. That is, the rules must be able to derive ww.

A one-step derivation is given by u1Au2→u1βu2u_1Au_2 \to u_1\beta u_2 if A→β∈RA \to \beta \in R and u1,u2∈(V∪Σ)∗u_1, u_2 \in (V \cup \Sigma)^*.

Consider the set of rules for defining arithmetic expressions. The language is defined over Σ={+,−,×,÷,x,y,z,… }\Sigma = \{+, -, \times, \div, x, y, z, \dots\}.

S→x∣y∣zS→S+SS→S−SS→S×SS→S÷SS→(S)\begin{align} S &\to x \vert y \vert z \\ S &\to S + S \\ S &\to S - S \\ S &\to S \times S \\ S &\to S \div S \\ S &\to (S) \end{align}

Now, for an expression such x+y×zx + y \times z, we can give a left-most derivation or a right-most derivation. A precedence order removes ambiguities in the derivation. In programming languages, a parser removes these ambiguities using some conventions.

Homework. Try and write the set of rules for the language which consists of aas and bbs such that every string has twice the number of aas as that of bbs.

Answer. We try to write the rules for equal number of a’s and b’s, and try to extend them.

>>S→ϵ>S→aSb ∣ Sab ∣ abS>S→bSa ∣ Sba ∣ baS>>> \begin{align} > S &\to \epsilon \\ > S &\to aSb \ \vert \ Sab \ \vert \ abS \\ > S &\to bSa \ \vert \ Sba \ \vert \ baS > \end{align} >

Does this work?

Note. ∣R∣\vert R \vert is finite.

We had seen the CFG for the language L={anbn}L = \{a^nb^n\}. How can one prove that the rules represent that language? That is, how do we know that the rules generate all the strings in the language and no other strings?

Consider the language we saw in the previous lecture - strings with equal number of a’s and b’s. The possible set of rules are -

S→aB ∣ bAB→b ∣ bS ∣ aBBA→a ∣ aS ∣ bAA\begin{align} S &\to aB \ \vert \ bA \\ B &\to b \ \vert \ bS \ \vert \ aBB \\ A &\to a \ \vert \ aS \ \vert \ bAA \\ \end{align}

The thinking is as follows -

  • SS generates strings with equal number of a’s and b’s. BB generates strings with one more b than a’s, and similarly for AA.
  • To write the inductive cases of SS, we consider strings starting with both a and b. Inductive cases for A,BA, B are also constructed similarly.

Another possible set of rules are -

S→aSb ∣ bSaS→ϵS→SS\begin{align} S &\to aSb \ \vert \ bSa \\ S &\to \epsilon \\ S &\to SS \\ \end{align}

These rules are the minimized set of the rules I wrote for the hw in the last lecture.

Grammars

We can write grammars in canonical forms. A grammar is said to be in Chomsky normal form if the rules are of the form

C→DE - one non-terminal replaced by 2 non-terminalsC→a - one terminal replaced by a terminal\begin{align} C \to DE &\text{ - one non-terminal replaced by 2 non-terminals} \\ C \to a &\text{ - one terminal replaced by a terminal} \end{align}

Claim. Any grammar GG (ϵ∉L(G)\epsilon \not\in L(G)) can be converted to an equivalent Chomsky Normal form.

Another canonical form of grammar is Greibach normal form. The rules are of the form

C→aα\begin{align} C &\to a\alpha \end{align}

Each non-terminal converts to a terminal followed by a symbol in (V∪Σ)∗(V \cup \Sigma)^*. Similar to the Chomsky form, every grammar can be converted to the Greibach normal form.

Push Down Automatons

Consider the language L={wcwR∣w∈(a+b)∗}L = \{wcw^R \vert w \in (a + b)^*\}.

Aside. Try writing the Chomsky normal form rules for the above language.

>>S→AA0∣BB0∣c>A0→SA>B0→SB>A→a>B→b>>> \begin{align} > S &\to AA_0 \mid BB_0 \mid c \\ > A_0 &\to SA \\ > B_0 &\to SB \\ > A &\to a \\ > B &\to b \\ > \end{align} >

The pushdown automaton for this language is given by -

image-20220131205500689

How do we take a grammar and produce the normal form of the grammar? We shall learn techniques such as eliminating useless symbols, elimination epsilon and unit productions. These will be used to get the designable form of the grammar that can also be used to show languages which are context-free using the pumping lemma.

The notation α1→nα2\alpha_1 \xrightarrow{n} \alpha_2 is used to denote that α2\alpha_2 can be derived from α1\alpha_1 in nn steps. The ∗* over the arrow represents the derivative closure of the rules.

Grammars G1,G2G_1, G_2 are equivalent iff L(G1)=L(G2)L(G_1) = L(G_2). For example, we have seen two grammars for the language L= strings with #a=#bL = \text{ strings with } \#a = \#b, and they are both equivalent.

Derivation trees

  • Trees whose all roots are labeled.
  • The root of the tree is labeled with the start symbol of the grammar SS.
  • Suppose A is the label of some internal node, then A has a children X1,…XRX_1, \dots X_R iff A→X1…XR∈RA \to X_1\dots X_R \in R.
  • ϵ\epsilon can only be the label of leaf nodes.

Derivations

Grammars with multiple derivation trees are ambiguous. Are there languages for which any grammar is ambiguous? Such languages are called as inherently ambiguous.

Homework. Find examples of inherently ambiguous grammars.

Simplifying grammars

Definition. A variable BB is productive in GG iff B→G∗wB \xrightarrow[G]{*} w for some w∈Σ∗w \in \Sigma^*.

Definition. A variable BB is reachable from the start symbol SS of GG if S→G∗αBβS \xrightarrow[G]{*} \alpha B \beta for some α,β∈(Σ∪V)∗\alpha, \beta \in (\Sigma \cup V)^*.

We useful variable XX is productive and reachable. These are necessary conditions but not sufficient. For example, consider the following grammar.

S -> AB
A -> c

Here, AA is useless even if it is productive and reachable.

Definition. A variable XX is useless if there is no derivation tree that gives w∈Σ∗w \in \Sigma^* from SS with XX as the label of some internal node.

Fixed point algorithm

The idea is to find a monotonic algorithm which gives us the set of useful symbols at the fixed point of the underlying function.

Firstly, let us try this for productive variables. We propose the following algorithm.

P0=ϕPi→Pi+1≜Pi∪{N∣N→α∈R and α∈(Σ∪Pi)∗}\begin{align} P_0 &= \phi \\ P_i &\to P_{i + 1} \\ &\triangleq P_i \cup \{N \mid N \to \alpha \in R \text{ and } \alpha \in (\Sigma \cup P_i)^* \} \end{align}

For example, consider the grammar

S -> AB | AA
A -> a
B -> bB
-- The algorithm
P_o = \phi
P_1 = {A} // Rule 2
P_2 = {A, S} // Rule 1
P_3 = {A, S}

Therefore, the symbols S,AS, A are productive in the above grammar. We propose a similar algorithm for reachable states in the grammar.

R0=ϕRi→Ri+1≜Ri∪{P∣Q→αPβ;α,β∈(Σ∪Pi)∗ and Q∈Ri}\begin{align} R_0 &= \phi \\ R_i &\to R_{i + 1} \\ &\triangleq R_i \cup \{P \mid Q \to \alpha P \beta; \alpha, \beta \in (\Sigma \cup P_i)^* \text{ and } Q \in R_i\} \end{align}

Definition. A nullable symbol is a symbol which can derive ϵ\epsilon. These symbols can be eliminated.

Definition. A unit production is a rule of the form A→BA \to B where A,B∈V A, B \in V.

We shall continue discussing simplifying grammars. As an initial step, we can get rid of symbols which are either unreachable or unproductive. However, the order in which we check productivity and reachability affects how the grammar is simplified. For example, consider the grammar

S -> a
S -> AB
A -> a

Now, if we eliminate unreachable symbols first (that is none), and then eliminate unproductive symbols (BB), we get

S -> a
A -> a

Notice that the above simplified grammar has a redundant rule. However, if we check for productivity (BB is eliminated) and then reachability (AA is unreachable), we get

S -> a

Claim. Eliminating unproductive symbols followed by unreachable symbols gives a grammar without any useless variables.

Homework. Prove the above claim.

ϵ\epsilon-productions

Suppose GG is a CFG such that L(G)L(G) has ϵ\epsilon, then L(G)−{ϵ}L(G) - \{\epsilon\} can be generated by a CFG G1G_1 which has no ϵ\epsilon-productions (rules of the form A→ϵA \to \epsilon).

Nullable symbols

AA is nullable if A→G∗ϵA \xrightarrow[G]{*} \epsilon.

How do we remove nullable symbols? We can’t just take out a rule of the form A→ϵA \to \epsilon as it may make AA unproductive. The way to go about this is to replace each rule of the form A→X1…XnA \to X_1\dots X_n to A→α1…αnA \to \alpha_1 \dots \alpha_n where

αi={XiXi is not nullableϵotherwise\alpha_ i = \begin{cases} X_i & X_i\text{ is not nullable}\\ \epsilon &\text{otherwise} \end{cases}

However, one must be cautious about replacing all the symbols by ϵ\epsilon and also about recursive rules. For instance, consider the following grammar

S→ϵ∣aSb∣bSa∣SSS \to \epsilon \mid aSb \mid bSa \mid SS

Now, SS is nullable but we can’t replace S→aSbS \to aSb by S→abS \to ab simply. We also need to have the rule S→aSbS \to aSb in place for recursion. Basically, for each rule of the form A→X1…XnA \to X_1\dots X_n, we need to have all the rules of the form A→αA \to \alpha where α\alpha spans over all subsets of X1…XnX_1 \dots X_n.

Unit Productions

To remove unit productions, let us assume that there are no ϵ\epsilon-productions and useless symbols. Now, we need to find all pairs (X,Y)(X, Y) such that X→G∗YX \xrightarrow[G]{*} Y. Once we find such pairs, we can try and eliminate the unit symbols themselves, or solely the rules.

Let us take the following grammar for L{w∣na(w)=nb(w)}L \{w \mid n_a(w) = n_b(w)\}

S→ϵ∣aSb∣bSa∣SS simplified to S→abS∣bSa∣SS∣ab∣baS \to \epsilon \mid aSb \mid bSa \mid SS \\ \text{ simplified to } \\ S \to abS \mid bSa \mid SS \mid ab \mid ba

and

S→ϵS→aB∣bAB→b∣bS∣aBBA→a∣aS∣bAA simplified by just removing S→ϵS \to \epsilon \\ S \to aB \mid bA \\ B \to b \mid bS \mid aBB \\ A \to a \mid aS \mid bAA \\ \text{ simplified by just removing } S \to \epsilon\\

To convert the grammar into Chomsky normal form, we do approximately the following - we replace each rule of the form A→X1…XnA \to X_1 \dots X_n with A→X1BA \to X_1B and B→X2…XnB \to X_2 \dots X_n. We keep repeating this until there is only a single terminal symbol on the rhs, or two non-terminals.

Consider a grammar in Chomsky form. The derivation tree will consist of nodes with either 2 children (A→BCA \to BC), 1 child (A→aA \to a) or leaf nodes.

Let the longest path in the derivation tree be kk. Then, the upper bound on the length of the word formed is 2k−12^{k - 1} and lower bound is kk. Note. The variables from VV can repeat across a path.

Pumping Lemma for CFG

For any CFL LL, the language L−{ϵ}L - \{\epsilon \} has a Chomsky Normal form grammar.

Theorem. Pumping Lemma For every CFL LL, there is a nn such that for all strings ∣z∣≥n\vert z \vert \geq n with z∈L(G)z \in L(G), there are strings u,v,w,x,yu, v, w, x, y such that z=uvwxyz = uvwxy and

  • ∣vwx∣≤n\vert vwx \vert \leq n
  • ∣vx∣≥1\vert vx \vert \geq 1
  • for all zi=uviwxiyz_i = u v^iwx^iy, i≥0i \geq 0, zi∈L(G)z_i \in L(G).

It is easy to show L={anbncn∣n≥1}L = \{a^nb^nc^n \mid n \geq 1\} is not a CFL using the above lemma.

Proof of the lemma

Let m=∣V∣m = \vert V \vert and take n=2mn = 2^m. If z∈L(G)z \in L(G) and ∣z∣≥n\vert z \vert \geq n, then its derivation tree has a path with at least m+1m + 1 variable nodes. By the pigeonhole principle, a variable repeats on this path.

Now, consider the path S,…,A,…,A,…,aS, \dots, A, \dots, A, \dots, a.

  • It is easy to the see that the word formed by the subtree below the first AA has length ≤n\leq n.
  • Also, as there are 2 AAs in the path, the number of letters in the “left” subtree and “right” subtree would be greater than 1.
  • These “left” and “right” subtrees can be derived an arbitrary number of times as AA can be derived from AA.

Note. To draw some more intuition, call the subtree formed by the first AA as T1T_1, and the subtree formed by the second AA as T2T_2. We shall label the word formed by T2T_2 as ww, and the word labeled by T1T_1 as vwxvwx. Now, ∣vx∣≥1\vert vx \vert \geq 1. Think. The “left” and “right” subtree in the above explanation together are formed by the set T1∖T2T_1 \setminus T_2.

Homework. Show that the following languages cannot be represented by CFG.

  • L={aibici∣j≥i}L = \{a^ib^ic^i \mid j \geq i\}
  • L={aibjck∣i≤i≤k}L = \{a^ib^jc^k \mid i \leq i \leq k\}
  • L={aibjcidj∣i,j≥1}L = \{a^ib^jc^id^j \mid i, j \geq 1\}

We shall see that 2 stacks PDA is the most expressive Turing machine.

Can’t there be useless symbols in normal forms? yes -> S→ABS \to AB

Ogden’s Lemma

This lemma is a generalization of pumping lemma. Consider the pumping lemma for the FSA. It basically said that some state must repeat for a string of length ≥n\geq n in the language. Ogden’s lemma talks about a similar claim for CFGs. It will be formally discussed in the next lecture.

Closure properties

The union, concatenation and Kleene closure of CFGs are also CFGs. Proof is left as a homework.

Intersection is not context-free!

Pushdown Automata

Consider the languages L1={wcwR∣w∈(0+1)∗}L_1 = \{wcw^R \mid w \in (0 + 1)^* \} and L3={wwR∣w∈(0+1)∗}L_3 = \{ww^R \mid w \in (0 + 1)^* \}. Let us build PDAs for these two models.

The stack of the PDA uses different symbols that those from Σ\Sigma. We shall denote the superset of symbols of stack by TT. Each transition in the PDA depends on the input symbol and the symbol on the top of the stack. These are similar to the FSA transition diagram. If both of these symbols are satisfied for the transition, we perform an action on the stack by pushing or popping symbols. Note that we can also choose to not perform any action.

We shall also use the symbol XX to denote ‘matching any character’ for the symbols on stack. We can also have ϵ\epsilon transitions in non-deterministic PDAs. ϵ\epsilon transitions basically denote ignoring input symbols.

Note. We can push multiple symbols in each transition but we can only pop one symbol in each transition.

The PDA for L1L_1 is given by

δ(q1,c,X)=(q2,X)δ(q1,1,X)=(q1,GX)δ(q1,0,X)=(q1,BX)δ(q2,0,B)=(q2,ϵ)δ(q2,1,G)=(q2,ϵ)δ(q2,ϵ,Z0)=(q2,ϵ)\begin{align} \delta(q_1, c, X) &= (q_2, X) \\ \delta(q_1, 1, X) &= (q_1, GX) \\ \delta(q_1, 0, X) &= (q_1, BX)\\ \delta(q_2, 0, B) &= (q_2, \epsilon) \\ \delta(q_2, 1, G) &= (q_2, \epsilon) \\ \delta(q_2, \epsilon, Z_0) &= (q_2, \epsilon) \\ \end{align}

The PDA for L3L_3 is similar but we cannot express this language without non-determinism. We can’t guess where the “middle of the string” occurs without guessing. Therefore, non-deterministic PDAs are more expressive than deterministic ones.

Remember that the non-deterministic PDA accepts a string if there is at least one run that accepts it.

Formal definition of PDA

A Pushdown automata is formally given by the 7 element tuple M⟨Q,Σ,T,δ,q0,Z0,F⟩M \lang Q, \Sigma, \Tau, \delta, q_0, Z_0, F \rang where

  • T\Tau is the set of stack symbols
  • Z0Z_0 is a special symbol denoting the bottom of the stack
  • FF is the set of final states of the automata
  • δ:Q×(Σ∪ϵ)×T→(Q,λ)\delta: Q \times (\Sigma \cup \epsilon) \times \Tau \to (Q, \lambda) where λ∈T∗\lambda \in \Tau^* is an action performed on the transition.

A string is accepted if one of the runs ends with an empty stack or at a final state. That is, L(M)={w∣(q0,w,Z0)⊢M∗(p,ϵ,ϵ)}∪{w∣(q0,w,Z0)⊢M∗(q,ϵ,λ),q∈F}L(M) = \{w \mid (q_0, w, Z_0) \vdash^*_M (p, \epsilon, \epsilon)\} \cup \{ w \mid (q_0, w, Z_0) \vdash^*_M (q, \epsilon, \lambda), q \in F\}. In the following lectures, we shall prove DPDA ≠\neq NPDA, ‘accepting by empty stack’ ≡\equiv ‘accepting by final state’ and PDA (NPDA) == CFG.

We define a move or an arrow as a transition in the PDA.

Instantaneous Description refers to the property of defining a system using a single number. In case of a PDA, the description is given by a numerical representation of (Current string, Remaining input tape, Stack content). These values, that constitute the dynamic information of a PDA, keep changing during moves. The notation ID1⊢MID2ID_1 \vdash_M ID_2 denotes a single transition in the PDA. The notation ID1⊢M∗ID2ID_1 \vdash^*_M ID_2 is a sequence of 0 or more moves.

We have seen the accept criteria in the last lecture. We will show that a PDA built on the final state accept criteria has an equivalent PDA built on the empty state accept criteria.

Greibach Normal Form

CFGs of the form A→aαA \to a\alpha.

Note. α\alpha in the above expression consists of non-terminals only!

What are the challenges involved in converting a grammar to a Greibach normal form? It involves the following steps.

Elimination of productions

Suppose we want to remove the rule A→α1Bα2A \to \alpha_1 B \alpha_2 and keep the language of the CFG same. Then, we consider all rules of the form B→βB \to \beta and replace each of them by A→α1βα2A \to \alpha_1 \beta \alpha_2. After doing this, we can delete the initial production involving AA.

Left Recursion

Suppose we have rules of the form A→Aα1∣Aα2∣⋯∣AαrA \to A\alpha_1 \mid A\alpha_2 \mid \dots \mid A\alpha_r which we wish to remove. Now, there would be other rules involving AA of the form A→β1∣⋯∣βsA \to \beta_1 \mid \dots \mid \beta_s.

Now, we define a new variable B∉VB \not\in V. Then, we write rules of the form A→β1B∣⋯∣ βsBA \to \beta_1B \mid \dots \mid \ \beta_s B and β→α1B∣⋯∣αrB \beta \to \alpha_1 B \mid \dots \mid \alpha_r B. We can then remove all the left-recursive productions of AA. Basically, we have replaced left-recursion rules with right-recursion rules.

Ordering of Variables

Simplify the variables in one order? Wasn’t taught?

Equivalence of PDA and CFG

Given any CFG GG, we convert it into Greibach normal form. Then, we choose the non-terminals as the stack symbols. The initial symbol in the grammar is taken as the top symbol of the stack initially. For each rule A→aαA \to a\alpha we write the transition δ(q,a,A)=(q’,α)\delta(q, a, A) = (q’, \alpha). We start with a single state in the DFA, and write all the rules on this state. Through this intuition, we have shown that every CFG has a corresponding PDA. Then, we need to show that every PDA has a corresponding CFG.

To show that CFG ⊆\subseteq PDA, we need to show the equivalence of a language in both directions. That is, for every string accepted by the CFG, we need to show that the PDA also accepts it and vice versa. Note that we also have to prove PDA ⊆\subseteq CFG.

Ogden’s Lemma revisited

Suppose we had to prove the language L={aibjckdl∣i=0 or j=k=l}L = \{a^ib^jc^kd^l \mid i = 0 \text{ or } j = k = l\} is not CFG. Can we do this using pumping lemma? No. Think.

We do this using Ogden’s lemma which goes something like this. You can give a z=z1…zmz = z_1 \dots z_m such that m≥nm \geq n. Now, we can mark positions by choosing a subset of ziz_i’s. Then, the vwxvwx from the pumping lemma must have at most nn marked positions and vxvx has at least one marked position. This is a stronger condition as compared to the pumping lemma.

Homework. Show that L={aibjck∣i≠j,j≠k,i≠k}L = \{a^ib^jc^k \mid i \neq j, j \neq k, i \neq k\} is not context-free using Ogden’s lemma.

Closure properties of CFLs

  • Union - L(G1)∪L(G2)L(G_1) \cup L(G_2) regular? Yes. Add a rule S→S1∣S2S \to S_1 \mid S_2.
  • Kleene closure - (L(G1))∗(L(G_1))^* regular? Yes. Add a rule S→S1S∣ϵS \to S_1S \mid \epsilon.
  • Concatenation - L(G1).L(G2)L(G_1). L(G_2) regular? Yes. Add a rule S→S1S2S \to S_1 S_2.
  • Intersection - Consider the example L1={aibicj∣i,j≥1}L_1 = \{a^ib^ic^j \mid i, j \geq 1\} and L2={aibjci∣i,j≥1}L_2 = \{a^ib^jc^i \mid i, j \geq 1\}. Both of them are context free but their intersection is not.
  • Complement - Easy to show from intersection.

Decision properties of CFLs

Is the language empty?

This is easy to check. Remove useless symbols and show that SS is useful.

Is the language finite?

Consider the Chomsky normal form of the grammar. Draw a graph corresponding to the grammar such that every node has a single edge directed to a terminal or two edges directed to non-terminals.

Claim. If the graph has a cycle, then the language formed by the grammar is infinite. This is intuitive.

We can find cycles using DFS simply.We can derive more efficient methods which is not the goal of this course.

Does a string belong to the language?

The first approach is the following. Get the Greibach form of the grammar. Now, for each letter cc in the string check whether there are rules of the form A→cαA \to c\alpha. We consider the values of all such α\alphas and continue parsing the rest of the input string. Therefore, at each letter in the string we limit the number of possible derivations. If we reach the end of the string without running out of possible derivations at each letter, then the string belongs to the language. Remember that we will start with the start symbol for the beginning of the string.

However, we can see that this method is not very efficient. We shall see the CYK algorithm which works in O(n3)\mathcal O(n^3).

Additional closure properties of CFLs

  • L(G)∩RL(G) \cap R, where RR is a regular language, is also context-free.

    How do we show that L={ww∣w∈(a+b)∗}L = \{ww \mid w \in (a + b)^*\} is not context free? It can be shown via pumping lemma which is complicated. However, it is very easy to prove it using the above property.

    How do we prove the closure property? Consider a PDA(M1)PDA(M_1) for L(G)L(G) and DFA(M2)DFA(M_2) for RR. Now, we construct a ‘product’ PDA similar to what we did in NFAs. We use the ‘final state’ accept PDA for the purpose. The final states would be F1×F2F_1 \times F_2. It is easy to see that we can get the required property.

CYK algorithm

The Cocke-Younger-Kasami algorithm can be used to check if a string ww belongs to L(G)L(G).

Suppose there is a w=w1w2…wi…wl…wnw = w_1 w_2 \dots w_i \dots w_l \dots w_n whose membership we need to check. We consider subproblems of the form: Is wij≜wi…wi+j−1w_{ij} \triangleq w_i \dots w_{i + j - 1} derivable from any non-terminal in the grammar? Then, finally, we need to answer is w1nw_{1n} can be derived from SS.

We consider the Chomsky normal form of the grammar for this algorithm. All strings of the form wj1w_{j1} can be checked easily. For each wi1w_{i1} we store all the non-terminals that can derive it. Now, the recursion for all j≥2j \geq 2 is given by

f(win)=⋃j=1n−1⋃A∈f(wij)⋃B∈f(wi(n−j)){C∣(C→AB)∈G}f(w_{in}) = \bigcup_{j = 1}^{n - 1}\bigcup_{A \in f(w_{ij})} \bigcup_{B \in f(w_{i(n - j)})} \{C \mid (C \to AB) \in G \}

See the following example using the CYK algorithm.

image-20220222011041265

It is easy to see that this algorithm takes O(n3)\mathcal O(n^3).

ϵ\epsilon closure

We define ϵ\epsilon closure for a state qq in a DFA as all the states that qq can reach via ϵ\epsilon transitions. Then, to remove all the ϵ\epsilon transitions from qq, we add a transition corresponding to all transitions from qq to each of the states in the ϵ\epsilon closure of qq. Also, if any state in the ϵ\epsilon closure of qq is final, then qq can also be made as a final state.

Note. Minimal DFAs need not be unique. They are isomorphic.

Satan-Cantor Game

The game goes like this. Satan chooses a random natural number and asks Cantor to guess the number. Cantor gets a chance to guess once on each day. If Cantor guesses the right number, then he can go to heaven. Does Cantor have a strategy that will guarantee him going to heaven? Yes, Cantor can choose numbers in the sequence 1,2,3,…1, 2, 3, \dots and eventually it is guaranteed that Cantor chooses the correct number.

Suppose, Satan changes the game by choosing a random integer. Does Cantor have a strategy then? Yes, choose numbers of the form 0,1,−1,2,−2,…0, 1, -1, 2, -2, \dots. Now, suppose Satan chooses a pair of integers, then how do we get a strategy? We can order the points based on the distance from the origin in the 2D Cartesian plane (Cantor’s pairing function). Similarly, a tuple of nn integers is also enumerable.

Can we give a set for Satan such that the elements are not enumerable? What if Satan chooses (n1,…,nk)(n_1, \dots, n_k) where kk is not known to Cantor. Can Cantor win in this case? Yes. Proof is homework.

Satan can choose the set of real numbers, and in that scenario Cantor would not be able to win. The key idea here is Cantor’s diagonalization argument.

Also, look up Kolmogorov complexity. Enumerability ≡\equiv Countability.

Enumerability in Languages

A language which is finite will be regular, and we can build an FSA for it. How about infinite languages? CFLs can represent a subset of these languages.

If we categorise the infinite languages as languages which are recursively enumerable and uncountable. Can we build models for recursively enumerable languages?

Turing Machines

Turing wanted to build a machine that could recognize any enumerable language. The inspiration is drawn from the recursive function theory developed by Alonzo Church. There are other people who developed Type-0 grammars which are similar to CFGs but the left hand side of the rules can consist of a string composed of terminals and non-terminals making it context-dependent.

Church and Turing came up with a thesis, and they proposed that Church’s theory and Turing’s machine can be used to compute any effectively computable function.

Aside. Aren’t all languages enumerable with alphabet being a finite set?

“Is L(G)L(G) empty?” is a decidable problem. However, “Is the complement of L(G)L(G) empty?” is not decidable! This property was proven by Godel.

We shall now introduce the notion of Turing machines. Instead of a stack, we have an input tape with a fixed left end. A string is written in the tape with each letter being in a cell of the tape. The machine also involves a control which is essentially a FSM that takes the input from the tape, and performs actions on it. Basically, in PDAs, we could only see the top of the stack, but here we are able to freely traverse over the tape.

Definitions from set theory

Definition. Enumerable of a set refers to the property of being able to define a one-to-one correspondence from the elements of the set to positive integers.

Definition. In computability theory, a set SS of natural numbers is called computably enumerable, recursively enumerable, semi-decidable, partially decidable, listable, provable or Turing-recognisable if

  • there is an algorithm such that the set of input numbers for which the algorithm halts is exactly SS.
  • or equivalently, there is an algorithm that enumerates the members of SS. That means that its output is simply a list of all the members of S={s1,s2,s3,… }S = \{s_1, s_2, s_3, \dots\} . If SS is infinite, this algorithm will run forever.

Dovetailing

In the Satan-Cantor game, the idea was to enumerate all possible answers “fairly”.

Let us consider the scenario where Satan chooses a kk tuple of integers where kk is unknown. How do we enumerate this set? We use dovetailing for the same. Consider the tuple (k,n)(k, n). For one such given tuple, we will enumerate all kk-tuples with distance from origin being less than nn. The idea is that we are balancing the enumeration across two dimensions, kk and nn, together.

Cantor’s diagonalization

How is the above set different from the power set of natural numbers? Let us consider the question in terms of languages. Consider a language L⊆Σ∗L \subseteq \Sigma^* with a finite Σ\Sigma. Σ∗\Sigma^* is enumerable (ϵ,a,b,c,aa,ab,ac,…\epsilon, a, b, c, aa, ab, ac, \dots). Now, is the set of all languages L\mathcal L enumerable? We know that L=2Σ∗\mathcal L = 2^{\Sigma^*}.

We shall use contradiction to show that the set is not enumerable. Consider the following table -

ϵ\epsilon aa …\dots
L1L_1 1 0
L2L_2 1 1
⋮\vdots ⋱\ddots

The table consists of all the languages (assuming they are enumerable) with the respective strings in the language tagged as 1. Define the language Lnew={wi∣wi∉Li}∀i∈NL_{new} = \{w_i \mid w_i \not \in L_i\} \forall i \in \mathcal N. We then have a contradiction that ∃Lnew\exists L_{new} such that lnew≠Lil_{new} \neq L_i for any ii.

Claim. The state of every computer can be encoded as a single number.

Turing Machines (2)

The machine can do the following things

  • Replace the symbols on the tape by symbols in TT where Σ⊆T−{B}\Sigma \subseteq T - \{B\}. BB is a blank symbol to denote an empty cell
  • Move left or right by one step
  • Go to the next state

So, the labels on the transitions of the FSM are of the form X∣Y,DX \mid Y, D where X,Y∈TX, Y \in T and D=L∣RD = L \mid R. It means that the symbol XX in the cell is replaced by the symbol YY. The machine has to definitely move left or right in each transition. A “run” starts from the first cell and the state q0q_0 in the FSM. As an example, we consider the following FSM for the language L={0n1n∣n≥1}L = \{0^n1^n \mid n \geq 1\}.

image-20220312155130493

TODO Draw the above diagram again.

In a Turing machine, we halt when there is no move possible.

Formally, a Turing machine is defined as T=(Q,Σ,T,δ,q0,B,F)T = (Q, \Sigma, T, \delta, q_0, B, F) where δ:Q×T→Q×T×{L,R}\delta: Q \times T \to Q \times T \times \{L, R\}. There are many variations possible to this machine which we shall show are equivalent to this simple definition. For example, we can have multiple tapes, output tape, non-determinism, etc.

Is countable same as enumerable? Countable implies that there is a one-to-one mapping from the elements in the set to natural numbers. This definition is equivalent to that of enumerability.

A Turing machine can enumerate a language. A language is recursively enumerable if a Turing machine can enumerate it.

Σ∗\Sigma^* is enumerable but there are languages in Σ∗\Sigma^* which are not enumerable.

The theory of Turing machines was developed in the 1930s.

Consider the derivation (q0,winp)⊢M∗(qk,x)(q_0, w_{inp}) \vdash^*_M (q_k, x) where the machine halts. A machine halts when there is no move at any given state. If qk∈Fq_k \in F and the machine MM halts, then MM accepts winpw_{inp}.

Variations of Turing Machines

  • 2-way infinite tapes
  • Multi-tape heads
  • Non-determinism
  • Output type (write only, immutable)

Let us try and build the Turing machine for L={anbncn∣n≥1}L = \{a^nb^nc^n \mid n \geq 1\}. We’ll use the following logic. In each pass, we will change 1 a, 1 b and 1 c to X, Y and Z respectively. If we have any extra a’s, b’s or c’s, then we will halt.

image-20220312183041093

The machine is given in the above diagram.

Homework. Draw a Turing machine for the language L={ww∣w∈(a+b)+}L = \{ww \mid w \in (a + b)^+\}. Hint - Think of subroutines. That is, tackle smaller problems like “Find the middle of the string”, and then match left and right.

Homework. Try L={an∣n is prime}L = \{a^n \mid n \text{ is prime}\}

Type-0 Grammars

These are also known as Unrestricted grammars. These are essentially same as CFGs but the LHS of rules can be any string. Consider the language L={anbncn∣n≥0}L = \{a^nb^nc^n\mid n \geq 0\}. The grammar can be as follows

S→ABCS∣TcCA→ACBA→ABCB→BCCTc→TccBTb→TbbATa→TaaTc→TbTb→TaTa→ϵ\begin{align} S &\to ABCS \mid T_c \\ CA &\to AC \\ BA &\to AB \\ CB &\to BC \\ CT_c &\to T_cc \\ BT_b &\to T_bb \\ AT_a &\to T_aa \\ T_c &\to T_b \\ T_b &\to T_a \\ T_a &\to \epsilon \end{align}

If one notices closely, then there are a few issues with this grammar. However, it is correct considering non-determinism. That is, a terminal string derived from this grammar will be in LL.

Homework. Write the Type-0 grammar for L={ww∣w∈(a+b)+}L = \{ww \mid w \in (a + b)^+\}

Let us go back to the L={anbncn}L = \{a^nb^nc^n\} language. How do we come up with a deterministic grammar? We use the idea of markers.

  • 1-end marker

    S→S1$S1→ABC∣ABCS1CA→ACCB→BCBA→ABC$→c,  Cc→ccBc→bc,  Bc→bbAb→ab,  Aa→aa\begin{align} S &\to S_1\text{\$} \\ S_1 &\to ABC \mid ABCS_1 \\ CA &\to AC \\ CB &\to BC \\ BA &\to AB \\ C\text{\$} &\to c ,\; Cc \to cc \\ Bc &\to bc ,\; Bc \to bb \\ Ab &\to ab ,\; Aa \to aa \\ \end{align}

    The problem with the above grammar is obvious. This issue is often prevented using priority rules in hierarchical grammars. Another fix for this is, adding the following set of rules

    Ca→aC,  ca→acCb→bC,  cb→bcBa→aB,  ba→ab\begin{align} Ca &\to aC ,\; ca \to ac\\ Cb &\to bC ,\; cb \to bc\\ Ba &\to aB ,\; ba \to ab \end{align}

    Check if this is correct

  • 2-end marker

TM as a recogniser

Are the set of moves on a TM a decision procedure? A decision procedure refers to a procedure that outputs yes or no for a given input. It involves correctness and termination. No, TM does not do that. For example, consider never halting TMs. Therefore, TM is a semi-decision procedure. In order to classify TM as a decision procedure, we need to show that it halts on every input. Also, we need to show that it gives the correct answer.

TM as a “computer”

Can TM replicate any function of the form y=f(X1,…,Xn)y = f(X_1, \dots, X_n) where the arguments belong to $\mathbb N$. Yes, it can be done. What should a Turing machine do when we give invalid arguments to partial functions? It should never halt. On total functions, the TM must always halt and give the correct answer. For example, we have the following TM for f(x,y)=max(0,x−y)f(x, y) = max(0, x - y). Numbers xx and yy are written consecutively on the tape in unary form separated by a 11.

image-20220328173509367

If the TM has to halt when w∉Lw \not \in L, then we shall see that this set of TMs will only recognise recursively enumerable languages. For TMs to accept all the enumerable languages, we must allow the TM to not halt for certain inputs.

TM as an enumerator

Such TMs do not take any input. It continuously writes input on the tape and never halts. The TM prints a sequence that looks like the following w1#w2#…w_1 \# w_2 \# \dots for each wi∈Lw_i \in L. The machine halts if LL is finite, but doesn’t otherwise. LL is recursively enumerable iff a TM can enumerate the language.

Semi-Decision Procedure - Given M1M_1 for LL as an enumerator, construct M2M_2 as a recogniser for LL. In M2M_2, we can just check if the given input is present in the list of words printed by M1M_1. Now, we have come up with a semi-decision procedure based on an enumerator.

Our goal is to determine if there are any functions that cannot be computed by TMs. Or rather, are there any languages that TM cannot enumerate or recognise. Enumeration and Recognition are equivalent (hint: dovetailing).

Recursive Function Theory

Let N={0,1,… }N = \{0, 1, \dots\}. Any function we consider will be of the form f:Nk→Nf: N^k \to N. How do we define these functions? We start with base cases and recursion. To define these functions, we shall define some basic functions that will be used to define the others.

  • Constant function - Cnk(x1,…,xk)=nC^k_n(x_1, \dots, x_k) = n for all x1,…,xk∈Nx_1, \dots, x_k \in N.
  • Successor functions - S(x)=x+1S(x) = x + 1.
  • Projection function - Pik(x1,…,xi,…,xk)=xiP^k_i(x_1, \dots, x_i, \dots, x_k) = x_i for 1≤i≤k1 \leq i \leq k.

We move on to more primitive recursive functions.

  • Composition - f(x1,…,xk)=h(g1(x1,…,xk),…,gm(x1,…,xk))f(x_1, \dots, x_k) = h(g_1(x_1, \dots, x_k), \dots, g_m(x_1, \dots, x_k))

Primitive recursion is given by

  • Basecase - f(0,x1,…,xk)=g(x1,…,xk)f(0, x_1, \dots, x_k) = g(x_1, \dots, x_k)
  • Recursion - f(S(y),x1,… )=h(y,f(y,x1,…,xk),x1,…,xk)f(S(y), x_1, \dots) = h(y, f(y, x_1, \dots, x_k), x_1, \dots, x_k)

For example, the formal definition of ++ is given by

+(0,x)=P11(x)+(S(y),x)=h(y,+(y,x),x)h(y,+(y,x),x)=S(+(y,x))\begin{align} +(0, x) &= P^1_1(x) \\ +(S(y), x) &=h(y, +(y, x), x) \\ h(y, +(y, x), x) &= S(+(y, x)) \end{align}

There are functions which are not primitive recursive.

We shall see that primitive recursion is not expressive enough, Adding “minimization” to our set of rules will help us define any total function. We shall also see Equational Programming that is Turing-complete.

As we have seen earlier, we are using 3 base functions - constant, successor, and projection. Composition is depicted as f=h∘(g1,…,gm)f = h \circ (g_1, \dots, g_m).

Primitive-Recursion in layman’s terms refers to recursion using for loops. We write the functions as f=ρ(g,h)f = \rho(g, h) where g,hg, h are the same functions that are used in the recursive definition. For example, add≜ρ(P11,S∘P23)add \triangleq \rho(P_1^1, S \circ P_2^3). The recursion must be of this form. The formal definition of multmult is given by mult≜ρ(C01,add∘(P13,P23))mult \triangleq \rho(C_0^1, add \circ (P_1^3, P_2^3)).

How do we write functions such as divdiv. Do we need if-then-else notion in our theory? Before we define this, let us try to define prevprev functions. We will define that prev(0)=0prev(0) = 0 for totality of the function. Then, we can define the function as prev≜ρ(C00,P12)prev \triangleq \rho(C_0^0, P_1^2). Using, prevprev we can define monusmonus as monus(y,x)=x−˙y≜ρ(P11,prev∘P23)monus(y, x) = x \dot- y \triangleq \rho(P_1^1, prev \circ P_2^3).

Now, to introduce the notion of booleans, we define isZero≜ρ(C10,C02)isZero \triangleq \rho(C_1^0, C_0^2). We can use this function to utilise booleans. Similarly, leq≜ρ(C11,isZero∘monus∘(S∘P13,P33))leq \triangleq \rho(C_1^1, isZero \circ monus \circ (S \circ P_1^3, P_3^3)). Using similar logic, we can implement looping and branching.

We will now see the limitations of primitive-recursion.

Limitations of primitive recursion

We have seen composition as h∘(g1,…,dn)h \circ (g_1, \dots, d_n). This concept is equivalent to passing parameters to functions in programming. To refresh the shorthand notion of primitive recursive functions, we define if-then-else as if_then_else(x,y,z)if\_then\_else(x, y, z) as yy when x>0x > 0 and zz otherwise. Therefore, if_then_else(x,y,z)=ρ(P22,P34)if\_then\_else(x, y, z) = \rho(P_2^2, P_3^4). Using this, we define

quotient(x,y)≜ρ(ite∘(P11,0,∞),ite∘(P33,ite∘(monus∘(mult∘(P33,S∘P23),S∘P13),P23,S∘P23),∞))\begin{align} quotient(x, y) &\triangleq \rho ( ite \circ (P_1^1, 0, \infty), \\ & ite \circ (P_3^3, ite \circ ( \\ &monus \circ (mult \circ (P_3^3, S\circ P_2^3) , \\ &S \circ P_1^3) , P_2^3 , S \circ P_2^3), \infty) ) \end{align}

Ackermann function

Many mathematicians tried to show that primitive recursion is not enough to represent all functions. In this pursuit, Ackermann came up with the following function

A(0,x)=x+1A(y+1,0)=A(y,1)A(y+1,x+1)=A(y,A(y+1,x))\begin{align} A(0, x) &= x + 1\\ A(y + 1, 0) &= A(y, 1) \\ A(y + 1, x + 1) &= A(y, A(y + 1, x)) \\ \end{align}

Similarly, there is a ‘91-function’ that Mc Carthy came up with. It is given as

Mc(x){x−10x>100Mc(Mc(x+11))otherwiseM_c (x) \begin{cases} x - 10 & x> 100 \\ M_c(M_c(x + 11)) & \text{otherwise} \end{cases}

The above function always returns 9191 for x<100x < 100. However, it requires a lot of recursive calls for evaluating its value.

All primitive functions are total

The converse of the above statement is false. For example, the Ackermann function is not primitive. The idea is to show that any ff defined using primitive recursion grows slower than A(nf,y)A(n_f, y) for some nfn_f. Using Godel numbering we can count all the possible primitive recursive functions.

Partial Recursive functions

We use the idea of minimisation to define partial functions and also increase the expressive power of our definitions. We have the following definition

μ(f)(x1,…,xk)≜{z∀z1<z  f(z1,x1,…,xk)>0∧f(z,x1,…,zk)=0\mu(f)(x_1, \dots, x_k) \triangleq \begin{cases} z & \forall z_1 < z \; f(z_1, x_1, \dots, x_k) > 0 \land f(z, x_1, \dots, z_k) = 0\\ \end{cases}

Notice that the first case in the above definition behaves like a while loop, as it gives the smallest value of zz that renders the function zero. The ‘partiality’ in the function definition comes from the fact that ff may never be zero.

The Church-Turing thesis states that all definable functions that can be defined using primitive recursion, minimisation, and substitution can be computed by a Turing machine. There is no proof for this yet. The set of these functions is the set of ‘all effectively computable functions’. However, there are undecidable functions that are not computable by a TM.

Equational Logic

This paradigm has the same expressive power as primitive recursion but is easier to express. To start off, we consider the function leqleq. We will define NN as {0,S(0),S(S(0)),… }\{0, S(0), S(S(0)), \dots\}. We write the rules as

leq(0,x)=S(0)leq(S(x),0)=0leq(S(x),S(y))=leq(x,y)\begin{align} leq(0, x) &= S(0) \\ leq(S(x), 0) &= 0 \\ leq(S(x), S(y)) &= leq(x, y) \end{align}

This way of writing rules is known as Pattern matching. Similarly, gcdgcd is given by

gcd(0,x)=xgcd(add(x,y),x)=gcd(y,x)gcd(y,add(x,y))=gcd(y,x)\begin{align} gcd(0, x) &= x \\ gcd(add(x, y), x) &= gcd(y, x) \\ gcd(y, add(x, y)) &= gcd(y, x) \\ \end{align}

In the above definition, the pattern matching is semantic and not syntactic. The syntactic pattern matching definition uses if_then_elseif\_then\_else. However, note that if_then_elseif\_then\_else is always assumed to be calculated in a lazy manner. That is, the condition is evaluated first and the corresponding branch is then evaluated. If the expressions in the two branches are evaluated along with the condition, then there is a chance that the computation never ends.

Also, the factorial function factfact is given by

fact(0)=S(0)fact(S(x))=mult(S(x),fact(x))\begin{align} fact(0) &= S(0) \\ fact(S(x)) &= mult(S(x), fact(x)) \end{align}

Another way of writing the factorial function using tail recursion is

f(x)=fa(1,x)f(y,1)=yfa(y,S(x))=fa(y×S(x),x)\begin{align} f(x) &= f_a(1, x) \\ f(y, 1) &= y \\ f_a(y, S(x)) &= f_a(y\times S(x), x) \end{align}

Notice that the first definition of factfact is very inefficient compared to the latter. The second definition does inline multiplication with the arguments carrying the answer. However, the values are pushed on to the stack in the case of the first definition. These concepts of optimisation come to great use in building compilers.

Term-rewriting

We have seen 3 computation paradigms

  • Turing machine
  • Type-0 grammars
  • Partial recursive functions

Now, we shall see a 4th paradigm called as term rewriting.

We have terms and domains. There a few constructors involved with a domain. For example, we have 0,S0, S for NN. Also, for lists we have nlnl (empty list) and ∙\bullet (cons/pipe). We use them as follows

image-20220330010921594

There are also constants (00) and function symbols/constructors (SS). Termination is guaranteed in normal forms. We also want unique normal form. This will ensure that a term gives a single answer with different recursions (confluence). If we get two answers, we call it ill-defined systems.

To understand this better, we shall define expexp.

exp(x,0)=s(0)exp(x,S(y))=mult(x,exp(x,y))\begin{align} exp(x, 0) &= s(0) \\ exp(x, S(y)) &= mult(x, exp(x, y)) \end{align}

maxmax is defined as

max(0,y)=ymax(S(x),S(y))=max(x,y)max(x,0)=x\begin{align} max(0, y) &= y \\ max(S(x), S(y)) &= max(x, y) \\ max(x, 0) &= x \\ \end{align}

Lists

Suppose we want to define appapp. We then have

app(nl,y)=yapp(∙(x,y),z)=∙(x,app(y,z))\begin{align} app(nl, y) &= y \\ app(\bullet(x, y), z) &= \bullet(x, app(y, z)) \end{align}

Similarly,

rev(nl)=nlrev(∙(x,y))=app(rev(y),∙(x,nl))\begin{align} rev(nl) &= nl \\ rev(\bullet(x, y)) &= app(rev(y), \bullet(x, nl)) \end{align}

Homework. Show that len(x)=len(rev(x))len(x) = len(rev(x))

How do we sort a list of numbers?

sort(nl)=nlsort(∙(x,y))=ins(x,sort(y))ins(x,nl)=∙(x,nl)ins(x,∙(y,z))=∙(min⁡(x,y),ins(max⁡(x,y),z))\begin{align} sort(nl) &= nl \\ sort(\bullet(x, y)) &= ins(x, sort(y)) \\ ins(x, nl) &= \bullet(x, nl) \\ ins(x, \bullet(y, z)) &= \bullet(\min(x, y), ins(\max(x, y), z)) \end{align}

Homework. Try quick sort and merge sort.

Termination

We have termination on NN due to >>. How about N×NN \times N? We use lexicographic ordering. One might think it’s not well-founded. This is because (9,1)(9, 1) is greater than (5,1000)(5, 1000). However, it is well-founded for finite length tuples. In case of strings, the length need not be finite in lexicographic ordering. Therefore, the ordered list need not be finite.

Homework. Give an ordering rule for multi-sets

Predicates and Branching

It is easier to express these things in the term-rewriting paradigm. I’m skipping these for brevity.

Can we write isPrimeisPrime, gcdgcd, and nth−primenth-prime? This paradigm naturally develops to Functional Programming. It’s essentially writing everything in terms of functions as we’ve been doing so far.

Logic Programming

Suppose we give the black-box the input x+3=10x + 3 = 10. Can we determine xx? Can we ask multiple answers in case of u+v=10u + v = 10? It is possible to do so in logic programming. We do this by passing parameters by unification. That is, we try to convert the parameters u,vu, v to look like the parameters given in the rules of ++. This is known as backtracking.

Term matching is don’t care non-determinism. There might be multiple possible reductions at any given situation, and all will lead to the same answer in case of well-formed normal forms. Also, all the paths should terminate.

What are the strategies for computing normal forms?

  • Hybrid - Check if sub-term matches rule-by-rule
  • Innermost - Many programming languages adopt this. Evaluate the “lowest” redex first.
  • Outermost - This is lazy evaluation. We evaluate topmost redex first.

Redex is a sub-term where a rule can be applied.

And then, sir lost his connection :D

Aside. Write primality test function using primitive recursion.

>>prime(0)=0>prime(S(x))=g(x,S(x))>g(0,y)=0>g(S(x),y)=ite(isZero(y),1,>ite(isZero(monus(S(x),gcd(S(x),y))),0,g(x,y)))>gcd(0,y)=y>gcd(S(x),y)=ite(gte(S(x),y),gcd(monus(S(x),y),y),gcd(y,x))>>> \begin{align} > prime(0) &= 0 \\ > prime(S(x)) &= g(x, S(x)) \\ \\ > g(0, y) &= 0 \\ > g(S(x), y) &= ite(isZero(y), 1,\\ > &ite(isZero(monus(S(x), gcd(S(x), y))), 0, g(x, y))) \\ \\ > gcd(0, y) &= y \\ > gcd(S(x), y) &= ite(gte(S(x), y), \\ &gcd(monus(S(x), y), y), gcd(y, x)) > \end{align} >

We were discussing the definition of quotientquotient in the previous lecture. In terms of minimisation, we can write the definition as

quotient(x,y)=μ(f)(x,y)f(k,x,y)=y∗k>x\begin{align} quotient(x, y) &= \mu(f)(x, y) \\ f(k, x, y) &= y*k > x \end{align}

Encoding Turing machines

Let us consider the example of enumerating all the finite subsets of NN. A subset (n1,n2,…,nk)(n_1, n_2, \dots, n_k) is represented as m=p1n1×⋯×pknkm = p_1^{n_1} \times \dots \times p_k^{n_k} where p1,…,pkp_1, \dots, p_k are the first kk prime numbers. Note that we need to ignore trailing zeros for this.

Can we enumerate Turing Machines? Let us try to encode a Turing Machine as a bit string. The core idea is that a Turing Machine has a finite set of states. We can encode a transition in the following way - Suppose we have the transition δ(q3,X1)=(q7,X2,D0)\delta(q_3, X_1) = (q_7, X_2, D_0). Then, the bit string corresponding to this is

11  000  1  0000000  1  0  1  00  1  0  1111\; 000 \;1 \; 0000000 \; 1\; 0 \; 1 \; 00 \; 1 \; 0 \; 11

Here, a 11 just acts as a separator, and every state, tape symbol and direction are encoded in unary format. A substring 1111 represents the start of a transition, followed by q3,q7,X1,X2,D0q_3, q_7, X_1, X_2, D_0 for the above example. This way, we can list all the transitions of the Turing Machine. All the transitions can be enclosed between a pair of substrings (111,111)(111, 111). Now, we just need to add the set of final states.

Instead of listing out all the final states, we can convert the Turing Machine to an equivalent TM which has a single finite state.

Homework. Prove that the above conversion can be done for any Turing Machine.

Now that we have encoded a TM, how do we enumerate the set of all TMs? We know how to enumerate bit strings based on the value and the length (ignore leading 00‘s for non-ambiguity). We need out to weed out the bit strings that do not represent a valid TM.

What features are present in a bit string that represents a TM? It needs to start with 111111, and end with 111111. If there is a 1111 in between the above substrings, there need to be at least 4 11‘s in between with appropriate number of 00’s in between. This concludes our discussion on encoding TMs.

Variants of TM

Let us consider the time of execution with a single computer and nn computers. Any task will have at most nn times speedup when done on nn-computers in comparison to a single computer (generally). For example, matrix multiplication can be heavily parallelised. However, tasks such as gcd calculation of kk numbers is inherently sequential and it is not easy to speed it up using parallel computation.

Now, we shall consider variants of TMs and show equivalence of each with the 1-way infinite tape variant.

2-way infinite tape

It is easy to see that a 2-way infinite tape can be restricted of the left movement beyond a point to simulate all the 1-way infinite tape machines.

To prove the other direction, we will consider a multi-track 1-way TM. That is, every cell will now contain 2 elements. The basic idea is that a 2-way machine of the form ⋯∣B1∣B0∣A0∣A1∣…\dots \mid B_1 \mid B_0 \mid A_0 \mid A_1 \mid \dots will be converted to (A0,C)∣(A1,B0)∣… (A_0, C) \mid (A_1, B_0) \mid \dots.

The states in the 2-way machine will be separated based on whether the transition is on the left side of the tape or the right side. Then, based on the side, we will work on the first element in the tuple of each cell or the second element. The formal proof is left to the reader.

Multi tapes

There are multiple tapes under a single control. Therefore, each transition is represented as (X1,…,Xk)∣(Y1,…,Yk),(D1,…,Dk)( X_1, \dots, X_k )\mid ( Y_1, \dots, Y_k) , (D_1, \dots, D_k). One can see that all the logic boils down to the Satan-Cantor puzzle.

Again, one direction of the equivalence is straightforward. The other half involves converting a kk-tuple to a natural number.

Non-Determinism

The equivalence can be shown in a similar way as that of regular languages.

k-head machine

We have a single tape which has multiple heads that move independently.

Offline TM

The input tape never changes. That is, the actions are read-only.

Universal Turing Machine

The intention is to build a general purpose computer. Recollect that a Turing Machine is represented as M=(Q,Σ,T,δ,q,B,F)M = (Q, \Sigma, T, \delta, q, B, F).

Every Turing Machine has an equivalent TM

  • whose alphabet is {0,1}\{0, 1\} and the set of tape symbols is {0,1,B}\{0, 1, B\}, and
  • has a single final state.

LL is

  • recursively enumerable - there exists a TM (recogniser) that accepts LL (need not halt on wrong input, think of recogniser built from enumerators).
  • recursive - there is a TM that accepts LL which halts on all inputs.

For example, consider the language that accepts a pair of CFGs (G1,G2)(G_1, G_2) if L(G1)∩L(G2)≠ϕL(G_1) \cap L(G_2) \neq \phi. To show that this language is recursively enumerable, we will give a high level algorithm in terms of primitive steps that we know can be converted to a TM. We consider the following algorithm.

- Enumerate L(G_1) // enumerate w, check G_1 =>* w (CYK)
- For each w in L(G_1) check if G_2 =>* w

Now, if we generate a word and check for the word in the other grammar alternately, then the algorithm will halt if the input is acceptable. However, it is not guaranteed to halt in case of unacceptable input for this algorithm. Does that mean the language is recursively enumerable?

We need to show that we can’t construct an algorithm that halts in case of an unacceptable input. Then, we can conclusively state that the language is recursively enumerable.

In conclusion, there are language that are recursively enumerable, and languages that are not recursively enumerable. The set of recursive languages are a strict subset of the set of recursively enumerable languages.

Non-recursive language

We know that we can enumerate all TMs and all w∈Σ∗w \in \Sigma^*. Then, we draw a 2D infinite bit matrix A where AijA_{ij} tells whether wi∈Mjw_i \in M_j. Now, we use the Cantor’s diagonalization argument to conclude that Ld={i∣Aii=0}L_d = \{i \mid A_{ii} = 0\} is not recursively enumerable. Genius proof based off Barber’s paradox.

If LL is not recursively enumerable, then Lˉ\bar L is also not recursively enumerable. That is, show that if TM accepts LL, then it must also accept Lˉ\bar L.

One might ponder on how we construct the table AA when some TM may not halt for a few inputs. The important distinction is that, we are “defining” this table conceptually and not “computing” it. The concept of dovetailing also comes to use here.

Recursively enumerable but not Recursive

The language of the Universal Turing Machine is the required example. We formally define this language as Lu={(M,w)∣ M halts on w}L_u = \{( M, w) \mid\ M \text{ halts on } w\}.

Equivalently, we are trying to write a Python script that takes another Python script as input along with some arguments. This script should halt when the input python script halts on the input argument, and need not halt otherwise. Basically, we are trying to build a simulator TM.

No lectures 32 and 33.

Undecidability

A language L⊆Σ∗L \subseteq \Sigma^* is recursive if there is a Turing Machine MM that halts in an accept state if w∈Lw \in L and in a reject state if w∉Lw \not\in L. It need not halt in reject states for recursively enumerable languages. The algorithms similar to the latter TMs are semi-decidable.

We were looking for languages that are not recursively enumerable LdL_d and languages that are recursively enumerable but not recursive LuL_u. For the latter set, we had seen the universal TM. We also have the language of “polynomials that have integer roots”. How do we show that this is recursively enumerable? The key idea lies in encoding polynomials as a number. The motivation for this language comes from Hilbert’s 10th Problem.

Another example for an undecidable problem is the Halting Problem.

Let us continue the discussion on LuL_u and LdL_d from the last lecture. We had constructed a matrix AA and showed using the diagonalization argument that there are languages that are not recursively enumerable. However, we did not address two issues

  • There are multiple TMs that accept the same language - It does not matter.
  • How do we fill the table? - Computation vs Definition.

Also, all the languages defined by each row AiA_i in the matrix form the set of recursively enumerable languages.

We had defined LuL_u as {(Mi,wj)∣Mi accepts wj}\{(M_i, w_j) \mid M_i \text{ accepts } w_j \}. We will show that this language is recursively enumerable by constructing a Turing Machine MM that accepts this language. The input tape will initially have the encoding of MiM_i followed by the encoding of wjw_j. Now, we use two more tapes

  • One for copying wjw_j
  • Another tape for keeping track of the state in MM, starting with state 0.

Now, we give the higher level logic of MM.

  • Validate MiM_i. This can be done using a TM.
  • Run MiM_i step-by-step. Pick the top state from the 3rd tape, find the corresponding move from the first tape, and update the 2nd and 3rd tapes.

The last two tapes help simulate any input TM. In conclusion, we have constructed a universal TM. Therefore, the TM paradigm is powerful enough to perform self-introspection.

Note that we have still not shown LuL_u is not recursive. We will use the properly of LdL_d not being recursively enumerable to show this.

Let us continue the discussion on the Universal Turing Machine. The encoding of a move δ(qi,Xj)=(qk,Xl,Dm)\delta(q_i, X_j) = (q_k, Xl, D_m) in a Turing Machine is 0i10j10k10l10m0^i10^j10^k10^l10^m. The universal TM works in 3 steps

  • Decode/Validate
  • Set up the tapes
  • Simulate

Also, we had shown that LuL_u is recursively enumerable by the construction of the universal TM. Suppose, there is a TM that halts every time for LuL_u. Now, we will show that LuL_u is recursive then LdL_d is recursive. To do that, we will convert LdL_d into an instance of LuL_u.

image-20220413194329791

Here, we can see that we are able to answer the question wi∈Ldw_i \in L_d by constructing a TM using the Universal TM. That is, if the Universal TM is recursive, then LdL_d is also recursive. Think.

Reduction Technique

To understand this technique, consider the following two problems

  • Lne={(M)∣L(M)≠ϕ}L_{ne} = \{( M ) \mid L(M) \neq \phi\} - Machine accepts at least one string
  • Lrec={(M)∣L(M) is recursive}L_{rec} = \{( M ) \mid L(M) \text { is recursive}\} - The language recognized by MM is decidable

The first language is recursively enumerable using dovetailing (words and moves being the dimensions). The second language is not recursively enumerable. To show non-recursivity, we convert LdL_d or LuL_u to an instance of this language. We need to try and come up with an algorithm that halts for machines with empty languages.

How do we do this?

The second problem is a little bit more difficult.

In conclusion, given a language

  • To prove that it is recursive, we need to construct a TM that halts on all inputs.
  • To prove that it is recursively enumerable, we just need to construct a TM that halts on good inputs. To show that it is not recursive, we need to use reductions probably.
  • To prove non recursively enumerable, we need to show that we can’t construct any TM.

TM is a powerful model as it is universal (self-referential), and it has many undecidable problems. They can represent Type-0 Grammar, Partial Recursive functions, and RAM (random access mechanism).

Post Correspondence Problem

Post is a mathematician. Consider the following table

w x
1 111
1011 10
10 0

Now, take the string 101111110101111110. Can we decompose this string in terms of wiw_i or xix_i? For example, we can decompose the string as 21132113 in terms of w′sw's and 21132113 again in terms of x’sx’s. These decompositions need not be unique.

So, PCP is stated as follows.

Given w={wi∣wi∈Σ∗},x={xi∣xi∈Σ∗}w = \{w_i \mid w_i \in \Sigma^* \}, x = \{x_i \mid x_i \in \Sigma^*\} and a string s∈Σ∗ s \in \Sigma^*, we need to be able to come up with decompositions s=wi1…wils = w_{i1} \dots w_{il} and s=xj1…xjls = x_{j1}\dots x_{jl} such that ik=jkik = jk for k∈{1,…,l}k \in \{1, \dots, l\}.

Consider the following table.

w x
10 101
011 11
101 011

Now, for any string ss, we will not be able to come up with decompositions that are equal for the above sets.

The reason we came up with this problem, is to show that PCP is undecidable (not recursive). That is, no TM can halt correctly on all PCP instances. However, it is recursively enumerable as we can enumerate all sequences fairly. This can be shown by a reduction of LuL_u to PCP.

Let us now consider another problem - Ambiguity of CFGs. Can we build a TM that halts with a ‘yes’ if the input CFG has an ambiguity and with a ‘no’ is it does not. In an ambiguous grammar, a single word has multiple derivations in the grammar. That is, we have multiple structurally different derivation trees. Using this problem we are trying to show the importance of direction of reduction. We know that PCP is undecidable. Therefore, we need to reduce PCP to an instance of the CFG problem. That is, we’ll essentially show that is the CFG problem is decidable, then so is PCP.

PCP is essentially a pair of sets of strings. What is the grammar corresponding to these sets such that when PCP has a solution, the grammar is ambiguous and unambiguous otherwise? We introduce kk new symbols a1,…,aka_1, \dots, a_k. We construct the following grammar

S -> Sa | Sb
Sa -> w_i Sa a_i | w_i a_i
Sb -> x_i Sb a_i | x_i a_i

It is easy to see that this grammar meets our requirements. To prove this, we need to show the proof in two directions

  • If PCP has a solution, then G is ambiguous
  • If G is ambiguous, then PCP has a solution. Here, we need to show that ambiguity happens only due to Sa and Sb.

Why did we introduce a?

Note. To show problem A is undecidable knowing that problem B is undecidable, we essentially show that A is a subroutine of B.

Properties of Recursive Languages

If L1L_1 and L2L_2 are both recursive, then so are

  • L1∪L2L_1 \cup L_2
  • L1∩L2L_1 \cap L_2
  • L1−L2L_1 - L_2
  • L1cL_1^c
  • L1L2L_1L_2

Recursively enumerable languages are closed under intersection, but not under complement.

Note. Don't get confused into thinking there are three (disjoint) kinds of sets: decidable, semi-decidable, and undecidable. There are two kinds: decidable and undecidable. Semi-decidable falls under undecidable.

NP-Completeness

Decision Problems

These are a class of problems that deal with problem instances like Fermat’s last theorem - ∀n>2∃a,b,c,an+bn=cn\forall n > 2\exists a, b, c, a^n + b^n = c^n? We also have the law of excluded middle in decision problems - The answer is either ‘yes’ or ‘no’.

Optimisation problems can be converted to a decision problem.

Decidable Problems

We solve these problems by building a brute-force TM - generate and test method. For example, consider the problem of finding a vertex cover in a graph of size kk. Now, the TM will enumerate all subsets of size kk and check each one for vertex cover conditions.

We come up with “algorithms” for these problems and check their efficiency. Apart from time and space complexity, we also consider descriptive (Kolmogorov) complexity. It refers to the program size. In our case, it refers to the size of the TM.

Complexity Classes

Given two problems, which problem is “more difficult”? The difficulty criterion we consider is time. We define two classes of problems PP and NPNP.

  • P is the class of (decision) problems that can be solved in “polynomial time” by a deterministic Turing Machine MM.
  • PSPACE refers to the class of problems that use polynomial number of cells in the tape.
  • NP is the class of (decision) problems that can be solved in polynomial time by non-deterministic TM. This is equivalent to guessing a solution in polynomial time followed by checking using a deterministic TM in polynomial time. The claim is that this is same as a non-deterministic TM. We shall use this technique to show that problems are in NP. That is, we’ll show that we can guess in P-time and verify in P-time.

For example, let us try to show vertex cover problem is in NPNP. Aside - A polynomial algorithm was developed in the 1980s for the problem “Is nn a prime number” in IITK (Manindra Agarwal).

More difficult problem

Given L1L_1 and L2L_2, which one is more difficult? We use reduction to answer this question.

L1≤PL2L_1 \leq_{P} L_2

If L1L_1 can be converted to an instance of L2L_2 in polynomial time, then we have the above defined relation. That is, L2L_2 is at least as difficult as L1L_1.

Completeness

We try to determine the most difficult problem amongst all the problems. To start off, we define that LsatL_{sat} belongs to NP-complete set. This problem refers to the satisfiability of propositional logic expressions.

Every problem in NPNP can be reduced to LsatL_{sat}. In some sense, LsatL_{sat} is the most difficult problem. But how did we come to this conclusion without knowing all the problems in NPNP? We can show that any non-deterministic TM can be reduced to LsatL_{sat}.

We define hard problems as anything not in PP. There are problems that are more difficult than the ones in NPNP!

We classify decidable problems as the set of recursive languages. These problems can be further classified as

  • Deterministic TM takes only polynomial number of steps in terms of the input size to halt.

  • A non-deterministic TM takes polynomial number of steps.

  • A non-deterministic TM needs Ω(2n)\Omega (2^n) number of steps.

SAT Problem PsatP_{sat}

Given a well formed formula FF, is FF satisfiable? A well formed formula is a formula that is formed via the base case (propositional variables) and inductive rules (using connectors like negation, ‘and’ and ‘or’).

This problem can be solved via brute force but that is exponential. So we now ask the following questions

  • Is Psat∈PP_{sat} \in P?
  • Is Psat∈NPP_{sat} \in NP?

We’ll answer the second question first. It is easy to construct a non-deterministic TM that solves the problem in polynomial steps. We can generate a random guess (bit string) and verify (check satisfiability) in polynomial steps. This procedure is the way to show that any problem is in NPNP.

Comparison of Problems

Let us revisit the topic of ≤P\leq_{P}. Psat≤P3-SATP_{sat} \leq_{P} 3\text{-}SAT, and 3-SAT≤PVC3\text{-}SAT \leq_P VC where VCVC is the vertex cover problem.

To do perform the latter reduction, we construct nodes for pp and ¬p\neg p for each propositional variable in the clause. Then, we construct cliques out of each disjunction in the CNF. Finally, we connect each pp with ¬p\neg p. Now, if we can find a vertex cover of this graph with size 2k2k, we get the satisfiability of the 3-CNF clause with kk disjunctive clauses.

  • If FF has a satisfying assignment, take out exactly one literal with value 11 out of each disjunctive clause and construct a VC out of the remaining literals. It can be shown that the vertex cover will have size 2k2k.
  • If there is a vertex cover, then we can drop at most 1 node from each disjunctive clause. Also, as the size if 2k2k we can drop exactly 1 node from each clause. Assign these dropped nodes with a value of 11. Now, since we have a true value in each clause, the assignment satisfies the expression.

NP-Completeness

As we mentioned before, we consider PsatP_{sat} or 3-SAT3\text{-}SAT as the hardest problem. That is, for every Q∈NPQ \in NP, Np≤PPsatNp \leq_P P_{sat}.

We show this by reducing non-deterministic Turing Machines to PsatP_{sat}. To prove that a problem is NP-complete, we show

  • That the problem lies in NPNP. This step is very important as there are problems that are more difficult than NPNP.
  • Convert the 3-SAT problem (or any other known NP-complete problem) to an instance of the given problem.

We list out some problems in NP-complete set.

  • 3-SAT
  • Vertex Cover
  • Clique in a graph
  • kk-coloring
  • Min-cut and Max-flow
  • Travelling Salesman Problem
  • Hamiltonian Cycle in a graph
  • Partitioning of a set of numbers such that the partitions have the same sum
  • Knapsack problem

The good news about NPNP-complete problems is that there are many heuristics and approximations such as LAs Vegas and Monte Carlo that work well for most of the above problems.


END OF COURSE


Type to search the whole site.