1
$\begingroup$

Trivially decidable problem is one in which the problem is a known property of the language/grammar. So intersection of two regular languages is regular should be trivially decidable? But it is given as not trivially decidable.

$\endgroup$
6
  • $\begingroup$ What is the question? Whether the intersection of two regular langauges is regular? Why are you talking about decidability? $\endgroup$ Dec 18 '12 at 14:14
  • $\begingroup$ @ Andrej Bauer. we have to check whether the intersection of two regular languages is triavilly decidable problem or not? $\endgroup$ Dec 18 '12 at 14:40
  • 2
    $\begingroup$ The intersection of two regular languages is always regular, so deciding whether the intersection of two regular languages is regular is trivially decidable. Where is it given as not trivially decidable? $\endgroup$
    – Sam Jones
    Dec 18 '12 at 15:14
  • 1
    $\begingroup$ "Intersection of two regular languages" is not a problem, therefore you cannot talk about it being "trivially decidable". I take it you mean to consider the question "Is the intersection of two regular languages a regular language?". The answer is "yes". Therefore, it makes little sense to ask whether the question is "trivially decidable", unless you want to hear the following answer: yes, because the answer is yes. $\endgroup$ Dec 18 '12 at 16:10
  • $\begingroup$ @SamJones, Andrej Bauer both of you thanks $\endgroup$ Dec 18 '12 at 17:16
5
$\begingroup$

Summarizing the discussion, the intersection of two regular languages is always regular, and so "trivially decidable".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.