will study computability theory – whether a problem can be solved by a computer (ch 4, 5, 6)

• not studying complexity theory (if a problem can be solved, how much time/space it will take to solve) (ch 7, 8, 9, 10, CSCE 423, 424)

Requires some preliminaries – ch 1-3

1. finite automata

2. push-down automata

3. Turing machines

Ch 0 will be a review

review of

• sequence

• set

• string

• language

Regular Languages

deterministic FA

non-deterministic FA

regular expressions

what exactly is a regular language – how do they connect to problems that are solveable by the three models

models used by many search/parse/editing tools

testing and verification/model checking

modelling OS/network protocols

all languages that can be recognized by a DFA are regular languages, likewise for NFA

A proof that DFA and NFA are equivalent

To show a languageg is regular, show either a DFA or an NFA

DFAs are a special type of NFA

So prove that NFAs are a subset of DFAs

Showing that REs accept regular expressions

RE to DFA/NFA

• $a$ - start state, accept a, to final state

• $\epsilon$ - start state is final state, no transitions other than the initial epsilon

• $\emptyset$ - start state, no transitions, no final state

• $R_1 \cup R_2$ - given a machine for each, use an epsilon transition to each as an NFA

• $R_1 \circ R_2$ - all final states of $R_1$ have an epsilon transition to the initial state of $R_2$

• $R_1^*$ - Empty state before initial, epsilon transition from each final state to the original start state

DFA/NFA to RE

Requires GNFA

• NFA + RE as transition labels

Conversion:

1. DFA to GNFA in a special form

   1. Start state only has outgoing transitions – often just add a new start state w/ ε transition

   2. one final state, only incoming transitions – Give all final states an ε transition to a new final state

   3. Only Any state to any state: at most one transition – merge transitions with union

2. Remove states one by one, except the start and final state – label each transition with concat of each relevant transition

3. The label between start and final is the regular expression

HW1 Due 09-21, No class 09-24, HW reviewed by TA 09-26, Exam 1 09-28

The Pumping lemma

• describes a common property of all regular languages, and some non-regular languages

• if a language has the property is it regular?

  • it may be regular

• if it doesn't have the property, than it isn't regular

• based on pigeonhole principle

  • if more than $p$ pigeons are placed into $p$ holes, then at least one hole will have at least one pigeon

• Consider a reg. lang. $A$ and a DFA for $A$ as well as a string $s \in A$ of $n$ symbols

  • The path must then consist of $n + 1$ states

  • if $n + 1 > |D|$, then the path repeats some states

  • $xz$ – $x$ takes it to 9, $z$ takes it from 9 to 13

  • $xyyz$ – $x$ takes to 9

• For any integer $i \geq 0$, $xy^iz$ is accepted by the machine

• If $A$ is a regular language, then there is a number $p$ (the pumping length) such that for any string $s$ in $A$ with $|s|\geq p$ it can be divided into two three pieces $s = xyz$ satisfyining the following conditions

  1. for each $i \geq 0$, $xy^iz \in A$

  2. $|y| > 0$

  3. $|xy|\leq p$

• Number of states is often the pumping number $p$ (in particular of a minimized DFA)

contrapositive of the pumping lemma

• normal: if $A$ is regular, then for any long enough string, some part of its first $p$ symbols can be pumped

• contrapositive: if for some long enough string $s$ in $A$ none of its first $p$ symbols can be pumped, then $A$ is not regular

• Language $A$ is not regular if, for every arbitrary number $p$, there exists a string $s$ in $A$ with $|s|\geq p$ having the following property:

  • for any decomposition of $s = xyz$ in which $|xy| \leq p$, and $|y| > 0$,…

Do it.

1. Let $p$ denote an arbitrary number

2. pick a string $s \in A$ with $|s| \geq p$

3. identify all possible decomps of $s$ into $xyz$ with $|xy| \leq p$ and $|y| \geq 0$

