Register

MadeEasy Subject Test 2017: Theory of Computation - Closure Property

• edited by
597 views
0 votes
0 votes

Consider the following statements:
S1: Complement of CSL is CSL.
S2: Complement of every turing recognizable language is turing recognizable.
S3: Turing decidable languages are closed under union and kleen start operation
The number of the above statements are wrong _______ .

I think the answer should be 0

My question is what is the difference between turing decidable and recognizable

• edited by
User Avatar

1 Answer

1 votes
1 votes
answer is 1

and complement of CSL is csl

turning decidable meanse halting TM

and turning recognizable means TM halts for ALL "yes" instances (word belonging to L) but may or may not halt for "no" instances.  i.e. RE languages
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Na462 asked Jan 13, 2019
1,053 views
MadeEasy Subject Test 2019: Theory of Computation - Closure Property
Consider the following Statements : There Exist a non-deterministic CFL whose reversal is DCFL. There exist a non regular CSL whose Kleene Closure is regular. Which of following are True ? Explain with reasons.
Consider the following Statements :There Exist a non-deterministic CFL whose reversal is DCFL.There exist a non regular CSL whose Kleene Closure is regular.Which of follo...
User Avatar
0 votes
0 votes
0 answers
3
Sambhrant Maurya asked Jan 9, 2019
525 views
MadeEasy Test Series: Theory Of Computation - Closure Property
L1 is regular, L2 and L3 are CFL L1 is regular, L2 is CFL and L3 is CSL L1 is CFL but not regular,L2 is CSL but not CFL,L3 is CFL L1, L2 and L3 are CFL
L1 is regular, L2 and L3 are CFLL1 is regular, L2 is CFL and L3 is CSLL1 is CFL but not regular,L2 is CSL but not CFL,L3 is CFLL1, L2 and L3 are CFL
User Avatar
0 votes
0 votes
2 answers
4
Dhoomketu asked May 10, 2018
604 views
Theory of computation - Closure Property
Cfl is closed under intersection with regular language. Then resultant languages will be regular or cfl ? Let X is cfl Y is regular language L=X intersection Y Then L is what?
Cfl is closed under intersection with regular language.Then resultant languages will be regular or cfl ?Let X is cflY is regular language L=X intersection YThen L is what...
User Avatar
Link Copied!