Automata and Formal Languages

Question 1

Define a register machine. Explain what inputs are for a register machine.

Define the halting set.

Answer 1

A register machine R consists of
(i) A sequence of registers R_1, R_2, .., where at each time t, R_i(t) in N_0
(ii) A finite program. That is, a finite number of states S_0, …, S_n where S_0 = terminal, S_1 = start. Each state has an instruction (j, +, k) or (j, -, k, l).
(j,+,k) means add 1 to register j then go to STATE k.
(j,-,k,l) means if R_j!=0, subtract 1 from R_j and go to state k, otherwise go to state l.

An input is for some k>=1, a k-tuple (n_1,…, n_k) in N^k. Then set R_1=n_1,…,R_k=n_k,R_j=0 for all j>k.

Question 2

Define a partial function, a total function. What does it mean for a partial function to be computable by a program P?

Question 3

Define a partial recursive function. Prove that partial recursive implies partial computable.

Question 4

Prove that partial computable implies partial recursive

Question 5

What does it mean for a partial function to be recursive or computable? What does it mean for a set X in N^k to be recursive, computable, or decidable? What does it mean for a set to be recursively enumerable?

Question 6

What is meant by P_n. What is meant by f_{n,k}. Find a function that is not partial recursive.

Question 7

Properties of r.e. sets
Prove TFAE. In particular, prove that (b)==>(a).