4. show that for each decomp, there exists an $i \geq 0$ s.t. $xy^iz \not\in A$ (i may be different for each decomp, if it isn't a good choice, try again)

5. conclude that $A$ is not regular.

$L_1 = \left\{ w \mid w \mathrm{ has the same number of a's and b's} \right\}$

• let $p$ be arbitrary

• Let $s = (ab)^p$ and we have $(ab)^p \in L_1$, and $|(ab)^p| = 2p > 1$

• wrong

  • $s = xyz$, $x = \epsilon$, $y = aba$, $z = b(ab)^{p-2}$

  • let $i = 0$, then $xy^iz = xz = b(ab)^{p-2} \not\in L_1$

  • Therefore, $L_1$ isn't regular

• Identify all possible decomps of $s$ into $xyz$ with $|xy| \leq p$ and $|y| > 0$

• follow from here

• Try

  • $p$ is arbit.

  • $s = a^pb^p$ and we have $a^pb^p \in L_1$

  • Ident all possible decomps of $s$ into $xyz$ with $|xy| \leq p$ and $|y| > 0$

  • $x = \epsilon$, $y = a^p$, $z = b^p$

    • $k = a^n$, $p-k \geq n \geq 0$

    • $y = a^k$, $p \geq k \geq 1$

    • $z = a^{p-n-k}b^p$

  • ex, $y = 2$, thus, language isn't regular.

Consider $L_2 = \{ww | w \in \{a,b\}^*\}$

• $p$ is arbitrary

• $s = a^pba^pb$

• $y = a^k$, $p \geq k \geq 1$, $x = a^n$, $p-k \geq n \geq 0$; $z$ is the remainder

• falls through as before

proving non-regularity

$L_3 = \{a^mb^n | m > n\}$

• $p$ is arbitrary

• $s = a^{p+1}b^p$

• $y=a^k$, $p \geq k \geq 1$

• $x=a^n$, $p-k \geq n \geq 0$, $z = remaining$

• $i = 0$, $xy^iz = xz = a^{p+1-k}b^p$, $\not\in L_3$

Closure properties

• $A \cup B$ – regular

  • combine NFA/DFA – easy

• $A \circ B$ – regular

  • combine NFA/DFA – similarly easy

• $A^*$ – regular

  • Allow accepting empty string and repeats

• $A \cap B$ – regular

  • see notes for DFA, can be extended to NFA

• $\bar{A}$ – regular

  • switch final/non-final states

• Reverse of a language a is defined as follows: $A^R = \{w^R | w \in A\}$

  • change direction of transitions, start state becomes final, if multiple final states, add a new state w/ epsilon transitions to old final states

  • Also regular

• $\Sigma = \{a, b\}$, $\Gamma = \{0, 1\}$

  • $h(a) = 00$, $h(b) = 01$

  • if $A$ is regular, than $h(A)$ is also regular

Closure properties can be used as for a contrapositive w/ the pumping lemma.

$L_4 = \{w | w \text{has different number of a's and b's}\}$

• We see that $\bar{L_4} = L_1$

• we have already proven that L_1 is not regular, therefore L_4 is not regular

$L_5 = \{a^nb^n | n \geq 0\}$

• $L_5 = L_1 \cap a*b*$

• therefore, $L_5$ is not regular – wrong! L_1 is not regular to begin with!

• Subset property doesn't apply either

is it possible to design a computer to solve a problem?

• chapter 1 , whether or not it's possible to design a DFA/NFA/RE for a given language

• to simplify – consider only decision problems – is a number divisible by 5

• Is it possible to design a computer to solve a decision problem

• what does it mean to solve – determine yes or no given an input

• input must be encoded

• whether or not strings are accepted

• is it possible to design a computer to recognize lang of decision problem

Models and Languages:

1. DFA/NFA/RE – smallest group, regular languages

2. PDA/CFG – Context Free Languages

3. Real Computers – problems solvable by computer

4. Turing Machines – Turing-recognizable languages

The CFG

• mathematical model to describe languages

• widely used in many applications

  • specify programming languages

  • generate images (contextfreeart.org)

  • automatically generate CS papers (pdos.csail.mit.edu/scigen)

• Ex:

  • $A \to 0A1$

  • $A \to \epsilon$

  • LHS is a variable

  • non variables, non empty string are terminals

• $(V, \Sigma, R, S)$

  • $V$ – Set of Variables

  • $\Sigma$ – Set of Terminals (alphabet)

  • $R$ – Set of Rules

  • $S$ – Start Variable

• Rules may be combined – $A \to 0A1 | \epsilon$

• Start from variable – find a rule that matches, and continue by variable.

• $\left\{ w \mathrm{over} \Sigma | S \Rightarrow^* w \right\}$

• parse trees may be used to explain a CFG

  • graphical/tree-based structure

• Ex:

  • $S \to S + S$

  • $S \to a$

CFGs are more powerful that DFA/NFA/RE

• Convert REs to a CFG

  1. $a \iff S \to a$

  2. $\epsilon \iff S \to \epsilon$

  3. $\emptyset \iff S \to S$ (or no rules)

  4. $R_1 \cup R_2 \iff S_1 \to R_1, S_2 \to R_2, S \to S_1 | S_2$

  5. $R_1 \circ R_2 \iff S \to SR_1 SR_2$

  6. $R_1^* \iff S \to \epsilon | SR_1 S$

• For NFA/DFA:

  • $S_i = sym S_j$

be careful when designing DFAs

use the examples

make sure to minimize

$L_1 = \left\{a^nb^n | n \geq 0 \right\}$

• $R \to \epsilon$

• $R \to a R b$

Two methods:

• Union Method – union of multiple smaller languages

• concatenation method – concatenation of multiple smaller languages

• recursive – $L_1L_2L$

• special cases

$L_2 = \left\{a^m b^n | m > n \geq 0\right\}$

• $S_2 \to a S_2$

• $S_2 \to a S_1$

$L_2 = \left\{a^mb^n | m \neq n\right\}$

• $S_3 \to S_2 | B$

• $B \to B b$

• $B \to S_1 b$

• $B^{\prime} \to B b | b$

$L_4 = \{ a^ib^ja^k | j > i + k, i \geq 0, k \geq 0 \}$

• $S_4 \to S_1 B^{\prime} S_1^R$

$L_5 = \{ x over \{a, b\} | x is a palindrome \}

• $S_5 \to \epsilon$

• $S_5 \to a$

• $S_5 \to b$

• $S_5 \to b S_5 b$

• $S_5 \to a S_5 a$

$L_6 = \{ x over \{a, b\} | x is not a palindrome \$}

• $S_6 \to a S_6 a$

• $S_6 \to b S_6 b$

• $S_6 \to a T b$

• $S_6 \to b T a$

• $T \to aT | bT | \epsilon$

$L_7 = \{ x over \{a, b\} | x has the same number of a's and b's \}$

• $S_7 = a S_7 a$

• $S_7 = b S_7 a$

• $S_7 = S_7 S_7$

• $S_7 = \epsilon$

a new model

• Adds a stack to a DFA/NFA

cfg – specify a programming language

PDAs can be used to design the compiler (See CSCE 425)

PDAs may be built upon either DFA or NFA, based upon NFA is more powerful

Stacks have 2 ops

• push – push a symbol onto the top of the stack

• pop – pop the symbol off of the top of the stack

Edges are now labeled differently: ($a, B \to C$)

• if current state is $P$, and $a$ is input symbol, and $B$ is the top of the stack symbol, then take transition, read input symbol, POP symbol B, and push $C$, going to new state $Q$

• with $\epsilon$ as $B$, the transition may be taken no matter the current symbol, and no symbol is to be popped

• with $\epsilon$ as $C$, don't push any symbol

• $\epsilon, \epsilon \to \epsilon$ – don't read, don't change the stack

• shortcuts do exist

Formal Description:

• NFA:

  $Q$

  States

  $\Sigma$

  Alphabet

  $\delta$

  $Q \time \Sigma_\epsilon \to P(Q)$

  $q_0$

  Start state

  $F$

  Final States

• PDA:

  $Q$

  States

  $\Sigma$

  Input Alphabet

  $\Gamma$

  Stack Alphabet – all possible stack symbols

  $\delta$

  $Q \time \Sigma_\epsilon \times \Gamma_\epsilon \to P(Q \times \Gamma_\epsilon)$

  $F$

  Final States

\$ is used to denote the first thing (popping will be empty stack)

An input string is accepted by a PDA if at least one copy of the PDA stops at a final state after reading the input string.

Use a 'configuration' to show how it works in homework:

• (current state, remaining input symbols, contents of the stack)

• $(1, aab, \epsilon) \Rightarrow (2, aab, \$) ⇒ (2, ab, A\$) \Rightarrow (2, b, AA\$) ⇒ (3, ε, A\$) \Rightarrow (4, \epsilon, \$)$

Designing a PDA for a language

• Split input string

• $S_1 = S_2^R$

• $|S_1| \leq |S_2|$ or other comparison

$L_1 = \{ wcw^R | w over \{a,b\}\}$

• $Q = \{1,2,3,4}$

• $q_0 = 1$

• $F = \{4\}$

• 2 makes a copy of the first part

• 3 compares the first part with the second

• transition to 4 on acceptance

$L_2 = \{ ww^R | w over \{a,b\}\}$

• $Q = \{1,2,3,4}$

• $q_0 = 1$

• $F = \{4\}$

• 2 makes a copy of the first part

• epsilon, epsilon, epsilon transition between 2 and 3

• 3 compares the first part with the second

• transition to 4 on acceptance

$L_3 = \{ w | w = w^R over \{a, b\} \}$

• add a transition between 2,3 tha reads either char but doesn't change the stack

PDA to CFG

Special form of PDA as first step

• Only one final state – epsilon transitions from old final sates to new

• Stack must be empty at the final state

  • Ex: $\Gamma = \{ \$, A, B \}$

  • Requires loop-back transitions to pop remaining stack symbols at the end

• A transiion is either a push transition ($a, \epsilon \to x$) or a pop transition ($a, x \to \epsilon$)

States P, Q – CFG Var $A_pq$ (all strings that can go from p to q without changinging the top stack symbol at p, and the top stack at p has never been popped) – Three types:

• $p\to r$ ($a, \epsilon \to x$) (push), $s \to q$ ($b, x \to e$) (pop) – $A_pq = a A_rs b$

• $p v q$ – $A_pq \to A_pv A_vq$

• $p$ – $A_pp \to \epsilon$

Continue given previous rules

Generating rules from the three types of rules

In $A_pq \to a A_rs b$, $A_rs$ must satisfy the same conditions as $A_pq$

push to pop in order for generating rules

Review of the Pumping Lemma for Regular Langugages

• The loop

Pumping Lemma for CFGs

• Assume each node has at most 3 child nodes

• If height is 1, it has at most 3 nodes

• If a tree has at least 3 leaf nodes, its height is at least 1

• $S \to aSb$, $S \to \epsilon$, $ab$

• Nuber of child nodes of a variable node is the number of symbols on the rhs of the rule

• Assume that each rule has at most $b$ symbols on the RHS, if a string as at least $B$ symbols, the height of the parse tree is at least $b$

• Generally,

  • $b$ is the max number of symbols on the RHS of a rule

  • $v$ is the total number of variables

• Consider a string $s$ that can be derived by the grammar, if $s$ has at least $b^{v+1}$ symbols, then

  • the height of the trea is at least $v + 1$

  • and the number of nodes is at least $v + 2$

  • The number of variables – the longest path has at least $v + 1$ variable nodes

  • According to the pigeonhole principle, some variable occurs at least once on the longest path

  • the number of terminals – $v + 1$

  • here are two subtrees under this parse tree – one for the earlier $T$ and another for the later.

  • The inner tree may be replaced with the outer, or likewise the outer with the inner

• Requires 2 pumped sequences?

• Lemma: If $A$ is a CFL, then there exists a pumping length $p$ such that for any stirng $s \in A$ with $|s| \geq p$, it can be devided into five pieces, $s = uvxyz$ satisfying the following conditions:

  1. For any integer $i \geq 0$, $uv^ixy^iz \in A$

  2. $|vy| > 0$ (one of $v$ and $y$ could be empty, but not both at the same time)

  3. $|vxy| \leq p$ ($vxy$ are not necessarily the first $p$ symbols since $|u|$ is unknown)

• Contrapositive: if for any $p$ there exists a string $s \in A$ with $|s| \geq p$, having the following property: For any decomposition of $s = uvxyz$ in which $|vy| > 0$ and $|vxy| \leq p$, there is an integer $i \geq 0$ for which $uv^ixy^iz \not\in A$, then the language is not context free.

Using the new Pumping Lemma

Prove that $L = \left\{ a^nb^nc^n | n \geq 0\right\}$

• Let $p$ be an arbitrary number,

• Consider $s = a^pb^pc^p$ and consider all possible decompositions as specified

• Cases:

  1. $vy$ has only $a$

     • if we set $i = 0$, we remove both $v$ and $y$

     • note, $i \neq 0$ prevents validity

  2. $vy$ consists of both $a$ and $b$

     • $i = 0$, any $i \neq 1$

  3. $vy$ has only $b$

     • See above

  4. $vy$ consists of both $b$ and $c$

     • See above

  5. $vy$ has only $c$

     • See above

• Likewise, $\{w over \{a, b, c\} | |w|_a = |w|_b = |w|_c\}$ follows, by the same string

For a string $s$ in a cfl, $A$, if $s$ is sufficiently long, then on the longest path from the root to a leaf in the parse tree, some variable appears more than once.

If $A$ is a cfl, then there exists a pumping length $p$ such that for any stirng $s \in A$, with $|s| > p$, it can be dividied into five pieces, $s = uvxyz$, satisfying the following conditions:

1. For any integerr $i \ge 0$, $uv^ixy^iz \in A$

2. $|vy| > 0$

3. $vxy \leq p$

Describes a common property

if has the property, it may be cf, but if it doesn't, it isn't CF, see contrapositive above

Prove that the following language is not context free: $L = \{ ww | w over \{a,b\}\}$

• Given cases 1-8, if $i \neq 1$, then $s \not\in L$

• For case 9:

  • if $v$ and $y$ have the same number of $a$s, string $a^pba^pb$ isn't a good choice

• Let $p$ be arbitrary, and $s = a^pb^pa^pb^p$

• For each case, if $i = 0$, the string doesn't hold. Any integer $i \neq 1$ holds. Language is not CFG

For $L = \{ wcw | w over \{a,b\}\}$

• First Proof:

  • $s = a^pb^pca^bp^b$

  • 11 cases

  • For each case, if $i = 0$, the string doesn't fit

• Different Proof:

  • List all possible decomps depending on whether $vy$ contains symbol $c$

  • 2 cases:

    • $c \in vy$

      • $i = 0$, new string $uxz$ doesn't have $c$, and thus not in $L$, in fact, $i \neq 1$ works.

    • $c \not\in vy$

      • Because $|vxy| \leq p$, $v$ and $y$ must contain a different number of symbols. Therefore, $s \not\in L$, and language not CF.

Initially only the standard turing machine, but from there, some variants

Recall DFA/NFA and PDA/CFG

Turing Machine

• Note: These are deterministic

• semi-infinite input tape, infinite to the right

• blank symbols after the original string, infinitely many

• finite number of states

• Input tape may be written to

• tape head can be moved left or right

• Transition, ex: from $P$ to $Q$, $a \to b, c$

  • $P$ – current state

  • $Q$ – next state

  • $a$ is the current tape symbol

  • $b$ is the new tape symbol

  • $c$ is either $L$ or $R$, $L$ to move head to left, $R$ to move to right

    • Moving left at leftmost edge

• Recognizes Turing-recogniseable languages (i.e., $a^nb^nc^n$)

• Has 2 final states – accept or reject

• When the machine enters the accept state, the machine accepts

• Enters the reject state or no more transitions to take

• Status may be described as a "configuration", (symbols on lhs of tape head, current state, current symbol, symbol on rhs of tape head)

• Described as:

  • $Q$ – States

  • $\Sigma$ – Input Symbols

  • $\Gamma$ – Tape Alphabet, $\Sigma \subseteq \Gamma$, Space $\in \Gamma$

  • $\delta$ – $Q \times \Gamma \to Q \times \Gamma \times \{l, r\}$

  • $q_{0}$ – Initial State

  • $q_{accept}$ – Accept State

  • $q_{reject}$ – Reject State

Design of a TM is like writing a program

Algorithm is a high-level idea

TM is the implementation

$\{a^{2^n} | n \geq 0\}$

• Count number of $a$s, say $m$

• check if $m$ is a power of 2

• Unary number to represent $m$

• use a binary number to represent $m$

Unary numbers, single symbol, $m$ is represented by $m$ symbols

binary, two symbols, etc

$a$ with unary number

• input string is already a unary number

• Checking whether a decimal number is a power of 2

  • divide by 2 until an odd number. If the odd number is $1$, $m$ is a power of 2

• Divide by 2, by replacing every other $a$ with a special symbol

• See turing machine from slides (TM1)

$a$ with binary counter

• remove an a from the string, increase counter by one

• count should be lsb first

• check to make sure that only the last bit is 1

• only count $m - 1$, and then check only 1s in counter

• See TM2 from slides

$#x#y#z$ where $x = y + z$ and $x, y, and $z$ are unsigned binary numbers, and the MSB is 1, MSB is first bit

• sum = y + z ; if sum == x, accept, reject

• while y > 0, i–, z++; if x == z, accept, reject

• while y > 0, y–, x–; while z > 0, z–, x–, if x == 0, accept, reject

• mark left end with submachine

• mini machine for initial validity (MSB check)

• mini machine for checking if $y = 0$

• mini machine for $y--$

  • find LSB, if 1, replace with 0

  • if 0, replace with 1, if next is 1, replace with 0, else, if next is 0, loop from start of step (if 0, replace w/ 1…)

• mini machine for $z++$

  • check if overflow, if so, shift $z$ right and add a 1, else, continue

• Another machine to check if $x = z$

Standard TM: Left, Right, state machine and rewrite rules

Variants

• Stay

• bi-infinite tape

• jump option

• non-deterministic

• multiple tapes

• multiple tape heads

• 2 dimensional tape

Stay option

• $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R, S\}$

