AFL 1

Prove if X and Y are countable, then X x Y (set of ordered pairs) is also.

Assume both non-empty as else…, X and Y have surjections from N, so can use cantor’s zigzag bijection. n=z(I,j) then f(n):=(pix(i),piy(j))

Show if X (non-empty) is countable then X* is infinite and countable

For an element x in X, n→x^n maps N injectively, so infinite.

Each X^n is countable by induction and lemma (if X and Y are countable, then X x Y is also), so X* is countable union of countable sets

State Cantor’s Theorem

if X infinite, then the power set P(X) (set of all subsets of X) is uncountable.

Prove Cantor’s Theorem

Injection i:N→X, assume pi: N→P(X) a surjection. Define D:={i(n); i(n) not in pi(n)}, D is not in range of pi by contradiction

Prove if X is countable, then the set of finite subsets of X is countable.

WLOG X non-empty, let pi:N→X be surjection, X* countable, find surjection from X* to the set of finite subsets of X.

For alpha in X*, define f(alpha):=ran(alpha) be the set of all elements of X in alpha.

For F a subset of X, find pi(n_x)=x for minimal n_x for each x in F, {n_x; x in F} a finite set. Order by size (n0 <n1 <n2 etc). Define alpha by alpha(i):=pi(ni), then f(alpha)=F.

Define a rewrite system

A pair (Ω, P) is called a rewrite system if Ω is a non-empty finite set and P is a finite set of rewrite rules over Ω.

Prove if Ω is a non-empty finite set, then there are countably many rewrite systems on Ω.

Ω* countable (L1.2), so Ω+ x Ω* in Ω* x Ω* countable (L1.1). P a finite set of Ω+ x Ω*, so countable (P1.4)

Define a grammar over Σ

A grammar over Σ is a tuple (Σ,V,P,S) where Σ and V are non-empty and disjoint with Ω := Σ ∪ V and we have that S ∈ V and that (Ω,P) is a rewrite system. We call S the start symbol.

Define the language of a grammar G

L(G):={w∈Σ* ∣ S —-G→w} = W ∩ D(G, S)

Define an isomorphism between G and G′

Let Σ be an alphabet and let G = (Σ,V,P,S) and G′ = (Σ,V′,P′,S′) be two grammars over Σ. Let f : Ω → Ω′ be any function and extend it by recursion to Ω∗.

We say that f is an isomorphism between G and G′ if

(i) it is the identity on Σ,i.e.,f(a)=a for all a∈Σ;

(ii) f(S) = S′;

(iii) the restriction f↾V is a bijection between V and V ′; and

(iv) for each α,β∈Ω∗, we have α→β∈P if and only iff(α)→f(β)∈P′.

If there is an isomorphism between G and G′, we also say that the two grammars are isomorphic.

Prove isomorphic grammars are equivalent

If f an isomorphism, f^-1 an iso the other way. By symmetry, suff to show if f an iso then L(G) contained in L(G’).

This is true by 2,4,1 of isomorphism def. (S=σ0​⇒σ1​⇒σ2​⇒⋯⇒σn​=w, then f(S)=S′=f(σ0​)⇒f(σ1​)⇒⋯⇒f(σn​)=f(w))

Prove that for any fixed finite Σ and V , the set G(Σ, V ) is countable. Hence, also the set L(Σ, V ) is countable.

Let W be set of rewrite systems (Σ ∪ V, P ). By P1.6, W is countable and hence also V ×W is (L1.1).

The map (S,(Σ∪V,P)) → (Σ,V,S,P) is a surjection from V × W onto G(Σ, V ).

Since L(Σ,V) = all the languages generated by those grammars, and it's just the image of a countable set, it's also countable.

Prove if G = (Σ,V,P,S) is any grammar and |V′| = |V|, then there is a

grammar G′ = (Σ, V ′, P ′, S′) that is isomorphic to G.

extend the bijection f : V → V ′ to a bijection from Ω to Ω′ by letting it be the identity on Σ. define S′ := f(S) and P′ by property (iv). So extension of f to Ω is an isomorphism between G and G′

Show if |V | = |V ′|, then L(Σ, V ) = L(Σ, V ′).

Take any language L∈L(Σ,V) It's generated by some grammar G∈G(Σ,V).

p1.14 there's an isomorphic grammar G′∈G(Σ,V′). p1.12, G′ generates the same language.

• Every language generated using variables from V can also be generated using V′

• And vice versa (since the argument is symmetric)

Therefore:

L(Σ,V)=L(Σ,V′)

Prove that for any finite Σ, L(Σ) is countable.

L_n := L(Σ, V) for any |V|=n. By C1.15 (If |V | = |V ′|, then L(Σ, V ) = L(Σ, V ′)), this well-defined as only depends on size of V.

L(Σ)= union n>=1 of L_n. By L1.13 each is countable, so countable union of countable sets, so countable.

What is a noncontracting production rule? Context-free? Regular?

α → β is called noncontracting if |α| ≤ |β|.
A → β is called context-free if A ∈ V and |β| ≥ 1.
A → a and A → aB are called regular if A, B ∈ V and a ∈Σ.

Prove if G is noncontracting and w ∈ W, then there is a bound N depending only on |w| and |Ω| such that w ∈ L(G) if and only if w has a derivation of length at most N.

Assume w ∈ L(G) so can be derived from start symbol, assume derivation minimal of length n.

G non contracting, so intermediate strings nondecreasing.

For a given length m, only finite strings (|Ω|^m), so if longer length than this there’s a loop, but can just remove that section to give a shorter derivation.

Add up max possible steps to get N = sum from m=1 to |w| of |Ω|^m

Prove the word problem for noncontracting grammars is solvable.

Compute N = sum from m=1 to |w| of |Ω|^m and check all derivations up to length N, clearly finite and by L1.20, derivation has max length N, so will give a correct result (yes if w found, no if not).

Define concatenation, union, intersection, complement and difference

(a) Concatenation. The language LM consists of words vw such that v ∈ L and w ∈ M. (b) Union. The language L ∪ M consists of words either in L or in M .

(c) Intersection. The language L ∩ M consists of words that are both in L and M .
(d) Complement. The language L := W+\L consists of nonempty words that are not in L.

(e) Difference. The language L\M consists of words in L that are not in M.

Let C be a class of languages, give 4 conditions closed under and prove them.

Union and complementation → intersection

Intersection and complementation → union

Intersection and complementation → difference

If W+ ∈ C and closed under difference → complementation

Consequence of set algebra and De Morgan’s laws W+\(A ∩ B) = W+\A ∪ W+\B and W+\(A ∪ B) = W+\A ∩ W+\B.

Define variable-based for both a production rule and grammar.

A production rule is called variable-based if its left-hand side does not contain any letters. A grammar is called variable-based if all of its rules are variable-based.

Prove for every grammar, there is a variable-based grammar that is equivalent to

it.

Add variable X_a, X_b,… where Σ={a,b,…}. Replace each terminal with corresponding variable, call this process X(α), and add the rules X_a→a for each new variabl.