<p>It's well-known you can present <a href="http://en.wikipedia.org/wiki/Computation_history#Decidability_results">computation history</a> of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty word), and if there was an algorithm for your problem, you could tell those cases apart.</p>

CC BY-SA 3.0
2014-04-05T14:56:14.540Z
2014-04-05T14:56:14.540Z
sdcvvc
<p>this problem was <a href="https://cs.stackexchange.com/questions/23111/computing-the-intersection-of-two-npda-where-it-is-possible">asked</a> over a week ago on <a href="http://cs.stackexchange.com">cs.se</a> now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it to them. eg it is known that CFLs are not closed under intersection but thats not the immediate answer.) a proof is ok but also looking for ref(s) if known. analysis of nontrivial special cases also might be interesting. also a single non empty/non trivial example case has not been given so far (eg plz exclude both languages regular languages).</p>

<blockquote>
  <p>let $L_1, L_2$ be <a href="http://en.wikipedia.org/wiki/Context-free_language" rel="nofollow noreferrer">CFLs</a> and $L=L_1 \cap L_2$ is known to be a CFL. is there an algorithm for constructing $L$?</p>
</blockquote>

<reference-request><computability><automata-theory><context-free>
is determining an unknown CFL from intersection of two CFLs decidable?
vzn
# is determining an unknown CFL from intersection of two CFLs decidable?

(Asked by: username_0 on 2014-04-05)

this problem was [asked](https://cs.stackexchange.com/questions/23111/computing-the-intersection-of-two-npda-where-it-is-possible) over a week ago on [cs.se](http://cs.stackexchange.com) now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it to them. eg it is known that CFLs are not closed under intersection but thats not the immediate answer.) a proof is ok but also looking for ref(s) if known. analysis of nontrivial special cases also might be interesting. also a single non empty/non trivial example case has not been given so far (eg plz exclude both languages regular languages).

> let $L\_1, L\_2$ be [CFLs](http://en.wikipedia.org/wiki/Context-free_language) and $L=L\_1 \cap L\_2$ is known to be a CFL. is there an algorithm for constructing $L$?

**Tags:** reference-request, computability, automata-theory, context-free

---

## 1 answers

### Answer by username_1 on 2014-04-05. Score: 6 | Accepted answer

It's well-known you can present [computation history](http://en.wikipedia.org/wiki/Computation_history#Decidability_results) of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty word), and if there was an algorithm for your problem, you could tell those cases apart.


---

