1
$\begingroup$

Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.

We want an algorithm which accepts GX and Gy as inputs. The algorithm will return true if the intersection of sets XS and YS is non-empty and will return false otherwise. We do not need to know exactly what the intersection is. It is possible that the intersection set is massive, so returning a container of all elements is unreasonable. Describing the intersection as a grammar is okay as long as it's apparent whether the grammar actually describes a non-empty set of string or not.

Just the name of the algorithm is fine if a Google search using that name will bring up the result. If the algorithm is obscure, additional information would be helpful.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

There is no such algorithm. Start by googling undecidability. The problem itself is called "language intersection/disjointness".

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$
    – xskxzr
    Jan 6, 2019 at 3:34
  • $\begingroup$ @xskxzr Thank you for your review. Yes it was meant as a comment, but ended up in the wrong box. I am happy you recognized the critique. I am confident that the added relevant information makes this an adequite answer. $\endgroup$
    – Hendrik Jan
    Jan 6, 2019 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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