• simulated using an intermediate state

• which doesn't change the intermediate symbol

Bi-infinite tape

• Mapping

  • cell-to-cell – each of T2's tape is mapped to a cell in T1's tape – every other mapping

  • string mapping – write the string of T2's tape on T1's tape

• Will require special transitions, with one or more special intermediate state

multiple tapes

• $\delta : Q \times \Gamma \times \Gamma \to Q \time \Gamma \time \Gamma \times \{L, R\} \times \{L, R\}$

• Considers symbols on tape one and two, new symbols on 1, 2; directions on tape 1, 2

• equivalent to normal TM

• Use a tape mapping – cell-to-cell or string

• Use string mapping, and special symbols (dotted) to denote current location of head

• From here, a series of special transitions is required. These are ugly.

Non-deterministic Turing Machine

• new outcome – loop, loops forever on $w$

remember - rejecting $w$ means it either enters reject or reaches a place of no more transitions

in NDTM, $\delta: Q \times \Gamma \to P(Q \times \Gamma \times \{L, R\})$

An NDTM accepts a string if at least one copy of the NDTM accepts the string.

An NDTM rejects a string if every copy rejects $w$.

An NDTM loops on $w$ if no copy accepts $w$ and at least one copy loops on $w$

Designing a TM from an NDT:

