Register

Interesting Problem of TOC Test Series

299 views

1 Answer

1 votes
1 votes

A) Computable Enumerable Languages

I'm guessing Computable Enumerable Languages are Recursively Enumerable Languages.

(I'm answering this according to a closure properties table given by Ravindrababu Ravula sir. Below is an explanation that I could find when I googled the same.)  

The Turing-recognizable (or recursively enumerable) languages are closed over homomorphism.

Consider the case where L is RE. Design a NTM M for H(L), as follows. Suppose w is the input to M. On a second tape, M guesses some string x over the alphabet of L, checks that H(x) = w, and simulates the TM for L on x, if so. If x is accepted, then M accepts w. We conclude that the RE languages are closed under homomorphism.

Source: University of Alabama Assignment 

Please correct me if I'm wrong. 

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

Related questions

1 votes
1 votes
1 answer
1
Souvik33 asked Dec 4, 2022
351 views
TOC | Made Easy Test Series | Q.13
Consider the following statement S: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFL The above statement is: TRUE FALSE
Consider the following statementS: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFLThe above statement is:TRU...
User Avatar
3 votes
3 votes
2 answers
2
srestha asked Apr 30, 2019
1,084 views
Made Easy Test Series:TOC-Turing Machine
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length}$P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on whi...
User Avatar
1 votes
1 votes
1 answer
3
srestha asked Apr 23, 2019
981 views
Made Easy Test Series:TOC-DFA
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________ Answer will be $3$ or $6?$
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________Answer will be...
User Avatar
0 votes
0 votes
0 answers
4
Vasu Srivastava asked Jul 14, 2017
569 views
Testbook Series TOC 2018 GATE
In the above, doesn't it also accepts empty string, and {a} or {b}? I think the answer there is wrong. Correct me if I am wrong. How is that they took different string here in the second one? z should be same, isn't it? Is PDA possible here? Isn't empty allowed?
In the above, doesn't it also accepts empty string, and {a} or {b}? I think the answer there is wrong. Correct me if I am wrong.How is that they took different string her...
User Avatar
Link Copied!