Chapter 13, Problem 1RQ

a) Define a phrase-structure grammar.

b) What does it mean for a string to be derivable from a string w by a phrase-structure grammar G?

To determine

To define a phrase-structure grammer.

Answer to Problem 1RQ

“ A phrase structure grammer is denoted by set $G=(V,T,S,P)$, where V is a vocabulary, T as a subset of V, S as a starting symbol and P as productions of the grammer. Here every production in P must contain at least one non terminal on its left side. “

Explanation of Solution

Given:

Phrase structure grammer.

Concept: Definition of phrase structure grammer involves following description of few alphabets :

V: It is a finite, non empty set of elements called symbols.

T : It is a subset of set V that consisting of terminal ( non replacing symbols of vocabulary) symbols.

S : It is a starting symbol ( element of vocabulary, used to start a sentence ) from V.

P : It stands for production. These are the rules that specify the replacement of one string from another in the sentence.

To determine

Meaning for a string to be derivable from another string $w$ by a phrase-structure grammer G.

Answer to Problem 1RQ

A string $w_0$ is called derivable from another string $w_1$ by a phrase-structure grammer $G=(V,T,S,P)$ if for a production $Vlf{z}_0\to z_1$, strings $w_0\to l{z}_{0}r$ (that is a concentration of $l,z_0$ and r) and $w_1\to l{z}_{1}r$ ( concentration of $l,z_1$ and r) can be replaced with each other and denoted as $w_1\Rightarrow w_0$.

Explanation of Solution

If two strings of a production of phrase-structure-language are be replaced in such a way, then it is said that one string is a derivation of another string. And it is represented by symbol $\Rightarrow$.