# 2.11. cs theoryÂ¶

Some notes on theoretical computer science, based on UVAâs course.

## 2.11.1. introductionÂ¶

Chomsky hierarchy of languages: \(L_3 \subset L_2 \subset L_1 \subset L_R \subset L_0 \subset ÎŁ*\)

each L is a set of languages

\(L_0=L_{RE}\) - unrestricted grammars - general phase structure grammars - recursively enumerable languages - include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine.

computable, maybe undecidable (if not in L_R)

L_R - recursive grammars - Turing machine that halts eventually

decidable

L_1 - context-sensitive grammars - all languages that can be recognized by a linear bounded automaton

L_2 - context-free grammars - these languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton.

L_3 - regular grammars - all languages that can be decided by a finite state automaton

contains ÎŁ*, \(\vert ÎŁ*\vert \) is countably infinite

strings

languages

ÎŁ* Kleene Closure has multiple definitions

{w \(\vert \) w is a finite length string ^ w is a string over ÎŁ}

{xw \(\vert \) w in ÎŁ* ^ x in ÎŁ} U {Æ}

ÎŁ_i has strings of length i

problems

automata

delta v delta-hat - delta hat transitions on a string not a symbol

\(\vert \)- notation writes the state between the symbols you have read and have yet to read

\(\vert \)- notation with * writes the state before the symbols you have to read and after what you have read

grammars

leftmost grammar - expand leftmost variables first - doesnât matter for context-free

parse tree - write string on bottom

sets

finite

countably infinite

not countably infinite

mappings

onto - each output has at least 1 input

1-1 - each output has at most 1 input

total - each input has at least 1 output

function - each input has at most 1 output

equivalence relation - reflexive, symmetric, transitive

proof methods

**read induction **

library of babel

distinct number of books, each contained, but infinite room

## 2.11.2. ch 1-3 - finite automata, regular expressionsÂ¶

alphabet - any nonempty finite set

string - finite sequence of symbols from an alphabet

induction hypothesis - assumption that P(i) is true

lexicographic ordering - {Æ,0,1,00,01,10,11,000,âŠ}

finite automata - like a Markov chain w/out probabilities - 5 parts

states

E - finite set called the alphabet

f: Q x E -> Q is the transition function

ex. f(q,0) = qâ

start state

final states

language - L(M)=A - means A is the set of all strings that the machine M accepts

A* = {\(x_1x_2...x_k \vert k\geq0 \wedge x_i \in A\)}

A+ = A* - Æ

concatenation A o B = {xy \(\vert \) x in A and y in B}

regular language - is recognized by a finite automata

class of regular languages is closed under union, concatenation, star operation

nondeterministic automata

can have multiple transition states for one symbol

can transition on Æ

can be thought of as a tree

After reading that symbol, the machine splits into multiple copies of itself and follows all the possibilities in parallel. Each copy of the machine takes one of the possible ways to proceed and continues as before. If there are subsequent choices, the machine splits again.

If the next input symbol doesnât appear on any of the arrows exiting the current state, that copy of the machine dies.

if any copy is in an accept state at the end of the input, the NFA accepts the input string.

can also use regular expressions (stuff like unions) instead of finite automata

to convert, first convert to gnfa

gnfa (generalized nfa) - start state isnât accept state

nonregular languages - isnât recognized by a finite automata

ex. C = {w \(\vert \) w has an equal number of Os and 1s}

requires infinite states

## 2.11.3. ch 4 - properties of regular languages (except Sections 4.2.3 and 4.2.4)Â¶

pumping lemma- proves languages not to be regular

if L regular, there exists a constant n such that for every string w in L such that \vert w\vert â„ n, we can break w into 3 strings w=xyz, such that:

yâ Æ

\(\vert xy\vert \) â€ n

For all k â„ 0, x y^k z is also in L

closed under union, intersection, complement, concatenation, closure, difference, reversal

convert NFA to DFA - write the possible routes to the final state, write the intermediate states, remove unnecessary ones

minimization of DFAs

eliminate any state that canât be reached

partition remaining states into blocks so all states in same block are equivalent

canât do this grouping for nfas

