Register

Practice Question #1

199 views
0 votes
0 votes
A is given a recursive set L accepted by some LBA M & a homomorphism h.

Choose the correct statement,

1) It may not be possible to decide if L = ∅ but it is always possible to decide if h(L) = ∅.

2) It is undecidable if h(L) is R.E set.

3) The emptiness problem of h(L) is the same as the halting problem of T.M.

4) It is decidable if h(L) is finite or infinite.
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
0 answers
2
gauravkc asked Jan 29, 2018
1,019 views
Theory of Computation
Consider the homomorphism h(a) = 11 amd h(b) = 10. Consider the inverse homomorphism of the regular set (01+00)* a) The resulting set is empty b) The resulting set is 00* c) The resulting set is infinite d) None of the above How to solve this?
Consider the homomorphism h(a) = 11 amd h(b) = 10. Consider the inverse homomorphism of the regular set (01+00)*a) The resulting set is emptyb) The resulting set is 00*c)...
User Avatar
2 votes
2 votes
0 answers
4
Chhotu asked Nov 19, 2017
677 views
DCFL Inverse Homomorphism $H^{-1}(L)$ and Homomorphism $H(L)$ Closure ?
Hi Guys, Why is DCFL closed under Inverse Homomorphism $H^{-1}(L)$, But it not closed under Homomorphism $H(L)$ ?
Hi Guys,Why is DCFL closed under Inverse Homomorphism $H^{-1}(L)$, But it not closed under Homomorphism $H(L)$ ?
User Avatar
Link Copied!