Q1. Let ∑ = {0,1}. Define the following language:
L = {x | x contains an equal number of occurrences of 01 and 10}
Either prove L is regular (by constructing a DFA/NFA or a regex) or prove that it is not regular using the Pumping Lemma for regular languages.
Q2. Given languages L, L' (over ∑ ), define the shuffle of L, L' to be
Shuffle(L, L') = {x_{1}y_{1}x_{2}y_{2}......x_{n}y_{n }| x_{i} ∈ L and y_{i} ∈ L' for i = 1,......, n}
Suppose that M = ( ∑, Q, q_{0},δ, F) is a DFA for L and M0 = (∑ ,Q', q_{0}',δ', F') is a DFA for L'. Construct an NFA that accepts Shuffle(L).
[This proves that Shu e is a closed regular operator, i.e., this proves that if L; L0 are regular, then Shu e(L; L0) is also regular.]
Q3. Let ∑={a, b, c}. Prove that the following language (defined over)
L = {uvuvu | u ∈ {a, b}* ; v ∈ {b; c}*} is not regular.
[HINT: Clean up and then use the pumping lemma for regular languages.]
Q4. Prove that the following languages are context-free by constructing the a context-free grammar for L_{1} and a push-down automata for L_{2}.
(a) L1 = {a^{m}b^{m}c^{n} | m ≥ 0, n ≥ 0}
(b) L2 = {a^{m}b^{n}c^{n} |m ≥ 0, n ≥ 0}
Finally:
(c) What is L1 ∩ L2? [Use set notation.]
(d) TRUE or FALSE: The intersection of any two context-free languages gives a context- free language.
Q5. Prove that
L = {a^{m}b^{n} |m ≠ n and 2m ≠ n}
is a context-free language.
Q6. Suppose L is a context-free language and L' is regular. Show that L ∩ L' is a context- free language. Specifically, if you're given a PDA diagram of L and a DFA diagram for L',describe informally how to draw a PDA diagram for L ∩ L'.
[... it's even better if you can describe the construction of L∩L' formally but you don't have
to.]
Q7. (a) A Turing machine M is considered a DFA1 if the read/prepare head always moves to the right and it halts (i.e., enters its q_{accept} or q_{reject}) when it reads a space (or blank) character on the input tape. Note that a DFA1 is like a DFA except that it must have exactly 1 accept state. (A DFA can have any number of accept states.) Is the following language:
Accept_{DFA1} = {#| M is a DFA1 and accepts w}
a Turing{decidable language? If it is, describe clearly how to construct a Turing decider (i.e.,a Turing machine that always halts) that accepts the language. Otherwise prove that it's not decidable.
(b) Consider the following language:
NonEmpty_{TM} = {#| M is a Turing machine and L(M) ≠0}
Is NonEmpty_{TM} a Turing-decidable language?
[This is the only TM problem but it actually requires very little TM knowledge. You have everything you need to solve this problem if have a general understanding of TMs and you have paid attention to the Wednesday and Friday classes during the last week.]
Q8. This is the problem for the second version of the final exam. You only need to attempt one of the three parts. Do not turn in any work for Q1-Q7 if you plan to turn in work for Q8, or you will get an immediate 0.
1. Given two words x,y ∈ ∑* , a DFA M separates x, y if L accepts either x or y but not both. What is the smallest number of states you need to construct a DFA that can separate any pair of distinct words of length ≤ n?
2. Consider the following problem: Given a PDA M and an integer n, is it true that ∑^{n} ⊆ L(M)? The corresponding language is L = {#| M is a PDA and ∑^{n} ⊆ L(M)} Is L regular, context-free, Turing{decidable, Turing{recognizable, not Turing{recognizable?
3. Either prove P = NP or P ≠ NP.