Using the standard notational convention, a Phrase Structure Grammar G is specif

Question

Using the standard notational convention, a Phrase Structure Grammar G is specified by the following eight productions:

Need help with part d and e. Thanks a lot!

3 Using the standard notational convention, a Phrase Structure Grammar G is specified by the following eight productions: 3: Sa 1:SWXYZ 8: Wa aa 2: Z XYZ (a) Fill in the blanks This grammar has .. terminal symbol(s) and non-terminal symbol(s) (b) Fill in the blank and provide the reason This grammar is type n but not type n+1, where n because: [1 mark] [1 mark] (c) Here is a derivation of the word aaaa E L(G) Using fairly obvious shorthands, this derivation can be abbreviated to Using the same abbreviated style, provide a derivation of a 16 2 marks (d) Give a succinct but complete description of L (G) Your description should relate to the language itself, not to how it is generated 1 mark (e) Justify your answer to (d) as fully as you can 2 marks

Explanation / Answer

d) L(G)={a,a4,a8,a16,a32..............a(power(2n))} n>=0 and n not equal to 1

e)S->WXYZ

Z->XYZ

S->A

Z->A

XY->YXX

Xa->aa

Wa->aa

S->WXYZ->WXYXYZ->WXYYXXZ->WYXXYXXZ->WXXYXXZ-> WXYXXXXZ -> WYXXXXXXZ -> WYXXXXXXa -> WXXXXXXa -> Waaaaaaa ->aaaaaaaa

here the only way to elimiate W,Y is to make the transformation as WY so that Y can be eliminated.So every time Y to be eliminated the X will be doubled so only 2 multiples of X will be formed so the 'a' will be in the powers of 2 like the above ones, as Y moves towards W all the X between them will be doubled every time, but aa will not be possible so only 2 powers will be possibe in the language except 2 ,so only 2 powers are possible.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.