• $T1$ searches the computation tree of $T2$ on string $w$, if accept node found, $T1$ accepts $w$

• Search is done using BFS to avoid issues with looping

• searching is done in shortlex order

• From NDTM with three tapes, input string, node id, one copy of $T2$, to a standard TM

Has multiple tapes, but last one is write-only

$L(E)$ – the language of all strings printed out on the write-only tape

has no input string

$L(T)$ – all strings accepted by a TM.

Enumerator to TM:

• $T$ accepts $x$ if $x \in L(E)$

• $E$ has $m$ tapes, $T$ has $m + 1$ tapes

• $T$ simulates $E$

• Every time $E$ prints out a string $w$ on the WO tape, $T$ checks if $w = x$, if so, $T$ accepts $x$, else, continue

• Thus, $L(T) = L(E)$

TM to Enumerator:

• For $i = 1$ to $\infty$

  • $E$ simulates $T$ on string $S_i$

  • If $T$ accepts $S_i$, $E$ prints out $S_i$ on the write only tape

  • If $T$ loops on $S_i$,

• However, $L(E) \neq L(T)$, because of loops – remedy as follows:

  • For $n = 1$ to $\infty$

    • For $i = 1$ to $n$,

      • $E$ simulates $T on $S_i$ for $n$ steps

      • If $T$ accepts $S_i$, E prints out $S_i$ on the output tape

  • Then $L(E) = L(T)$

