Question

Explain, or define, briefly but completely:

a.     If you are told that a language L is finite, what category(ies) is the language in? Why?

b.    State – carefully, completely -- the Church-Turing Thesis

c.      If you have an NDFA for L, how do you construct an NFA for L*? Describe in general but perhaps also illustrate with an example.

d.    If L = a*b*(ab)* what is PREFIX(L) = {x: x is a prefix of some string in L}?

e.     Define: A is mapping reducible to B (A <=_m B)

Answer 1

a) If L is finite, then L is a regular language. We can construct a regular expression to represent the finite language. If the finite language is composed of the strings s₁ , s₂ , … s_n, then it can be defined by the following regular expression

s₁U s₂U … U s_n .

If we are able to construct a regular expression for a language then that language is a regular language.

b) Church Turing Thesis

Church Turing Thesis states that "any computation that can be carried out by mechanical means can be performed by some Turing machine" otherwise it can also be stated as "a computation is mechanical if and only if it can be performed by some Turing machine".

This also tells that anything which can be done on any existing digital computer can also be done by turing machine.

c)

d) L = a*b*(ab)*

Strings of L = { epsilon, a, b, ab, abab, aa, bb, abab, aabbabab, aaab ...... }

Prefix of the string aabbabab will be a, aa, aab, aabb, aabba, aabbab, aabbaba.

e)