Search code examples
context-free-grammarcomputation-theoryambiguity

How to get the second leftmost derivation in this example?


Using the grammar below, my text says that the string "the girl touches the boy with the flower" can be leftmost derived in two ways making the grammar ambiguous. When I try to find the second derivation, I fail. I really do not see how a second derivation is possible since getting the terminals follows a standard one way pattern: all go from a phrase nonterminal to a couple non-terminals that go to terminals to the terminals.

Grammar

⟨SENTENCE⟩→⟨NOUN-PHRASE⟩⟨VERB-PHRASE⟩

⟨NOUN-PHRASE⟩→⟨CMPLX-NOUN⟩ | ⟨CMPLX-NOUN⟩⟨PREP-PHRASE⟩

⟨VERB-PHRASE⟩→⟨CMPLX-VERB⟩ | ⟨CMPLX-VERB⟩⟨PREP-PHRASE⟩

⟨PREP-PHRASE⟩→⟨PREP⟩⟨CMPLX-NOUN⟩

⟨CMPLX-NOUN⟩→⟨ARTICLE⟩⟨NOUN⟩

⟨CMPLX-VERB⟩→⟨VERB⟩ | ⟨VERB⟩⟨NOUN-PHRASE⟩

⟨ARTICLE⟩ → a | the

⟨NOUN⟩ → boy | girl | flower

⟨VERB⟩ → touches | likes | sees

⟨PREP⟩ → with

Below is how I got my first leftmost derivation.

Sentence,

Noun-phrase Verb-phrase,

Cmplx-noun Verb-phrase,

Article Noun Verb-phrase,

the Noun Verb-phrase,

the girl Verb-phrase,

the girl Complx-Verb,

the girl Verb Noun-phrase,

the girl touches Noun-phrase,

the girl touches Cmplx-noun Prep-phrase,

the girl touches Article Noun Prep-phrase,

the girl touches the Noun Prep-phrase,

the girl touches the boy Prep-phrase,

the girl touches the boy Prep Cmplx-noun,

the girl touches the boy with Cmplx-noun,

the girl touches the boy with Article Noun,

the girl touches the boy with the Noun,

the girl touches the boy with the flower


Solution

  • At

    the girl Verb-phrase
    

    Use

    ⟨VERB-PHRASE⟩→⟨CMPLX-VERB⟩⟨PREP-PHRASE⟩
    

    Then <PREP-PHRASE> will generate "with the flower".