Register

theory of computation

275 views
1 votes
1 votes

Consider the following statements:
S1: For any two sets A and B, if A is uncountably infinite and B is countably infinite, then A ∩ B is
countably infinite.
S2: For any two languages A and B, if A ⊆ B, then A is reducible to B.
The number of incorrect statements are _____.

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

0 votes
0 votes
0 answers
1
RahulVerma3 asked Apr 2
52 views
Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$? assuming $ at the end and begining of the input tape
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
User Avatar
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
160 views
Michael Sipster Theory of Computation
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.
User Avatar
Link Copied!