More specifically: for any arbitrary CFG, is there guaranteed to exist two distinct strings such that a leftmost parse of both strings creates the same parse tree? If not, does there exist any CFG that has this property?

I know that given a string and a CFG, there may be multiple leftmost parse trees for the same string (if the grammar is ambiguous), but I am unsure if the converse is true.

I suspect the answer is no and I have not come across a case that seems to suggest otherwise, but I cannot think of a rigorous justification.

  • $\begingroup$ Welcome to CS.SE! Please edit to clarify what you are asking. Are you asking, does there exist any CFG where some pair of distinct strings can create the same parse tree? Are you asking, is there always a pair of distinct strings that create the same parse tree, for all possible CFGs? Are you asking about a specific CFG? (If so, which one?) Are you asking for an algorithm that takes a CFG as input and outputs whether there exist a pair of distinct strings with the same parse tree? What counts as "the same parse tree"? This can be considered for re-opening if it's edited to clarify. $\endgroup$ – D.W. Aug 3 '16 at 20:38
  • $\begingroup$ Also, what are your thoughts? What have you tried? What self-study have you done? Have you tried working through some examples? Have you tried proving this on your own? We want you to make your best effort towards solving it on your own before asking, and show us in the question what you've tried. Please edit the question to clarify these points. Thank you! $\endgroup$ – D.W. Aug 3 '16 at 20:39
  • 1
    $\begingroup$ Hint: what happens when you traverse the roots of parse-trees in leftmost order? If two trees are the same, their roots are the same. What effect does this have on the word produced? $\endgroup$ – jmite Aug 3 '16 at 21:51
  • 1
    $\begingroup$ Hint: The string can be read off the leaves of the parse tree (traversed left to right). $\endgroup$ – Yuval Filmus Aug 6 '16 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.