Homework Assignment #1: Solutions

Contents

• Problem 1
• Problem 2
• Problem 3
• Problem 4
• Problem 5
• Problem 6
• Problem 7
• Problem 8
• Problem 9
• Problem 10

Problem 1:

In order to determine the cardinalities of the sets, you should use the rules which relate the cardinalities of the various set operators to the cardinalities of their operands. Note also that for disjoint sets A and B of finite cardinality, | A È B | = |A| + |B| . Note, on the other hand, that for any set A, | A È A | = | A | since of course A È A = A .

| (A È B) ´ B | = | (A È B) | ´ |B| = (|A| + |B|) | ´ |B| = (3 + 2) ´ 2 = 10		| A ´ (B È C) | = |A| ´ | (B È C) | = |A| ´ (|B| + |C|) = 3 ´ (2 + 4) = 18
| Ã(A) ´ B | = | Ã(A) | ´ |B| = ( 2 |A| ) ´ |B| = ( 2 3 ) ´ 2 = 16		| B ® (A È A) | = (| A È A |) |B| = |A| |B| = 3 2 = 9

Problem 2:

In order to characterize the cardinalities of sets in these broader terms, you need to understand the "arithmetic" of infinite quantities.

• | (A È B) ´ B |
  
  = | (A È B) | ´ |B|
  
  = (|A| + |B|) | ´ |B|
  
  = (finite + countably infinite) ´ countably infinite
  
  = countably infinite ´ countably infinite
  
  = countably infinite

• | A ´ (B È C) |
  
  = |A| ´ | (B È C) |
  
  = |A| ´ (|B| + |C|)
  
  = finite ´ (countably infinite + uncountable)
  
  = finite ´ uncountable
  
  = uncountable

• | Ã(A) ´ B |
  
  = | Ã(A) | ´ |B|
  
  = ( 2 ^|A| ) ´ |B|
  
  = ( 2 ^finite ) ´ countably infinite
  
  = finite ´ countably infinite
  
  = countably infinite

• | B ® (A È A) |
  
  = (| A È A |) ^|B|
  
  = |A| ^|B|
  
  = finite ^{countably infinite}
  
  = uncountable

Problem 3:

Perhaps the easiest way to do this problem is to count the relevant strings of a specific length, then add up all of these counts. When the length is less than 3, the substring issue is irrelevant. For a length of 0, there is 1 string (the empty string); for a length of 1, there are 3 strings; and for a length of 2, nine possible strings, since each "slot" in the string can be filled in one of three ways.

Beginning with strings of length 3, we need to consider also those strings which have "abc" as a substring and subtract them out of the count. Thus for a length of 3, there would be 27 strings, but we must subtract 1 to account for "abc", which is a substring of itself. For lengths of 4 and 5, notice that the substring "abc" can occur in several different ways. For example, for strings of length 5 we have patterns such as "_ _ abc", "_ abc _" and "abc _ _", where the underscores represent other letters. Each underscored slot can be filled in one of three ways, so for a length of 5 we have 3⁵ original candidates, minus 3 times 3² possibilities in which "abc" occurs as a substring, according to one of the three patterns. This leaves 243 - 27 = 216 strings of length 5. Similar calculations yield 81 - 6 = 75 strings of length 4.

Finally, when counting strings of length 6, we must remember not to count the string "abcabc" twice when subtracting out for strings with "abc" as a substring. In other words, this string fits both of the patterns "_ _ _ abc" and "abc _ _ _", but should only be counted once. This yields a total of 729 - (4 * 3³ - 1) = 729 - 107 = 622 strings of length 6.

The sum total is then 1 + 3 + 9 + 26 + 75 + 216 + 622 = 952 strings

Note: the following exercises and problems are from the textbook (on pages 83-90).

Exercises 1.2 (M₁ only):

M₁ = ( {q₁,q₂,q₃}, {a,b}, d, q₁, {q₂} ) where d is given by the following table:

d	a b
q1 q2 q3	q2 q1 q3 q3 q2 q1

Exercise 1.3:

The machine given can be nicely drawn as a series of states with q₃ in the middle and arranged as a "ladder". Then we can interpret "u" and "d" as up and down, for example as in the following diagram:

Exercise 1.4, parts (c) and (d):

The following diagram describes a machine which recognizes the given language with substring "0101". Note that if we fail to recognize a full substring "0101" in a left-to-right sweep, we must go back to the state which represents the best prefix we have nevertheless seen so far, if any. These considerations are handled by the back-looping transitions which go above and below the "main line".

This next diagram describes a machine which recognizes the given language with "0" occurring as the third symbol. The idea is that upon the third transition, a "0" takes us to a final state which we can loop back to on any symbol. Furthermore, a "1" transition will take us into a "sink hole". Note that we must see at least 3 symbols to end up in the final state.

