83.9k views
4 votes
Give an example of a language L such that |L|=5 and |L^2|=16.

User Mikezang
by
5.4k points

1 Answer

5 votes

Answer:

He can define pas follows: Let P be defined on the set of languages accepted by some Turing machine M. Let it be True if 10 ] is 5 and False otherwise.

Step-by-step explanation:

The domain of P is the SD languages since it is those languages that are accepted by some Turing machine H. P is nontrivial since P({ a, aa, aaa, aaaa, aaaaa, aaaaaa, b, bb, bbb, bbbb, bbbbb, bbbbbb } ) is True and P ( 5 ) is False.

Thus {< M> is a Turing machine and I L I - 5 and I L I - 16 }

User Jason Plank
by
5.9k points