## 2.11.4. ch 5 - context free grammars and languagesÂ¶

\(w^R\) = reverse

context-free grammar - more powerful way to describe a language

ex. substitution rules (generates 0#1)

A -> OA1

A -> B

B -> #

def

variables - finite set

terminals - alphabet

productions

start variable

recursive inference - start with terminals, show that string is in grammar

derivation - sequence of substitutions to obtain a string

can also make these into parse trees

leftmost derivation - at each step we expand leftmost variable

arrow with a star does many derivations at once

parse tree - final answer is at bottom

sentential form - the string at any step in a derivation

proofs in 5.2s

w equivalence

parse tree

leftmost derivation

rightmost derivation

recursive inference

derivation

if else grammar: \(S \to \epsilon \vert SS \vert iS \vert iSeS \)

context-free grammars used for parsers (compilers), matching parentheses, palindromes, if-else, html, xml

if a grammar generates a string in several different ways, we say that the string is derived ambiguously in that grammar

ambiguity resolution

some operators take precedence

make things left-associative

think about terms, expressions, factors

if unambiguous, leftmost derivation will be unique

in an unambiguous grammar, leftmost derivations will be unique

inherently ambiguous language - all its grammars are ambiguous

ex: \(L = {a^nb^nc^md^m} \cup {a^nb^mc^md^n} , n \geq 1, m\geq1\)

## 2.11.5. ch 6 - pushdown automata (donât need to know 6.3 proofs)Â¶

pushdown automata - have extra stack of memory - equivalent to context-free grammar

similiar to parser in typical compiler

two ways of accepting

entering accept state

accept by emptying stack

convert from empty stack to accept state

add symbol X_1

start by pushing it onto the stack then push on Z_1, spontaneously transition to q_0

everything has epsilon-transition to final accepting state when they read X_1

convert accept state to empty stack

add symbol X_1 under Z_1 (this is so we never empty stack unless we are in p- there are no transitions on X_1)

all accept states transition to new state p

p epsilon-transitions to itself, removes element from each stack every time

6.3

convert context free grammar to empty stack

simulate leftmost derivations

put answer on stack, most recent variable on top

if terminal remove

if variable nondeterministically expand

if empty stack, accept

convert PDA to grammar

every transition is of from pXq

variables of the form [pXq] (X is on the stack)

[pXq] -> a where a is what transitioned p to q

pushdown automata can transition on epsilon

def:

transition function - takes (state,symbol,stack symbol) - returns set of pairs (new state, new string to put on stack - length 0, 1, or more)

start state

start symbol (stack starts with one instance of this symbol)

set of accepting states

set of all states

alphabet

stack alphabet

ex. palindromes

push onto stack and continue OR

assume we are in middle and start popping stack - if empty, accept input up to this point

label diagrams with i, X/Y - what input is used and new/old tops of stack

ID for PDA: (state,remaining string,stack)

conventionally, we put top of stack on left

parsers generally behave like deterministic PDA

DPDA also includes all regular languages, not all context free languages

only include unambiguous grammars

## 2.11.6. ch 7 - properties of CFLsÂ¶

Chomsky Normal Form

A->BC

A->a

no epsilon transitions

for any variable that derived to epsilon (ex. A -*> epsilon)

if B -> CAD

replace with B -> CD and B -> CAD and remove all places where A could become epsilon

no unit productions

eliminate useless symbols

works for any CFL

Greibach Normal Form

A->aw where a is terminal, w is string of 0 or more variables

every derivation takes exactly n steps (n length)

generating - if x produces some terminal string w

reachable - x reachable if S \({\to}^*\) aXb for some a,b

CFL pumping lemma - pick two small strings to pump

If L CFL, then \(\vert z\vert \geq n\), we can break z into 5 strings z=uvwxy, such that:

vx â Æ

\(\vert vwx\vert \leq n\), middle portion not too long

For all i â„ 0, \(u v^i w x^i y \in\) L

ex. \(\{0^n1^n\}\)

often have to break it into cases

proof uses Chomsky Normal Form

not context free examples

\(\{0^n1^n2^n\vert n\geq1\}\)

{\(0^i1^j2^i3^j\vert i\geq 1,j\geq 1\)}

{ww\(\vert w \in \{0,1\}^*\) }

closed under union, concatenation, closure, and positive closure, homomorphism, reversal, inverse homomorphism, substitutions

intersection with a regular language (basically run in parallel)

not closed under intersection, complement

substitution - replace each letter of alphabet with a language

s(a) = \(L_a\)

if \(w = ax\), \(s(w) = L_aL_x\)

if L CFL, s(L) CFL

time complexities

O(n)

CFG to PDA

PDA final state -> empty stack

PDA empty stack -> final state

PDA to CFG: O(\(n^3\)) with size O(n^3)

converstion to CNF: O(n^2) with size O(n^2)

emptiness of CFL: O(n)

testing emptiness - O(n)

which symbols are reachable

test membership with dynamic programming table - O(n^3)

CYK algorithm

## 2.11.7. ch 8 - intro to turing machines (except 8.5.3)Â¶

Turing Machine def

states

start state

final states

input symbols

tape symbols (includes input symbols)

transition function \(\delta(q,X)=\delta(q,Y,L)\)

B - blank symbol

infinite blanks on either side

arc has X/Y D with old/new tape symbols and direction

if the TM enters accepting state, it accepts

assume it halts if it accepts

we can think of Turing machine as having multiple tracks (symbol could represent a tuple like [X,Y])

multitape TM has each head move independently, multitrack doesnât

common use one track for data, one track for mark

running time - number of steps that TM makes

NTM - nondeterministic Turing machine - accepts no languages not accepted by a deterministic TM

halts if enters a state q, scanning X, and there is no move for (q,X)

restrictions that donât change things

tape infinite only to right

TM canât print blank

simplified machines

two stacks machine - one stack keeps track of left, one right

every recursively enumerable language is accepted by a two-counter machine

TM can simulate computer, and time is some polynomial multiple of computer time (O(n^3))

limit on how big a number computer can store - one instruction - word can only grow by 1 bit

LBA - linear bounded automaton - Turing machine with left and right end markers

programs might take infinitely long before terminating - canât be decided

turing machine can take 2 inputs: program P and input I

ID - instantaneous description

write \(X_1X_2...qX_iX_{i+1}...\) where q is scanning X_i

program that prints âhâ as input -> yes or no

imagine instead of no prints h

now feed it to itself

if it would print h, now prints yes - paradox! therefore such a machine canât exist

TM simulating computer

tape that has memory

tape with instruction counter

tape with memory address

reduction - we know X is undecidable - if solving Y implies solving X, then Y is undecidable

if X reduces to Y, solving Y solves X

define a total mapping from X to Y

\(X \leq _m Y\) - X reduces to Y - mapping reduction, solving Y solves X

intractable - take a very long time to solve (not polynomial)

<> notation means bitstring representation

\(<n> = 0^n\)

\(<m,w> means w \in L(M)\)

KD - âknown to be distinctâ

idempotent - R + R = R

## 2.11.8. ch 9 - undecidability (9.1,9.2,9.3)Â¶

does this TM accept (the code for) itself as input?

enumerate binary strings - add a leading 1

express TM as binary string

give it a number

TM uses this for each transition

separate transitions with 11

diagonalization language - set of strings w_i such that w_i is not in L(M_i)

make table with M_i as rows, w_j as cols

complement the diagonal is characteristic vector in L_d

diagonal canât be characteristic vector of any TM

not RE

recursive - complement is also recursive

just switch accept and reject

if language and complement are both RE, then L is recursive

universal language - set of binary strings that encode a pair (M,W) where M is TM, w \(\in (0+1)^*\) - set of strings representing a TM and an input accepted by that TM

there is a universal Turing machine such that L_u = L(U)

L_u is undecidable: RE but not recursive

halting problem - RE but not recursive

Riceâs Thm - all nontrivial properties of the RE languages are undecidable

property of the RE languages is a set of RE languages

property is trivial if it is either empty or is all RE languages

empty property \(\emptyset\) is different from the property of being an empty language {\(\emptyset\)}

ex. âthe language is context-free, empty, finite, regularâ

however properties such as 5 states are decidable

## 2.11.9. Ch 10 - 10.1-10.4 know the additional problems that are NP-completeÂ¶

intractable - canât be solved in polynomial time

NP-complete examples

boolean satisfiability

symbols ^-, etc. are represent by themselves

x_i is represented by x followed by i in binary

Cookâs thm - SAT is NP-complete

show SAT in NP

show all other NP reduce to SAT

pf involves matrix of cell/ID facts

cols are ID 0,1,âŠ,p(n)

rows are alpha_0,alpha_1,âŠalpha_p(n)

for any problemâs machine M, there is polynomial-time-converter for M that uses SAT decider to solve in polynomial time

3SAT - easier to reduce things to

AND of clauses each of which is the OR of exactly three variables or negated variables

conjunctive normal form - if it is the AND of clauses

conversion to cnf isnât always polynomial time - donât have to convert to equivalent expression, just have to both be satisfiable at the same times

push all negatives down the expression tree - linear

put it in cnf - demorgans, double negation

literal - variable or a negated variable

k-conjunctive normal form - k is number of literals in clauses

traveling salesman problem - find cycle of weight less than W

O(m!)

Independent Set - graph G and a lower bound k - yes if and only if G has an indpendent set of k nodes

none of them are connected by an edge

reduction from 3SAT

node-cover problem

node cover - every node is on one of the edges

Undirected Hamiltonian circuit problem

TSP with all weights 1

Directed Hamiltonian-Circuit Problem

subset sum

is there a subset of numbers that sums to a number

reductions must be polynomial-time reductions

P - solvable in polynomial by deterministic TM

NP - solvable in polynomial time by nondeterministic TM

NP-completeness (Karp-completeness) - a problem is at least as hard as any problem in NP = for every language Lâ in NP, there is a polynomial-time reduction of Lâ to L

Cook-completeness equivalent to NP-completeness - if given a meachansim that in one unit of time would answer any equestion about membership of a string in P, it was possible to recognize any language in NP in polynomial time

NP-hard - we donât know if L is in NP, but every problem in NP reduces to L in polynomial time

if some NP-complete problem p is in P then P=NP

there are things between polynomial and exponential time (like 2^logn), and we group these in with the exponential category

could have P polynomials run forever when they donât accept

could simply tell them to stop after a certain amount of steps

there are algorithms called verifiers

## 2.11.10. more on NP CompletenessÂ¶

a language is polynomial-time reducible to a language B if there is a polynomial time comoputable function that maps one to the other

to solve a problem, efficiently transform to another problem, and then use a solver for the other problem

satisfiability problem - check if a boolean expression is true

have to test every possible boolean value - 2^n where n is number of variables

this can be mapped to all problems of NP

ex. traveling salesman can be reduced to satisfiability

P - set of all problems that can be solved in polynomial time

NP - solved in polynomial time if we allow nondeterminism

we count the time as the length of the shortest path

NP-hard problem Lâ

every L is NP reduces to Lâ in polynomial time

NP-complete Lâ

Lâ is NP-hard

Lâ is in NP

ex. graph coloring

partitioning into equal sums

if one NP-complete problem is in P, P=NP

decider vs. optimizer

decider tells whether it was solved or not

if you keep asking it boolean questions it gives you the answer

graph clique problem - given a graph and an integer k is there a subgraph in G that is a complete graph of size k

this is reduction from boolean satisfiability

graph 3-colorability

reduction from satisfiability - prove with or gate type structure

approximation algorithms

find minimum

greedy - keep going down

genetic algorithms - pretty bad

minimum vertex cover problem - given a graph, find a minimum set of vertices such that each edge is incident to at least one of these vertices

NP-complete

can not be approximated within 1.36*solution

can be approximated within 2*solution in linear time

pick an edge, pick its endpoints

put them in solution

eliminate these points and their edges from the graph

repeat

maximum cut problem - given a graph, find a partition of the vertices maximizing the number of crossing edges

can not be approximated within 17/16*solution

can be approximated within 2*solution

if moving arbitrary node across partition will improve the cut, then do so

repeat