College of Computer & Information Science Spring 2009 Northeastern University Handout 2 CSG714: Theory of Computation 9 January 2009

Problem Set 1 (due Friday, January 23)

1. (10 points) Neural nets and finite state automata

This problem is taken from the text by Aho, Hopcroft, and Ullman. Figure 1 depicts a neural network. Each neuron (the triangles depicted in the figure) has excitatory (clear circles) and inhibitory (filled circles) synapses. A neuron produces a 1-output if the number of excitatory synapses with 1-inputs exceeds the number of inhibitory synapses with 1-inputs by at least the threshold of the neuron (the number inside the triangle).

Determine a finite state automaton whose behavior is equivalent to that of the given neural network. The final states of the automaton correspond to a 1-output of the network. Assume that there is sufficient time between changes in input value for signals to propagate and for the network to reach a stable configuration. Assume that the initial values of x, y, and z are all 0.

Figure 1: A neural network.

2. (3 × 5 = 15 points) Number of states in FSAs

Consider the language L_{k} defined over the alphabet {0, 1}, for a given integer k > 0.

L_{k} = {w ∈ {0, 1}^{∗} : w has a 1 in the kth position from the end}.

(a) Describe an NFA for L_{k}, given integer k > 0.

(b) Describe a DFA for L_{k}, given integer k > 0. How many states does your DFA have?

(c) Show that the number of states in any DFA for L_{k} is exponential in k while there exists an NFA for L_{k} whose number of states is linear in k.

3. (2 × 7 = 14 points) Regular languages For each of the languages below, determine whether it is regular. Justify your answer.

(a) {uwu^{R} : u, w ∈ {0, 1}^{+}}.

(b) {uu^{R}w : u, w ∈ {0, 1}^{+}}.

4. (2 × 8 = 16 points) Context-free grammars Design a context-free grammar for each of the following languages over the alphabet {a, b, c}.

(a) Set of all strings with twice as many b’s as a’s.

(b) The set {a^{i}b^{j}c^{k} : i, j, k ≥ 0 and if i = 1 then j = k}.

5. (3 × 5 = 15 points) Context-free languages and PDAs

(a) Show that the following language is not context-free. {a^{i}b^{j}c^{k} : 0 ≤ i ≤ j ≤ k}

(b) Show that the following language is context-free, by constructing a (nondeterministic) PDA

that accepts the language.

{a^{n}b^{n} : n ≥ 1} ∪ {a^{n}b^{2n} : n ≥ 1}.

(c) Prove that there does not exist any deterministic PDA that accepts the language of (b). (Remark: This is a challenging problem. One approach in to argue that any DPDA cannot “differentiate” between all strings of the form a^{n}b^{n}. That is, for two such strings, it will end up in the same configuration. Then, argue that such a machine cannot possibly accept the above language.)