in Theory of Computation
584 views
0 votes
0 votes

Subset problem in undecidable for DCFL's , now consider the following argument given below.

G1 and G2 are DCFL,the algorithm to test whether L(G1) is a subset of L(G2) or not.

  1. Check for equivalence (L(G1)=L(G2)) ,if yes then we're done else go to Step 2
  2. Compute L= L(G1) ᑚ L(G2) and test whether L=L(G1) ?

the second step looks quite convincing and it seems like that the above procedure did solve the subset problem. So my question is that,if the above procedure is not correct how can i prove it ? 

in Theory of Computation
584 views

1 Answer

2 votes
2 votes
Best answer

Now, lets talk about property of DCFL.

1. DCFL are not closed under Intersection

https://gatecse.in/closure-property-of-language-families/

DCFL are closed under complementation and inverse homomorphism.

since they are not closed under intersection how could you decide whether the result of intersection of two dcfl are also dcfl.

selected by

1 comment

should've done my research first before asking the question.

thank you so much :)
0
0

Related questions