These are recursively enumerable a/k/a a Turing recognizeable language

A language is recursively enumerable iff a languages is Turing Recogniseable

Adding a stack to a DFA/NFA gives a PDA

Regular Language Closure Properties

• Union

• Concatenation

• Star

• Intersection

• Complement

Context Free

• Union

• Concatenation

• Star

Turing Recognizeable

• Union – Run A, if A accepts, fine. If B accepts, fine.

  • Accept if either accept

  • Reject if both reject

  • Loop if both loop

• Concatenation and star are part of homework

• Intersection – Also Holds

  • If a and b accept, if either reject, rejectx

• Complement – May or may not be recognizeable – See Ch. 4, will be shown later

$L$ is Turing Recognizable

• Design TM for $L$ such that if $x \in L$, $M$ stops and accepts $x$ (answer is yes)

  • if $M$ stops and rejects $x$, answer no

  • if $M$ runs forever, no answer

$L$ is Decideable

• only two answers, yes and no

• Design a decider $M$ for $L$, such that

  • if $x \in L$, $M$ stops and accepts $x$

  • if $x \not\in L$, $M$ stops and rejects $x$

The Decision problem

• Does a DFA $D$ accept a string $x$

• Language $A_DFA = ≤ft\{⟨le D, W ⟩le \mid D \textrm{accepts} w \right\}

