Log In
0 votes
intersection of two recursive lang is recursive

is this problem decidable or not?
in Theory of Computation 184 views
this is closure property of recursive languages so its always true and hence decidable.
Recursive languages are closed under Intersection. So that statement is always True which makes it decidable.

1 Answer

2 votes
Best answer

This is a trivial fact as it follows from closure property that intersection of two recursive language is a recursive language for sure..Hence we can say that this property is decidable..

In fact

Any closure property if satisfied for a given class of language and given operation, then the problem that the resultant language after applying that particular operation is also in the same class is  decidable..

selected by

Related questions

0 votes
1 answer
$L=\left \{< M_{1},M_{2}> \text{such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$
asked Jul 15, 2019 in Theory of Computation ajaysoni1924 243 views
0 votes
0 answers
0 votes
0 answers
From $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$ I was unable to get proof given in pdf above.Can anyone explain, if someone got it.
asked Jan 13, 2019 in Theory of Computation Ayush Upadhyaya 103 views
0 votes
1 answer
Let L be a DCFL and R is a regular language. Consider the below given problems. P : Is L ≠ R? Q : is R ⊂ L? Choose the correct option. Both problems P and Q are decidable. Both problems P and Q are undecidable. Problem Q is decidable and P is undecidable. ... for DCFL's, i.e when both languages are DCFL's. How do I analyze decidablity for different languages? In this case, for a RL and DCFL.
asked Jan 9, 2019 in Theory of Computation utkarshkosta 177 views