Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 0: Q8E (page 1)

Show that the stringthe girl touches the boy with the flowerhas two different leftmost derivations in grammar G2 on page 103. Describe in English the two different meanings of this sentence.

Short Answer

Expert verified

It can be shown that the given string can be derived in two different leftmost derivations in grammar G2.

Derivation 1, gives the meaning of the sentence as that the girl used the flower to touch the boy. Derivation 2 , means that the boy is holding the flower when the girl touches her.

Step by step solution

01

Explain leftmost derivations.

The leftmost derivation is derived by using the productions from the grammar. The derivation of the string from the grammar starts at the leftmost end of the string, thus it is called leftmost derivation.

02

Show that the given string can be derived in two leftmost derivations and it has two meanings.

Consider the string,the girl touches the boy with the flowerto perform left most derivation. The string can be derived using the grammar G2on page 103 as follows.

Derivation 1:

localid="1662113548058" SENTENCE→NOUN-PHRASEVERB-PHRASESENTENCE→COMPLEX-NOUNVERB-PHRASESENTENCE→COMPLEX-NOUNCOMPLEX-VERBPREP-PHRASESENTENCE→ARTICLENOUNCOMPLEX-VERBPREP-PHRASE⇒ARTICLENOUNCOMPLEX-VERBPREP-PHRASE⇒ThegirlCOMPLEX-VERBPREP-PHRASE⇒ThegirlVERBNOUN-PHRASEPREP-PHRASE⇒ThegirltouchesNOUN-PHRASEPREP-PHRASE⇒ThegirltouchesCOMPLEX-NOUNPREP-PHRASE⇒ThegirltouchesARTICLENOUNPREP-PHRASE⇒ThegirltouchestheNOUNPREP-PHRASE⇒ThegirltouchestheboyPREP-PHRASE⇒ThegirltouchestheboyPREPCOMPLEX-NOUN⇒ThegirltouchestheboywithCOMPLEX-NOUN⇒ThegirltouchestheboywithARTICLENOUN⇒ThegirltouchestheboywiththeNOUN⇒ThegirltouchestheboywiththeflowerDerivation 2:

localid="1662113579670" SENTENCE→NOUN-PHRASEVERB-PHRASE⇒SENTENCE→COMPLEX-NOUNVERB-PHRASE⇒SENTENCE→ARTICLENOUNVERB-PHRASE⇒ARTICLENOUNVERB-PHRASE⇒TheNOUNVERB-PHRASE⇒ThegirlVERB-PHRASE⇒ThegirlCOMPLEX-VERBPREP-PHRASE⇒ThegirlVERBNOUN-PHRASEPREP-PHRASE⇒ThegirltouchesNOUN-PHRASEPREP-PHRASE⇒ThegirltouchesCOMPLEX-NOUNPREP-PHRASE⇒ThegirltouchesARTICLENOUNPREP-PHRASE⇒ThegirltouchestheNOUNPREP-PHRASE⇒ThegirltouchestheboyPREP-PHRASE⇒ThegirltouchestheboyPREPCOMPLEX-NOUN⇒ThegirltouchestheboywithCOMPLEX-NOUN⇒ThegirltouchestheboywithARTICLENOUN⇒ThegirltouchestheboywiththeNOUN⇒Thegirltouchestheboywiththeflower

Derivation 1, gives the meaning of the sentence as that the girl used the flower to touch the boy. Derivation 2 , means that the boy is holding the flower when the girl touches her.

Therefore, the string has been derived in two ways that gives two meanings.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Give a counter example to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL that is generated by the CFG G=(V,∈,R,S). Add the new ruleS→SS and call the resulting grammar. This grammar is supposed to generate A*.

Let CNFk= is a satisfiable cnf-formula where each variable appears in at most k places}.

a. Show thatCNF2?P .

b. Show thatCNF3 isNP-complete.

Show that if G is a CFG in Chomsky normal form, then for any stringw∈L(G) of lengthn⩾1, exactly2n-1 steps are required for any derivation of w.

Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

In the following solitaire game, you are given anm×m board. On each of itsm2 positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board until each column contains only stones of a single color and each row contains at least one stone. You win if you achieve this objective. Winning may or may not be possible, depending upon the initial configuration. LetSOLITAIRE={<G>|G is a winnable game configuration}. Prove that SOLITAIREis NP-complete.
See all solutions

Recommended explanations on Computer Science Textbooks

Algorithms in Computer Science

Read Explanation

Theory of Computation

Read Explanation

Game Design in Computer Science

Read Explanation

Computer Programming

Read Explanation

Issues in Computer Science

Read Explanation

Databases

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free