Register

Closure Properties Of Languages

582 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 ? 

User Avatar

1 Answer

Best answer
2 votes
2 votes

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
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
2
UltraRadiantX asked Oct 9, 2021
466 views
Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.
let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...
User Avatar
1 votes
1 votes
1 answer
3
vaishali jhalani asked Dec 14, 2016
784 views
regular languages closure properties
What is difference between Kleene closure and infinite union in context of regular languages?
What is difference between Kleene closure and infinite union in context of regular languages?
User Avatar
2 votes
2 votes
1 answer
4
eyeamgj asked Aug 18, 2018
1,407 views
closure properties of cfl
cfl are closed under a) min b)max c)half d)alt e)none of these cfl are not closed under init l/a cycle set diffeence
cfl are closed undera) min b)max c)half d)alt e)none of thesecfl are not closed under initl/acycleset diffeence
User Avatar
Link Copied!