consider two languages l1=(a*+b)* and l2=(a*b*)* what is the relationship between two languages
Answers
Answered by
25
Answer:
We have one to one mapping for all instances of L1 to L2.
L1 is given to be undecidable. Further L1 is polynomial time reducible to L2. (By given mapping). Now if L2 is decidable then there is algorithm to solve L2 in polytime. But then we can solve every instance of L1 in polytime, making L1 also decidable. Contradiction.
hope it is helpful
make me as brineliest
Answered by
10
Answer:
Simple. L1 = L2
Explanation:
This is a property of regular languages.
Similar questions