in Theory of Computation recategorized by
692 views
1 vote
1 vote

Given below are two statements:

Statement $I$: The problem “Is $L_1 \wedge L_2 = \phi$?” is undecidable for context sensitive languages $L_1$ and $L_2$

Statement $II$: The problem “Is $W \in L$?” is decidable for context sensitive language $L$. (where $W$ is a string).

In the light of the above statements, choose the correct answer from the options given below

  1. Both Statement $I$ and Statement $II$ are true
  2. Both Statement $I$ and Statement $II$ are false
  3. Statement $I$ is correct but Statement $II$ is false
  4. Statement $I$ is incorrect but Statement $II$ is true
in Theory of Computation recategorized by
692 views

1 comment

  1. it is not re
0
0

1 Answer

0 votes
0 votes

Few Undecidable Problems for CFLs

L(G1) ∩ L(G2) = ∅  disjointness 

 L(G) = Σ*                universality

L(G)  Is Regular       regularity

L(G1) = L(G2)          equality ”

L(G) is ambiguous    ambiguity

The problem “Is W∈L?” is decidable for context sensitive language L. (where W is a string).

it is membership problem which is decidable for CFL 

Hence both statements are true option A is correct ans 

https://gatecse.in/grammar-decidable-and-undecidable-problems/

 

Answer:

Related questions