Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
What is the question? Whether the intersection of two regular langauges is regular? Why are you talking about decidability? – Andrej Bauer Dec 18 '12 at 14:14
@ Andrej Bauer. we have to check whether the intersection of two regular languages is triavilly decidable problem or not? – user1771809 Dec 18 '12 at 14:40
2  
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? – Sam Jones Dec 18 '12 at 15:14
1  
"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. – Andrej Bauer Dec 18 '12 at 16:10
@SamJones, Andrej Bauer both of you thanks – user1771809 Dec 18 '12 at 17:16
show 1 more comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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