This page is located at http://www.cs.bc.edu/~alvarez/Theory/Exam1/practice1.html
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.
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.
c) The union of any twenty regular languages is also a regular language.
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.
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?
a) What language does this NFA recognize? Give a clear, unambiguous description.
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?
a) The set of w in {a,b}* that contain an even number of a's and an even number of b's.
b) The set of w in {0,1,2,3,4,5,6,7,8,9}* whose length is a power 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.
a) Find the language recognized by the DIA defined as follows.
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).