Let be a context-free grammar in Chomsky Normal Form with and containing 10 variable symbols including the start symbol . The string is derivable from . The number of steps (application of rules) in the derivation is ________.
GATE CS 2024 (Forenoon) — Question 59
Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataNAT2 marksMedium
A GATE question every morning
One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.
More on Context-Free Grammars & Push-Down Automata
- GATE CS 2026 (Forenoon) · Q25Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S aSbS bS Which of the following statements i…
- GATE CS 2026 (Forenoon) · Q52Consider the following context-free grammar G : S abaaBAbba A aaBBAb bBabaa B aBb ab In the above grammar, S is the start symbol, a and b a…
- GATE CS 2026 (Afternoon) · Q29Which of the following grammars is/are ambiguous?
- GATE CS 2025 (Forenoon) · Q19Consider the following context-free grammar G , where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is…
- GATE CS 2025 (Afternoon) · Q24Which ONE of the following languages is accepted by a deterministic pushdown automaton?
- GATE CS 2024 (Afternoon) · Q52Consider a context-free grammar G with the following 3 rules. S aS S aSbS S c Let w L(G) . Let n a(w), n b(w), n c(w) denote the number of…

