ME TEST TOC

Question

Comments

no incorrect ?

---

Both are false.

For 1st one see 1st question of this: https://courses.cs.washington.edu/courses/cse322/10sp/final-solutions.pdf

For 2nd see the same pdf question 1.d or see this: https://gateoverflow.in/156701/reducibility

---

1. NON RE $\cap$ REC = NON RE $\cap$ NON RE = NON RE we can say only it is non RE but cannont say always REC

---

it would be better if you can type questions because if anyone has the same problem then there is only searching required.

Answer 1

S1: FALSE.
A ∩ B can be empty which is finite. E.g.,
A=[-1,0] (set of all real numbers between -1 and 0) and
B= N, the set of natural numbers.

S2: FALSE
Given A ⊆ B, the we can assume that B= a^xb^yc^z where x,y,z are non-negative integers(which is Regular). Now assume another language A = a^nb^nc^n; n belongs to non-negative integer(which is CSL).
Clearly all the strings which follows A will be in the subset of strings generated by B. But we cannot make strings in A to be accepted by finite automata ,so A is not reducible to B. If it would be possible then surely FA would be enough to accept any CSL which is not correct...

Comments

perfect!