CS 3156 Section C, Fall 1998
Homework 1 -- due Friday, Oct. 2

1. Problem 0.7, page 26 of the text.

2. Prove that for any tex2html_wrap_inline161 and tex2html_wrap_inline54 ,

displaymath157

3. Let tex2html_wrap_inline165 be an alphabet of size s ( tex2html_wrap_inline60 ).

(a) How many strings of length n can be formed with symbols from tex2html_wrap_inline165 ?
(b) How many strings of length at most n can be formed with symbols from tex2html_wrap_inline165 ?

Justify your answers.

4. Let L be a language over some finite alphabet. The language tex2html_wrap_inline179 (read ``L star'') is defined by

displaymath158

Prove that tex2html_wrap_inline187 .

5. If tex2html_wrap_inline189 , the reverse of w, denoted by tex2html_wrap_inline193 , is tex2html_wrap_inline195 . For a language L, tex2html_wrap_inline199 . A string w is called palindrome if it is its own reverse, i.e., if tex2html_wrap_inline203 . A palindrome language is a language that contains only palindromes.

(a) Prove that if L is a palindrome language, then tex2html_wrap_inline209 .
(b) Prove or disprove: if tex2html_wrap_inline209 , then L is a palindrome language.

6. Problem 1.4(a,b,f,i,j), page 84 of the text.

Extra credit. You are employed by a toy company, and your boss thinks he has a great new idea. He dreams about selling sets of electronic toys that can play a simple war game. Each set will contain a ``general'', a ``lieutenant'', and a variable number of ``soldiers.'' The toys are to be arranged in a line, with the general at one end and the lieutenant at the other; each toy is able to exchange signals with the left and right neighbors only. When the general is touched, it sends a signal to the neighboring soldier. This signal has to be propagated to all soldiers in such a way that they all reach a certain state (``fire gun'') at the same time. Soldiers must be identical, and they start in the same initial state. The general and lieutenant can have a different diagram, however, all automata operate in sync: each of them reads the left and right input at the same time, does some processing, then sends signals to the left and right neighbors at the same time (the receive-process-send cycle takes one second).

How can you make the soldiers synchronize given the above restrictions? The problem would be trivial if there would be a direct wire from the general to any other soldier, or if the signal would propagate instantaneously from one soldier to another. It is also easy to design the soldiers if you know how many they are. But your design should work for any number of soldiers.

(a) Describe a deterministic finite state diagram for the operation of each soldier, as well as general and lieutenant state diagrams, such that their operation will give the desired result. Note that each transition in the soldier diagram has two inputs and two outputs. Technically, because of the output produced on transitions, these toys are not finite automata, but finite automata with output, or finite state transducers (see problem 1.19, page 87 of the text).

(b) Explain why your design works. If there are n soldiers, how many seconds must elapse between the moment the general is touched and the synchronous gun fire?