(a) E is r.e., that is phi(n) = {1 if n in E, undefined else is partial recursive.
(b) E is the image of a partial recursive function on N^k
(c) E is the domain of a partial recursive function on 1-variable

(d) E is the image of an injective total recursive function. i.e., “E can be listed.”

Answer 7

Proof:

(a) ==>(c) is immediate
(a) ==>(b) Consider a register machine computing phi(n). Just add another register R_N, copy R_1 to R_N at the start, then copy R_N to R_1 just before halting. This gives phi’(n) = {n if n in E, 0 else. This implies (b)

(c) ==>(a) is immediate.
(b) ==>(a). Given program P_n, do the following process called Q. Given x in N for Q, run the zig-zag process (having ordered N^k) to compute f_n,k(.) for each input . Each time f_n,k(.) halts, compare the output to x, and halt if equal.
(a) ==>(d). We know E is the domain of a partial recursive function g. If E is finite, it is trivial. Let E be infinite. We begin a diagonal process which starts computing g(n) for each n. Then we define f(1) as the first n for which g(n) halts, f(2) as the second, and so on. Thus f is total recursive and has image d.

Question 8

Show that E is recursive iff E and N\E are re.

Answer 8

==> clear

<=== E and N\E are the domains of f and g resp. We can make f output 1 and g output 0. So simply define h(n) which is f(n) if it halts or g(n) if g halts (by going through the steps diagonally).

Question 9

What is W_n and how are they related to re sets?

Show that re unions of W_n is re and finite intersections are re.

Question 10

What is a universal program? Show that one exists.

Answer 10

A universal program can simulate any machine on any input.

We show there exists a partial recursive u s.t

u(n,k,m)= {r if n codes a program P_n, m codes a k-tuple (m_0,…,m_{k-1}) and f_{n,k}(m_0,…,m_{k-1) halts with r, and does not halt else}

Which is actually trivial.

Question 11

Define the halting set. Define K. Show that K is ri.e., but K, H are not recursive.

Answer 11

H = {(n,m): n codes a program and f_{n,1}(m) halts }

K = {n : n codes a program and f_{n,1}(n) halts}

N\K is not r.e. Suppose N\K= W_N for some N.

Then N in K iff f_N(N) halts iff N in W_N iff N not in K.

Question 12

Define the halting set. Define K. Show that K is ri.e., but K, H are not recursive.

Answer 12

H = {(n,m): n codes a program and f_{n,1}(m) halts }

K = {n : n codes a program and f_{n,1}(n) halts}

N\K is not r.e. Suppose N\K= W_N for some N.

Then N in K iff f_N(N) halts iff N in W_N iff N not in K.

Question 13

What does it mean for A to many to one reduce to B. Why is it called “many-to-one reduction”?
How is many-to-one reduction a useful notion in proving if a set is r.e. or recursive?

Answer 13

A in N many to one reduces to B in N if there is a total recursive function f : N–>N such that x in A iff f(x) in B. Thus the question of membership in A “reduces” to the question of membership in B in a many-to-one fashion, since potentially many x in A may map to the same f(x).

We denote it as A <= B, since B is in a since harder than A (solving membership in B solves A).

The following are clear, since given x in A, we may compute f(x) and then check membership in B.

1. If B r.e. then so is A
2. If B recursive, so is A

Also,

3. A <= B iff N\A <= N\B.

Question 14

State and prove the s-m-n theorem.

Answer 14

A partial function h : N^{m+n}–>N is partial recursive iff there exists a total recursive g : N^m –> N such that for all (e_1,…,e_m,x_1,…,x_n),
h(e_1,…,x_n)=f_{g(e_1,…,e_m),n}(x_1,…,x_n), where equality also extends to undefinedess (i.e., LHS defined iff RHS defined).

It’s actually trivial. For existence, we fix e_1,…,e_n and then we have an algorithm taking in (x_1,…,x_n) and outputting h(e_1,…,e_m, x_1,.., x_n), and so we can compute the code of this algorithm in a total way.

Conversely, if we have written h in this form, then it is partial recursive since we just have an algorithm which given e_1,…,x_n, first computes M = g(e_1,..,e_m). Then if M is defined, uses f_{M,n} on x_1,…,x_n.

Question 15

Explain why the halting set is the strongest r.e. set under many to one reductions.

Answer 15

We know that if X <= K, then X is r.e. (as K is).

Now suppose X is r.e. We very cleverly define f:N^2–>N such that

f(e, n) = { 1 if e in X, undefined else.

So f is r.e., and by the s-m-n theorem,

f(e,n)=f_{g(e),1)(n)

So e in X iff f_{g(e),1)(g(e)) halts iff g(e) in K, and so X <= K (!)

Question 16

State and prove the recursion theorem

Answer 16

For each total recursive h : N–>N, there exists n, f_{h(n),1}=f_{n,1} as functions.

Proof:
Recall u, the universal function u(n,k,m).
Let g(x,y)=u(h(u(x,1,3^x)),1,3^y).

Recall u(n,1,3^n)=f_{n,1}(n)

By s-m-n, g(x,y)=f_{f_{m,1}(x),1}(y), some m.
Let n=f_{m,1}(m).
We verify that f_{n,1}(y) = f_{h(n),1}(y) whenever f_{n,1}(y) halts.

Question 17

What is a property of re sets? What does it mean for a property to be r.e. or recursive? State and Prove Rice’s Theorem.

Answer 17

If C a non-trivial class of r.e. sets and

Question 18

Define a DFA and an NFA and the languages and extended transition functions

Answer 18

A DFA has (Q, delta, q_0, F)

Question 19

What is the subset construction? Show the equivalence of languages accepted by DFA’s and NFA’s.

Question 20

What are regular expressions?

Answer 20

Regular expressions are languages defined inductively as follows:

1. The empty language, and the language containing the empty word are regular
2. The language {a} is regular.
3. The union of languages L,M (denoted L+M) is regular
4. The concatenation LM is regular
5. The closure L* is regular

Question 21

Show that every regular language is the lanugage of an epsilon-NFA.

Answer 21

We build inductively eps-NFAs with one accept state, which is not he start state, no arcs out of the accept state and no arcs into the start state.

1. The basis languages are trivial.
2. For union, put them in parallel.
3. For concatenation, put them in series.
4. For closure, loop back to the start.

Question 22

Show that every DFA accepts a language which comes from a regular expression.

Question 23

Show that if L,R are regular languages, then

1. L U R is regular
2. LR is regular
3. The complement of L is regular
4. The intersection of L and R is regular.
5. L* is regular.
6. The reversal of L is regular (i.e., the accepted words are precisely the reverse of the words in L)

Question 24

State and Prove the Pumping Lemma for DFA’s.