GATE CS 2017 (Forenoon) — Question 43

Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataNAT2 marksHard

Consider the following grammar: \(\text{stmt} \rightarrow \textbf{if } \text{expr} \textbf{ then } \text{expr} \textbf{ else } \text{expr}; \text{stmt} \mid 0\) \(\text{expr} \rightarrow \text{term } \textbf{relop} \text{ term} \mid \text{term}\) \(\text{term} \rightarrow \textbf{id} \mid \textbf{number}\) \(\textbf{id} \rightarrow a \mid b \mid c\) \(\textbf{number} \rightarrow [0-9]\) where \(\textbf{relop}\) is a relational operator (e.g., <, >, ...), 0 refers to the empty statement, and \(\textbf{if, then, else}\) are terminals. Consider a program \(P\) following the above grammar containing ten \(\textbf{if}\) terminals. The number of control flow paths in \(P\) is ________. For example, the program \(\textbf{if } e_1 \textbf{ then } e_2 \textbf{ else } e_3\) has 2 control flow paths, \(e_1 \rightarrow e_2\) and \(e_1 \rightarrow e_3\).
Practise the full 2017-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Context-Free Grammars & Push-Down AutomataTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group