TIFR CSE 2020 | Part B | Question: 9

Question

A particular Panini-Backus-Naur Form definition for a $<\textsf{word}>$ is given by the following rules:

• $<\textsf{word}>:: = \:<\text{letter}> \mid <\text{letter}>\:<\text{pairlet}>\mid <\text{letter}>\:<\text{pairdig}>$
• $<\textsf{pairlet}>:: = \:<\text{letter}>\:<\text{letter}> \mid <\text{pairlet}>\:<\text{letter}>\:<\text{letter}>$
• $<\textsf{pairdig}>::=\:<\text{digit}>\:<\text{digit}>\mid <\text{pairdig}>\:<\text{digit}>\:<\text{digit}>$
• $<\textsf{letter}>::=\: a\mid b\mid c \mid  \dots \mid y \mid z$
• $<\textsf{digit}>::=\:0\mid 1\mid 2\mid \dots \mid 9$

Which of the following lexical entities can be derived from $<\text{word}>?$

1. $\textsf{word}$
2. $\textsf{words}$
3. $\textsf{c22}$

• A. None of $\text{I},\text{II}\:\text{or}\:\text{III}$ 
• B. $\text{I}$ and $\text{II}$ only
• C. $\text{I}$ and $\text{III}$ only
• D. $\text{II}$ and $\text{III}$ only
• E. $\text{I},\text{II}$ and $\text{III}$

Answer 1

given that,

<pairlet> :: =   <letter><letter> | <pairlet><letter><letter>

∴ <pairlet> = (<letter><letter>)$^+$   ------> (1)

Generates all strings which are even length and all are letters and length grater than 0.

 

<pairdig> :: =   <digit><digit> | <pairdig><digit><digit>

∴ <pairdig> = (<digit><digit>)$^+$   ------> (2)

Generates all strings which are even length and all are digits and length grater than 0.

 

<word> ::=  <letter> |  <letter><pairletter>  |  <letter><pairdigit>

<word> ::=  <letter> | <letter> (<letter><letter>)$^+$  | <letter> (<digit><digit>)$^+$

 

generates, following types of strings

i) all strings which are length odd and those are letters only.

ii) all the strings which are length odd and those are starts with one letter and remaining are digits only.

Answer 2

II) and III) can be generated