Exercise 1.12, part (b):

In order to convert the given NFA to a DFA form, we let the state set of the new machine equal the set of subsets of the state set of the old machine (i.e., Q = {{},{1},{2},{3},{1,2},{2,3},{3,1},{1,2,3}}). Then we set the start state of the new machine equal to the set of states reachable by zero or more e-transitions from the old start state. Next we set the final states of the new machine to any state containing a final state of the old machine. And finally, we create the new transition function so as to take one state to another on a given symbol just when there existed a transition on that symbol from any state in the first set to any state in the second set in the old machine, including possible e-transitions.

For the given NFA, we get a DFA represented by the following state diagram:

We can further consolidate this machine by eliminating those states which are unreachable from the start state (since we can never reach them, they cannot affect the set of strings the machine will recognize).

Exercise 1.20:

A finite state transducer is a 5-tuple:

T = ( Q, S, G, d, q₀ )

• Q is a set called the set of states;
• S is a set of symbols, called the input alphabet;
• G is a set of symbols, called the output alphabet;
• d is a function called the transition function

  d : (Q ´ S) ® (Q ´ G)

• and q₀ is a member of Q called the start state.

Now given a finite state transducer T as described above and a string w = w₁, ..., w_n in S* and a string v = v₁, ..., v_n in G*, we say that T computes v from w just when there exists a sequence of states r₀, ..., r_n in Q* such that both of the following hold:

• r₀ = q₀ and
• for each i between 0 and n-1 (inclusive),

  d(r_i,w_i+1) = (r_i+1,v_i+1)

Exercise 1.22:

We can design a simple machine to effect this transformation as follows: it has two states, one for having read an even number of symbols and one for having read an odd number of symbols. On any transition it goes from one of these states to the other. Upon going from the even to the odd state, it inverts the input by emitting the opposite symbol from the one it has read. Upon going to the even state, it emits the same symbol that it has read.

This state diagram illustrates the machine:

Problem 1.24:

Read the textbook's definition of A^R as "the reverse of language A". Then we are asked to show that the reverse of any regular language is regular. Assume that we are given some regular language A; by the definition of regular language there must be some DFA M such that L(M) = A. We will construct a new DFA M' such that L(M') = A^R.

The basic idea is to reverse all of the arrows of the original machine, and to interchange initial and final states. Note however that this basic plan will not work directly, as it may introduce non-determinism (some arrows in the new machine may lead to several states on a given input), it may yield a partial transition function (there may be some states in the converted machine which have no transition defined on a given input symbol), and it may not yield a well-defined single initial state (since the original machine may have had several final states). Therefore in fact we will convert M into a NFA N, which we can then convert to the DFA M' using the usual techniques (i.e., those of Theorem 1.19).

This said, let

M = ( Q, S, d, q₀, F )

We define the NFA N as follows:

N = ( Q' , S, d', q_i, {q₀} )

where:

• q_i is a new initial state, not in the original Q;
• Q' = Q È {q_i};
• and the new transition function d' is defined (piece-wise) as follows:

  d'(q,a) = { r | d(r,a) = q } for all q in Q and a in S ;

  d'(q_i,e) = F ;

  d'(q,e) = {} for all q in Q ;

  d'(q_i,a) = {} for all a in S .

Without producing a rigorous proof by induction of the claim that N will recognize A^R, we can see informally that any sequence of states that will cause M to accept a string w will allow N to accept w^R. N can go by an epsilon transition from its new initial state to the correct final state of M and then by reversed transitions through the appropriate states until it reaches the now-final state of N (corresponding to the initial state of M). This plus the application of Theorem 1.19 completes the construction of a DFA M' which will recognize A^R and thus the proof.

Problem 1.29:

For each n, we can directly construct a DFA M_n which will recognize the language B_n. The idea is that the machine will have n states, and transitions on input symbol "a" leading in a circular fashion from the initial state, through each state in (ordinal) turn, until it finally returns from the last state to the initial state again. This last state will be the only final state in the machine.

Informally, if the machine reads a string of "a"s whose length is a multiple of n (including possibly 0 for the empty string), it will cycle through the n states exactly that multiple of times, thus ending up in the final (also initial) state. On the other hand, if it reads a string of "a"s whose length is not a multiple of n, then it will end up in some state other than the final one, and thus not accept the string.

More formally, we construct the machine M as follows:

M_n = ( Q , {a}, d, q₀, {q₀} )

where:

• Q = {q₀, ..., q_n-1};
• and the d is defined as follows:

  d(q_i,a) = q_i+1 for all i between 0 and n-1 (inclusive) ; and

  d(q_n-1,a) = q₀ .