3. Consider the following context-free grammar (CFG): X aXbY|Y Y CY | (a) Show...

Transcribed Image Text:

3. Consider the following context-free grammar (CFG): X → aXbY|Y Y → CY |€ (a) Show using a parse-tree, or otherwise, how the word aabb is derived from the grammar. [5 marks] (b) The language described by the CFG above is recognised by the following push-down au- tomata (PDA): 90 E, E$ a, e a b, a → € C, EE JJ d E, EE €, $→ € 91 93 92 Trace the development of the stack for the path which leads to the acceptance of the word aabb. [5 marks] (c) Describe, in English, the language derived from the CFG. [4 marks] (d) By extending the PDA illustrated above (3b), or otherwise, design a PDA which recognises the language {abci, j, k ≥ 0 and i jor j = k}. [6 marks] 3. Consider the following context-free grammar (CFG): X → aXbY|Y Y → CY |€ (a) Show using a parse-tree, or otherwise, how the word aabb is derived from the grammar. [5 marks] (b) The language described by the CFG above is recognised by the following push-down au- tomata (PDA): 90 E, E$ a, e a b, a → € C, EE JJ d E, EE €, $→ € 91 93 92 Trace the development of the stack for the path which leads to the acceptance of the word aabb. [5 marks] (c) Describe, in English, the language derived from the CFG. [4 marks] (d) By extending the PDA illustrated above (3b), or otherwise, design a PDA which recognises the language {abci, j, k ≥ 0 and i jor j = k}. [6 marks]