With the widespread availability of tools like ChatGPT, Computer Science exams should focus on reasoning, construction, justification, and originality rather than memorization. The following question types are effective for undergraduate CS courses.
Example (Automata Theory):
Given the PDA transitions shown,
simulate the PDA for input aabb.
Show the stack contents after each transition.
Example (Parsing):
Design a grammar where left recursion is intentionally preserved.
Justify why eliminating left recursion would harm your parsing strategy.
Example (Algorithms):
for(i=0; i<n; i++) {
for(j=1; j<n; j=j*2) {
sum++;
}
}
(a) Identify the mistake in the claimed time complexity O(n log n).
(b) Correct it with proper justification.
Using the argument discussed in Chapter 5,
explain why a DPDA cannot recognize a certain CFL.
Provide a different example of your own.
A DFA is partially defined.
Add only two transitions so that it recognizes
strings where the number of 1s is congruent to 2 mod 3.
Explain why no additional transitions are needed.
Two students gave answers on NP-completeness.
(a) Which answer is closer to correctness?
(b) Identify one deep conceptual flaw in the other.
If context switching time becomes zero,
which scheduling algorithms lose their advantage, and why?
Convert the given grammar to CNF
without eliminating epsilon productions.
Explain how correctness is preserved.
Why does determinism in DPDA matter more for parsing
than for language generation?
(Answer in 4–5 lines.)
After studying Pushdown Automata,
name one concept that became clearer
and one that became more confusing, with reasons.