• $A_{DFA}$ is decideable – a decider can be designed for the language

• Decider checks if encoding is valid – if not, reject

  • then simulate $D$ on $w$ – if accept, accept, else, reject

• Doesn't work for NFAs with this same system

  • After checking validity, convert NFA to DFA, then follow DFA rules

• Similarly for RE, convert to DFA

Given a TM $M$ and a string $w$, know if $M$ accepts $w$

• For Machine Program $M$ in lecture, and $w = ab$, $w = abc$ and $w = abcab$ – works, but may not always

Then:

• $U$ – a machine akes in an encoding

  • If encoding is invalid, reject

  • Simulate $M$ on $w$

    • If accepts, accept

    • If rejects, reject

  • Not a decider! But, is $U$ a TM?

    • $S_{accept}$ is $A_{TM}$

    • $S_{reject}$ $M$ rejects $w$ and invalid encoding strings

  • Then $A_{TM}$ is Turing-recognizeable, by $U$

$A_{TM}$ is undecideable – by contradiction

• Assume that $A_{TM}$ is decidable, then there is a decider $H$ for $A_{TM}$

  • Then $H$ accepts if $M$ accepts

  • Reject otherwise.

• Then make a new machine, $X$ using $H$

• $X$ takes an encoding of a TM, $M$, simulating $M$ on the encoding of itself.

• If $H$ accepts, reject, else if $H$ rejects, accept

  • $X$ rejects if $M$ accepts $\langle M \rangle$

  • $X$ accepts if $M$ does not accept $\langle M \rangle$

• Will $X$ accept itself? No! Contradiction

  • Accepts if $X$ rejects $\langle X \rangle$

  • Rejects if $X$ accepts $\langle X \rangle$

  • Contradiction!

• Thus, $A_{TM}$ is undecideable! Turing, Church, 1936

Youtube video for Halting Problem

Problem 1 – use recursive structure, likewise for problem 2

PDA for $L_1$

• Push an $A$ for each $a$

