Test by Bikram | Theory of Computation | Test 2 | Question: 17

Question

Match the following statements with True (T) / False (F) :

$S1: \ CFG = \{ <G> \mid \text{ G is a CFG and } L (G) = \Sigma ^* \} \text{ is undecidable}$
$S2: \ A = \{ <G> \mid \text{ G is a CFG over } \{0, 1\} ^*, 1 ^* \cap L( G) \neq \not{0} \} \text{ is undecidable}$
$S3: \ CFG = \{ <G,G'> \mid \text{ G,G' are CFG' s and } L (G) = L (G')\}  \text{ is undecidable}$
$S4: \ CFG= \{ ( <G> \mid \text{ G is a CFG and } L (G) = \not{0} \} \text{ is decidable}$

• A. S1 - T, S2 - T, S3 - T , S4 - T
• B. S1 - T, S2 - F, S3 - T , S4 - T
• C. S2 - T, S3 - F, S1 - T , S4 - T
• D. S1 - T, S2 - F, S3 - T , S4 - F

Comments

Sir,

reg intersect cfl = cfl,

but is cfl != phi decidable?

---

For S2,

1* ∪ CFL => CFL  and CFLs are decidable under emptiness problem. So whether cfl equal to ∅ or not is decidable..

---

@Bikram sir here i am considering 1*  as cfl  and in this case CFL1 ∩ CFL2  != PHI this is disjointness pro​​​​​​​perty o​​​​​​​f cfl and is undecidable in this case statement is true so​​​​​​​ why we are taking 1* as regular language as here we are talking about regular language