Register

test series

• edited by
309 views
0 votes
0 votes
Let A and B be disjoint, R.E. languages. Let (A∪B)'   also be recursive enumerable. What can you say about A and B?
(a) Neither A nor B is decidable is possible
(b) At least one among A and B is decidable
(c) Both A and B are decidable
(d) None of above
Solution: Option (c)

how?
• edited by
User Avatar

1 Answer

2 votes
2 votes

A and B are RE,    (AUB) Complement is RE 

(AUB) C = AC ∩ BC  ------> RE -------> Both AC  and BC are RE  // RE languages  are closed under intersection

Since RE languages are not closed under complementation ......Thus  If  A and AC  both are RE implies that A is Recursive (Decidable ), Similarly for B as well.

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

Related questions

350
views
1 answers
0 votes
tishhaagrawal asked Nov 26, 2023
350 views
Test Series: Is null string considered as a proper prefix of any string? According to me, total number of proper prefixes for n length string should be (n-1), can anyone please get this point cleared.
User Avatar
709
views
3 answers
1 votes
Akash Chakraborty asked Jul 13, 2023
709 views
Practice Test Series Question
User Avatar
379
views
1 answers
1 votes
Souvik33 asked Dec 4, 2022
379 views
TOC | Made Easy Test Series | Q.13
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
457
views
0 answers
0 votes
Pranavpurkar asked Nov 16, 2022
457 views
Test-Series
Consider the following language:$L$ $=$ { $<M>$ $|$ $L(M)$ has atleast $10$ strings }Which of the following is true about L?A)L is decidable ...
User Avatar
Link Copied!