• Then have a recognizer for one $b$, two $b$'s and three $b$'s

• Uses non-deterministic transitions, similar for $L_2$

Do algebra on inequalities

Theorem 1: \(f: A \to B\) is correspoondence, tthen \(f^{-1}:B -to A\) is also correspondence

Sets a and B have the same size \(|A| = |B|\) iff \(A\) and \(B\) have the same number of elements – applies on both finite and infinite sets

Set $A$ has a smaller size than $B$, $|A| < |B|$ if there is a one-to-one function from $A$ to $B$, but no correspondence between $A$ and $B$ (again, for both finite and infinite sets)

For infinite set $A$:

• If there is a corresbondence between $A$ and $\mathbb{N} = \{1, 2, 3, \ldots\}$, then $|A| = |N|$ and $A$ is countably infinite.

• Theorem 2: If there is no correspondence between $A$ and $\mathbb{N}$, then $|A| > |N|$, and $A$ is uncountably infinite

EX: $E = \{ x | x \in \mathbb{Z}, x \mod{2} \equiv 0\}$

• Countably infinite. Several options for mapping.

$O = \{ x | x \in \mathbb{Z}, x \mod{2} \equiv 1 }$ – countably infinite

$\mathbb{Z} = E \cup O$ – Still countably infinite

• Several options for correspondence

$S$ – All possible strings over $\Sigma$

• Countably infinite if $\Sigma$ is finite

$B$ – All possible infinite sequences over $\Sigma = \{0, 1}$

• Uncountably infinite.

• By Contradiction. $f: N \to B$ is a correspondence

• Then there exists a $b \in B$, s.t. for each symbol at index $n$, it is the opposite symbol than at index $n$ of $f(n)$

• Contradiction – there does not exist an $n$ such that $f(n) = b$.

Theorem 3: If $|A = |N|$ and $B \sub A$, then $|B| = |N|$

If $|A| = |B|$ and $|A| > |N|$, then $|B| > |N|$

Number of languages vs number of TMs

• $M$ is all possible TMs; $L$ is all possible languages

  • $|M| = |N|$

    • $|M| = |M_C|$ where $M_C$ is all possible encoding strings

    • $|M_C| = |N|$ as $M_C \sub S$

  • $|L| > |N|$

    • $|L| = |B| > |N|$

    • A correspondence bust be formed between $L$ and $B$ – See Slides

Theorem: A language $L$ is decideable iff $L$ is Turing-recognizeable and $\overbar{L}$ is Turing-recognizeable ($L$ is co-Turing-recognizeable).

• Proof (forwards):

  • Given a Decider $D$ for $L$, Given $x$, accept if $x \in L$, reject if $x \not\in L$

  • Then given a TM $M_1$ for $L$, accept if $x \in L$, reject if $x \not\in L$ or if $x$ causes $M_1$ to loop

  • Likewise a TM for $\overbar{L}$ called $M_2$.

  • $M_1$ is a decider, accept if accept, reject or loop otherwise

  • For $M_2$, use decider, if decider accepts, reject or loop, if decider rejects, accept

• Proof (backwards):

  • While true:

    • Sim $M_1$ for one step on $x$

    • Sim $M_2$ for one step on $x$

    • If $M_1$ accepts, accept

    • If $M_2$ accepts, reject

Then $\overbar{A_{TM}}$ is Turing-unrecognizeable

• Proof: Assume $\overbar{A_{TM}}$ is Turing-recognizeable. And $A_{TM}$ is Turing-recognizeable. Then $A_{TM}$ is decideable. $\textreferencemark$ $A_{TM}$ is thus Turing-unrecognizeable.

Closure properties of deciedale languages:

• Union

• Concatenation

• Star

• Intersection

• Complement

Consider two problems, $X$ and $Y$

• Whether either is is decideable, or is Turing-recognizeable

• Assume a solution for $Y$ (a decider or TM)

• We say tha $X$ can be reduced to $Y$ ($X$ is reducible to $Y$), $X \leq Y$ if we can design a solution to $X$ using the solution to $Y$.

Assuming a decider for $Y$

• Decider for $X$ is built on this.

• A general reduction method

The Mapping Reduction Method:

• Given an assumed decider to $Y$

• A Mapping function $f$ is used to take the input for $X$ and convert it to input for $Y$

• $f$ must be computable, and a TM that halts on every input string $x$ and outputs $f(x)$ on its tape

Application:

• If $X \leq Y$

  • If $Y$ is decideable, then $X$ is decideable

  • If $X$ is undecideable, then $Y$ is also undecidable

  • If $Y$ is Turing-recognizeable, then $X$ is also (See $A_{TM}$)

  • If $X$ is Turing-unrecognizeable, then $Y$ is likewise

