105 Practice Final Solution Outline

The following is a solution outline for the practice final. I did this quickly by your request so let me know before the weekend if there are any major gaffs! Please generate your own solutions before you look at these!

1. Consider the context-free grammar G=(V,T,P,S) where P is the set of productions:
S-->aB
B-->Sbb
S--> epsilon

• What is L(G)?
  L(G)={aⁿb²ⁿ| n greater than or equal to 0}.
• Is G a regular grammar? Why or why not?
  G is not a regular grammar. It is neither a right-linear nor a left-linear grammar.
• Transform G into a Chomsky Normal Form grammar G' which accepts L(G).
  G'=(VU{S'},T,P',S') with productions
  S' --> epsilon
  S' --> C_aB
  S --> C_aB
  B --> SD
  D --> C_b C_b
  C_a --> a
  C_b --> b
  B --> C_b C_b

2. Consider the PDA M=({q₀,q₁,q₂},{a},{A,B},delta,q₀,A,{q₀}) with instructions delta(q₀,a,A)={(q₁,BA)}, delta(q₁,a,B)={(q₀,epsilon)} and delta({q₁,epsilon,B)={(q₂,B)}.

• What is N(M)?
  N(M) is the empty set.
• What is L(M)?
  L(M) is (a²)*
• Is M deterministic? Why or why not?
  M is not deterministic since there are two instructions (delta(q₁,a,B) and delta(q₁,epsilon,B)) which can both be applied to the same configuration.

3. Fill in the following chart with Y if the set of languages in the row is closed under the property in the column and N if it is not.
Give a brief justification for 2 of your answers in each row.

	union	intersection	concatenation	complement
regular languages	Y	Y	Y	Y
context-free languages	Y	N	Y	N
recursive languages	Y	Y	Y	Y
r.e. languages	Y	Y	Y	N

The proofs for regular languages are shown in the book in section 3.2.

The Y proofs for for context-free languages are shown in section 6.2.

The N proof for the intersection of context-free languages is based on the following: L1 = {aⁱbⁱc^j} and L2 = {aⁱb^jc^j} are both CFLs but their intersection L3 = {aⁱbⁱcⁱ} is not a CFL by the pumping lemma for CFLs.

The N proof for the complement of a context-free language is based on the following: If context-free languages were closed under both union and complement then they would be closed under intersection. They are not closed under intersection and they are closed under union, so they must not be closed under complement.

The proofs for recursive languages are shown in the book in section 8.2. Intersection can be shown by constructing a machine which interleaves the computations of two machines. Concatenation can be shown by nondeterministically guessing the boundary between the end of the first substring of the concatenated string and the beginning of the second substring of the concatenated string. The "concatenation machine" executes the first machine on the first part and and the second machine on the second part. To be a concatenated string, both substring executions must terminate with a Y. Note that if an input string is a concatenation, some nondeterministic guess at the boundary will provide an accepting computation.

For r.e. languages, U and complement are covered in section 8.2. For concatenation, construct a 2 tape TM which nondeterministically guesses the boundary between the first and second substrings. Put the first string on the first tape and the second string on the second tape and interleave the execution of both machines. For intersection, you can also use a 2 tape turing machine. Copy the string on the second tape and interleave computations on the first and second tape. If the machine simulated by the first tape and the machine simulated by the second tape both accept, then make your constructed "intersection TM" accept the string.

4. Consider the language L={0ⁿ1ⁿ2ⁿ| n > 0}.

• Show that L is not context-free.
  This is shown in the book in section 6.1.
• Is L recursive? Why or why not?
  This language is recursive. Construct a TM which marks 0, shifts right to the first unmarked 1, marks it, shifts right to the first unmarked 2, marks it, and then returns to the first unmarked 0. The machine should check if equal numbers have been marked (i.e. is there anything left over) and accept if the input is of the right form. In any case, the machine will halt.
• Is L r.e.? Why or why not?
  Every recursive language is r.e.

5. Let M=({q₀},{1},{1,B},delta,q₀,B,F) be a Turing machine with instructions delta(q₀,1)=(q₀,1,R) and delta(q₀,B)=(q₀,B,R).

• What is L(M)?
  Woops! I never told you what F is. If F is the null set, then L(M) is the null set. If F is {q₀}, then L(M)=1*.
• Convert M to a TM M' accepting L(M) which halts iff it accepts. Describe M' by giving Q, SIGMA, GAMMA, delta, q₀ and F.
  If F is the null set then M already accepts w iff it halts on w. If F is nonempty, then construct M' with one extra instruction and one extra state q₁, i.e. M'=({q₀,q₁},{1},{1,B},delta', q₀, B, {q₁}). Let delta' be all current instructions with the addition of delta(q₀,B)={(q₁,B,R)}. Then M' accepts L(M) and halts on string w iff it accepts w.

6. What kind of machines accept r.e. languages?

Turing machines

Always halting Turing machines

The class of recursive languages is a subset of the class of r.e. languages.

The subclass is proper. The language L_u given in class is r.e. but not recursive.

7. Consider the following classes: recursively enumerable (r.e.) languages, languages accepted by deterministic FSAs, context-free languages (CFLs), recursive languages, all languages, regular langugages, deterministic context-free languages (DCFLs), languages accepted by DTMs.

Draw a diagram which shows the subset relationships between these languages.

I don't know enough html to do the diagram but ...

The set of all languages properly contains the set of r.e. languages
The set of r.e. languages properly contains the set of recursive languages
The set of recursive languages = the set of languages accepted by DTMs
The set of recursive languages properly contain the set of CFLs
The set of CFLs properly contain the set of DCFLs
The set of DCFLs properly contain the set of regular languages
The set of regular languages = the set of languages accepted by deterministic FSAs

For the given language classes, show by exhibiting particular languages, which subset relationships in the diagram are proper. For example, if you have claimed that language class A is a proper subset of language class B, then give an example of a language that is in class B but not in class A.

{aⁿb_n| n>0} is a DCFL but not regular
{ww^R| w in (0+1)*} is a CFL but not a DCFL
{a^p| p prime} is recursive but not a CFL
L_u is r.e. but not recursive
L_d is not r.e.

8. Show that it is undecidable to determine the following question: "Given TMs M₁ and M₂, is L(M₁)=L(M₂)?".

Here's an outline of the proof. Note that this is the same reduction proof as the one given in class except that this time we are using a different "known" undecidable problem.

Assume towards a contradiction that the language L₌={e(M1)e(M2)| M1 and M2 are TMs and L(M1)=L(M2)} is recursive, i.e. there exists an always halting turing machine M₌ which accepts L₌.

We'll construct an always halting TM which accepts L_emptystring={e(M)| M a TM and M accepts the empty string}. Since L_emptystring is not recursive, this will be a contradiction.

Given a TM M, we will construct a TM M' which does the following on input x:

• erase x
• execute M on the empty string
Note that L(M')= emptyset iff M accepts the empty string.

Let M₀ be a TM which doesn't accept anything, i.e. L(M₀)=emptyset.
Now we'll construct TM M'' which accepts L_emptystring. M'' takes as input e(M) and

• builds M' as described above.
• Computes the encoding e(M') of M' and forms e(M')e(M₀) where M₀ is the "empty set TM" defined above
• feeds e(M')e(M₀) as input to M₌.
• If M₀ halts with Y, then e(M') = the empty set which means that M does not accept the empty string.
  If M₀ halts with N, then e(M') does not = the empty set which means that M accepts the empty string.

Hence M'' is an always halting Turing machine which accepts L_emptystring. Contradiction.