Scribd
Upload
19 views2 pages

Assignment 8 Solutions Overview

This document provides solutions to 4 exercises from a textbook. Exercise 1 involves determining whether certain automata belong to certain classes. Exercise 2 provides an algorithm to decide if an automaton belongs to the class ALLDF A . Exercise 3 describes two methods for enumerating the set of all triples of natural numbers. Exercise 4 explains how to construct an automaton that recognizes the reverse of the language of a given automaton, and uses this to decide if the automaton belongs to a certain class.

Uploaded by

Mauricio Flores
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

Assignment 8 Solutions Overview

This document provides solutions to 4 exercises from a textbook. Exercise 1 involves determining whether certain automata belong to certain classes. Exercise 2 provides an algorithm to decide if an automaton belongs to the class ALLDF A . Exercise 3 describes two methods for enumerating the set of all triples of natural numbers. Exercise 4 explains how to construct an automaton that recognizes the reverse of the language of a given automaton, and uses this to decide if the automaton belongs to a certain class.

Uploaded by

Mauricio Flores
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Solutions to Assignment 8

November 23, 2000

Exercise 1 (30 pts) Please do Exercise 4.1 on page 169 in the textbook.

Solution
1. Is hM, 0100i ∈ ADF A ? Yes.

2. Is hM, 011i ∈ ADF A ? No.

3. Is hM i ∈ ADF A ? No. The input is of a wrong format.

4. Is hM, 0100i ∈ AREX ? No. The input is of a wrong format.

5. Is hM i ∈ EDF A ? No. There exists a string (e.g., 0100) that is accepted by M .

6. Is hM, M i ∈ EQDF A ? Yes. M and M of course recognize the same language, namely, L(M ).

Exercise 2 (20 pts) Please do Exercise 4.3 on page 169 in the textbook.

Solution Here is a procedure that decides ALLDF A . Given a representation hAi of an automaton
A, we can construct an automaton B that recognizes L(A), that is, the complement of L(A). Since
EDF A is decidable, we can have an algorithm deciding whether hBi ∈ EDF A .
• If hBi ∈ EDF A , then L(B) = ∅. Hence, L(A) = Σ∗ , that is, hAi ∈ ALLDF A .

• If hBi 6∈ EDF A , then L(B) 6= ∅. Hence, L(A) 6= Σ∗ , that is, hAi 6∈ ALLDF A .

Exercise 3 (20 pts) Please do Exercise 4.8 on page 169 in the textbook.

Solution Let T be the set of triples {hi, j, ki | i, j, k ∈ N }. Here is a simple and intuitive method
to enumerate T . For each triple hi, j, ki, we call i + j + k the sum of the triple. For each natural
number n, we have only finitely many triples with sum equal to n. So we can first enumerate all
triples with sum 0, and then all triples with sum 1, and then all triples with sum 2, and so on. This
clearly allows us to enumerate all the triples in T .
A rigorous way to solve the problem is to construct a 1-1 and onto map f from T to N . This
can be done as follows. First, we know that P = {hi, ji | i, j ∈ N } is countable. For instance, one
can show that the function g(hi, ji) = (i + j)(i + j + 1)/2 + j is a 1-1 and onto map from S to N .
Let f (hi, j, ki) = g(hg(hi, ji), ki) for i, j, k ∈ N . We now show that f is a 1-1 and onto map from T
to N .
Assume that f (hi, j, ki) = f (hi0 , j 0 , k 0 i). Then g(hg(hi, ji, ki)) = g(hg(hi0 , j 0 i, k 0 i)). Since g is 1-1,
we have hg(hi, ji, ki) = hg(hi0 , j 0 i, k 0 i). Hence, g(hi, ji) = g(hi0 , j 0 i) and k = k 0 . Again, we have
hi, ji = hi0 , j 0 i since g is 1-1. Therefore, we have hi, j, ki = hi0 , j 0 , k 0 i, yielding that f is 1-1.

1
Given n ∈ N , we have g(hm, ki) = n for some m, k ∈ N since g is onto. Also we have g(hi, ji) =
m for some i, j ∈ N since g is onto. Therefore, we have f (hi, j, ki) = g(hm, ki) = g(hg(hi, ji), ki),
yielding that f is onto.

Exercise 4 (20 pts) Please do Exercise 4.19 on page 170 in the textbook.

Solution Let S = {hM i | M is a DFA that accepts wR whenever it accepts w}. We show that S is
decidable. Given hM i, which represents an automaton M , we can construct an automaton N such
that L(N ) = L(M )R , that is, N accepts a word w if and only if M accepts wR . Notice that this
claim follows from Exercise 1.24 on page 88 in the textbook.
Clearly, hM i ∈ S if and only if L(M ) = L(N ). Since EQDF A is decidable, there is an algorithm
deciding whether hM, N i ∈ EQDF A .

• If hM, N i ∈ EQDF A , we have L(M ) = L(N ). Therefore, hM i ∈ S.

• If hM, N i 6∈ EQDF A , we have L(M ) 6= L(N ). Therefore, hM i 6∈ S.

You might also like