All Questions
Tagged with context-free computability
4 questions
6
votes
1
answer
2k
views
Show that minimal CFG is undecidable via mapping reduction
Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.
The ...
- 395
0
votes
1
answer
386
views
is determining an unknown CFL from intersection of two CFLs decidable?
this problem was asked over a week ago on cs.se 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 ...
- 11.1k
-2
votes
1
answer
724
views
Intersection between context-free and context-sensitive language decidability [closed]
I'm trying to find a formal proof of the following fact:
Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ($...
- 1
26
votes
3
answers
15k
views
How is proving a context free language to be ambiguous undecidable?
I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
- 389