Example: $X = EQ_{DFA} = \left\{ \langle D_1, D_2 \rangle \right\}$, as well as $Y =$ Emptiness.

• Decider for $E_{DFA}$

• Input is Encoding of 2 DFAs

• Sub-machine/Mapping function:

  • Takes encoding, writes $\langle C \rangle$ for $Y$ – See previous proof of $EQ_{DFA}$

$Y = H_{TM}$, $X = A_{TM}$

• $X$ is proven to be undecideable

• Show $X$ is reducible to $Y$

• $X$'s decider takes an encoding of $\langle M, w \rangle$ and decides acceptance and rejection

• If $Y$ accepts, simulate $M$ on $w$, finally accepting if $M$ accepts, rejecting otherwise, including if $Y$ rejects

• Formally proven:

  • Assume, for a contradiction, assume that $HALT_{TM}$ is decidable and $Y$ is the decider for it.

  • Design a decider $X$ on input $\langle M, w \rangle$

    • Check validity of $\langle M, w \rangle$

      • Reject if invalid

    • Simulate $Y$ on $\langle M, w \rangle$

      • If $Y$ accepts, simulate $M$ on $w$

        • If $M$ accepts, accept.

        • If $M$ rejects, reject.

      • If $Y$ rejects, reject.

  • Then, $A_{TM}$ is decideable. $\textreferencemark$

  • Therefore, as the assumption is wrong, $HALT_{TM}$ is undecideable.

Mapping Reduction for the above

• Define $f$ such that if $Y$ rejects, $X$ rejects, if $Y$ accepts, $X$ accepts

• To be continued

If $X \leq 1$, and $X$ is undecideable, then $Y$ is undecideable.

$X = A_{TM}$, $Y = \overline{E_{TM}}$

• Proof. For the purpose of contradiction, assume that $Y$ is decideable, and we have a decider for it.

  • Then define $f$ taking input for $X$ and mapping it to input $Y$ (a decider for $X$)

  • Accept if decider for $Y$, accept, likewise for rejection

  • Most important step: Defining the Mapping

    • $\langle M, w \rangle \in A_{TM} \iff f(\langle M, w \rangle) = \langle T \rangle \in \overline{E_{TM}}$

      • In, $L(T) \neq \emptyset$, $\langle T \rangle$ is invalid

      • Not in, $L(T) = \emptyset$

    • Function $f$ as follows:

      • $$L(T) = \left\{ \begin{matrix} \neq \emptyset & M \text{accepts} w\\\emptyset & \text{otherwise}\end{matrix}\right.$$

    • $f$ outputs $\langle T \rangle$

    • Simulate decider for $\overline{E_{TM}}$ on $\langle T \rangle$

      • If accepts, accept; reject otherwise

  • $T$ works by taking any string, and simulates $M$ on $w$, accepting if accepts, rejecting if rejects. Looping if loop

$X = \overline{A_{TM}}$, $Y = EQ_{TM}$

• For the purpose of contradiction, assume $Y$ is recognizeable and we have a TM for $Y$

• Then $f$ goes from $\langle M, w \rangle$ to $\langle T_1, T_2 \rangle$

  • $T_1$

    • takes in $t_1$

    • Always rejects

  • $T_2$

    • takes in $t_2$

    • Simulate $M$ on $w$

      • Accept if accept

      • reject otherwise

• Contradiction, as $X$ is unrecognizeable

$W_{TM} = \{ \langle T \rangle | T\ \text{writes symbol}\ a\ \text{on the tape at some point}\}$

$A_{TM} \leq W_{TM}$

• Assume there exists a decider for $W_{TM}$

• Define mapping function $f$

  • $\langle T \rangle$ operates as follows:

    • Replace all instances of $a$ in $M$ with a different symbol (not otherwise in the alphabet), for instance $A$

    • Then, simulate $M$ on $w$

      • If $M$ accepts, write $a$ on the tape

      • Otherwise, write nothing on the tape

      • In all cases, accept/reject/loop as appropriate

Mappings map from $\langle M, w \rangle$ to $\langle T \rangle$

• Implementation may do various things

• including modifying the original encoding string

• And there are many possible mappings

• And may work by adding a new transition after replacing certain things

$A_{LBA}$ – acceptance of LBAs

LBA – Linear Bounded Automaton

• A modification of a turing machine with a limited and finite tape size

• tape is $n$ cells, where $n$ is the length of the input string

• Proof of acceptance (using decider)

  • Consider total number of configurations – $mg^nn$

    • $n$ is number of input symbols

    • $m$ is number of machine states

    • $g$ is number of tape symbols ($|\Gamma|$)

  • Simulate for $mg^nn$ steps

    • If $L$ accepts $w$, then accept

    • If $L$ rejects, reject

    • If $L$ does not stop within this number of steps, reject