CS385, Theory of Computation
Practice Problems for the First Midterm Exam

This page is located at http://www.cs.bc.edu/~alvarez/Theory/Exam1/practice1.html

Solutions to selected problems to be discussed at the in-class review session

Note that previous problem sets provide great practice problems!

  1. For each of the following, determine whether the given statement is true or false. If you answer true, provide a proof of the statement. If you answer false, give a concrete counter-example and an explanation of why it contradicts the given statement. Note that unexplained answers will receive little or no credit on the midterm exam.

    a) For every NFA N, the powerset construction discussed in class produces a language-equivalent DFA M that has at most twice as many states as N.

    Solution

    False. The DFA that results from the construction has 2N states, a number that is greater than N whenever N ≥ 1.

    b) If L is a nonempty regular language, then there is a string w in L such that its n-fold concatenation wn is in L for every integer n ≥ 1.

    Solution

    False. Consider the language consisting of the single string cat, for example.

    Solution

    c) The union of any twenty regular languages is also a regular language.

    Solution

    True, because the union of any two regular languages is regular, Just pick a first language among the twenty, and repeatedly "add another language", invoking the regularity of the union of two regular languages at each step (induction).

    d) If A and B are both regular languages, then the set of all strings that belong to neither A nor B is also a regular language.

    Solution

    True, because the target language is the complement of the union of A, B. The union of two regular languages is regular and the complement of a regular language is regular (why?).

    e) If A is a non-regular language, then A U B must also be a non-regular language. Does it matter whether B is regular or not?

    Solution

    The original statement is false. For example, assuming A is non-regular, let A' be the complement of A, that is, the set of all finite strings (over the same alphabet) that do not belong to A. Then the union A U A' is the set of all finite strings over the given alphabet, which is regular. What if A is non-regular and B is regular? Well, the union could still be regular. For example, consider the case B = all finite strings, for which the union will also be the set of all finite strings. Another example is A = all strings of the form an bn, and B = all strings over {a,b} of even length.

  2. Consider the NFA described below.

    State space Q = {start, second, third}
    Alphabet Sigma = {a, b, c}
    Start state q0 = start
    Set of accepting states F = {third}
    Transition function delta given by (all values not shown are empty):
    delta(start, b) = {start, second}
    delta(start, a) = {start}
    delta(start, c) = {start}
    delta(second, a) = {third}
    delta(second, b) = {third}
    delta(second, c) = {third}

    a) What language does this NFA recognize? Give a clear, unambiguous description.

    Solution

    The above NFA recognizes the language of strings over {a,b,c} that contain the symbol b in the next-to-last position.

    b) Convert the above NFA to a language-equivalent DFA. Use the procedure discussed in class. Explain each step. How many states are accessible from the start state?

    Solution

  3. (Don't submit) Practice converting DFA and NFA to regular expressions. For instance, review example 1.36 and exercise 1.16 in the textbook.

  4. Regular, or not? Give a detailed explanation in each case.

    a) The set of w in {a,b}* that contain an even number of a's and an even number of b's.

    Solution

    Regular. Intersection of two regular languages (which ones? how to show that each of these two languages is regular? why is the intersection of two regular languages also regular?).

    b) The set of w in {0,1,2,3,4,5,6,7,8,9}* whose length is a power of 2.

    Solution

    Not regular. Pumping Lemma argument, as follows. If this language, call it P2, were regular, it would have some finite pumping length, p. Consider the string w that consists of precisely 2p 0's and no other symbols. Since 2p > p, this string w has length at least p. Also, w belongs to P2 since its length is a power of 2. Therefore, the Pumping Lemma assures us that there is a "good split" w = xyz such that
    • |xy| ≤ p
    • y ≠ ε
    • x yn z is in L for all non-negative integers n ≥ 0.
    However, we can show that any split that satisfies the first two of the above conditions will fail to satisfy the third one. Here goes. Let L = |y|. Then L ≠ 0 since y ≠ ε. The length of the pumped string x yn z is the same as the length of xyz yn-1, which is precisely 2p + (n-1)L. I claim that, for some non-negative integer value of n, this length is not a power of 2. Intuitively, this is because the distance between consecutive powers of 2 increases indefinitely the larger these powers are, while the distance between consecutive values of 2p + (n-1)L remains constant at exactly L for all values of n. Therefore, for a large enough value of n, the latter value will eventually fall into the ever-widening gap between consecutive powers of 2.

    Here is a more precise argument based on the above intuitive idea. Choose n = 1 + 2L. Then n > L. The length of x yn z is 2p + 2L L. This length is either a power of 2 or it isn't. If it isn't, we're done, as we've shown that one of the pumped strings is not in L, contradicting the third condition promised by the Pumping Lemma. Suppose, on the other hand, that the length 2p + 2L L is a power of 2, say:

    2p + 2L L = 2m,

    where m is necessarily larger than both p and L, and hence 2m is necessarily strictly greater than L in particular. I claim in this case that increasing n by one will yield a pumped string x yn+1 z the length of which is not a power of 2. To see this, note that increasing n by one will increase the length of the pumped string by precisely L, from 2m to 2m + L. On the other hand, the smallest power of 2 above 2m is 2m+1, which differs from 2m by exactly 2m. Since 2m > L, we see that 2m+1 > 2m + L, which shows that the pumped string has a length (equal to the term on the right in the latter inequality) that lies strictly below 2m+1, and therefore lies strictly between two powers of 2. This shows that the pumped string x yn+1 z fails to belong to the target language P2. This contradicts the conclusion of the Pumping Lemma for P2, which shows that our initial assumption that P2 is regular must be false.

    c) The set of w in {a,b,c}* that do not have abcab as a substring.

    Solution

    Regular. Complement of the regular language L( (a U b U c)*abcab(a U b U c)*) of all strings that do have abcab as a substring. Why is the complement of a regular language regular?

  5. Define a new machine model as follows. A Deterministic Infinite Automaton, or DIA, is a tuple I = (Q, Sigma, delta, q0, F) similar to a DFA except that the state space Q is allowed (but not required) to have infinitely many states. At each state, there should be exactly one exiting transition for each symbol of the alphabet. We'll require that the strings processed by DIA be of finite length. Every DFA may be considered to be a DIA in which the state space happens to be finite.

    a) Find the language recognized by the DIA defined as follows.

    State space Q = the set of all whole numbers (positive, 0, or negative)
    Sigma = {a, b}
    delta(n, a) = n+1 for every whole number n
    delta(n, b) = n-1 for every whole number n
    q0 = 0
    F = {5}

    Solution

    It is easy to see that this machine will be in state j at some point during a computation if and only if the portion of the input string that has already been processed has exactly "j more a's than b's" (j can be negative here, too, so I'm allowing for strings that have fewer a's than b's). The DIA described therefore recognizes the language of strings over the alphabet {a,b} that have exactly 5 more a's than b's.

    b) Are all languages recognized by DIA regular? if you answer yes, prove your claim by providing an airtight general argument. If you answer no, give a specific example of a DIA that recognizes a non-regular language (you'd also need to prove that the language recognized by your DIA is non-regular).

    Solution

    Of course not. The language recognized by the DIA in the previous subtask is not regular. Establishing the non-regularity of this language is a straightforward application of the Pumping Lemma. Don't take my word for it - do it!