693 views
0 votes
0 votes

Q-1) What are the things that are not decidable about DCFL or DCFG? 


2)How complexity theory is related to formal langauages ,I know that pure complexity lies in decidable region but question like this confuses me : 
 

3) Apart from this this question : which asks which of them is polynomially decidable   :
 

4) And how we calculate the quotient and moreover question asks to draw the dfa for the same language,how to work with quotient .?

2 Answers

Best answer
2 votes
2 votes

1)it will answer all your questions for this part

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

2)

part a) Hope you know , we can only talk about complexity for some problem 'P' when we know that there exists an algorithm for problem 'P'.When there exists no algorithm for some problem , then can you tell complexity for such problem? No. iff some problem is decidable (REC)then there would exist some algorithm for such decidable problem.

So when we know RE languages are semi-decidable and if they're not decidable (means RE but not REC) then we can't talk about complexity for such problems. It's basic restriction with algorithm's definition that they must terminate after finite amount of time but in case of RE problems , there may exists an infinite loop and in such case there is no finite amount termination so Algorithm doesn't exists for RE but not REC problems.

part b)'Complexity' term is not defined for RE languages so option 'a' is out.Now as per my knowledge All P,NP,NPC problems can be decided by TM , so they all comes under REC languages.NPH can be decidable or undecidable.overall we can say if some algorithm is of exponential time complexity , it would be recursive.

3)Equivalence for DFA comes under P class , so yes! polynomially decidable. equivalence of two NFA comes under NPC class and equivalence for RE , is undecidable (not even RE).

4) Read peter linz.

selected by
1 votes
1 votes

1. For DCFL,the problems which are not decidable are : a) Subset problem (Is L1 is a subset of L2?)

                                                                                          b) Is L1 interection L2 = phi ?(Emptiness)

                                                                                          c) Is intersection of two langages of same type? (DCFL intersection DCFL)?

   For CFL ,the problems which are not decidable are:  a) Completeness b)Equality c) Subset d) Emptiness 

                                                                                        e) Complement is of same type or not?

                                                                                         f) Intersection is of same type or not?

2. Regular language : O(n)

    CFL : O(np)

    CSL : <= O(2n)

     REC: > O(2n)

     REL:  Complexity not defined

3.  According to me, all of them are polynomially decidable. But various places,I found that "When there are direct algorithms              present , then we can say that they are polynomially decidable" . By this , only 1st option seems correct.

4. In L1/L2 , U must write few  strings derivable from L1, and try to find quotient with each of the string of L2,U will definitely come      across a pattern or finite number of strings.

(I hope it might help u :) )

Related questions

1 votes
1 votes
0 answers
1
Nishtha3121996 asked Jan 14, 2018
602 views
IN L2 PROPER PREFIX MEANS THEY ARE NOT TAKING TRIVIAL STRING THAT IS EPSILON AND STRING ITSELF,CLARIFY IT