Decision Properties MCQs: 10 Solved CFG and PDA Questions
Solve ten Decision Properties MCQs by separating the input model from the property being tested, then checking the relevant algorithm or undecidability result.
KnowledgeGate Team
Exam prep & CS education

Decision Properties questions become difficult when the same property word changes status as the representation moves from DFA or NFA to CFG, PDA or DPDA, and Turing machine. Before recalling any result, identify both the object and the property.
The ten questions below test emptiness, finiteness, ambiguity, universality, equivalence, containment, regularity and deterministic context-free languages. For each question, identify the model, name the deciding algorithm or undecidability result, and then check the explanation. Use GATE, PSU, Engineering and Technical Exams for the wider syllabus route. Questions 7, 8 and 9 are concept drills; the Decision Properties practice set gives you further practice.
Related reading: the Turing Machine Decision Properties MCQs post covers machine-language properties; this page focuses on CFG, PDA and DPDA boundaries. For the underlying concepts, see decision problems and CFL identification MCQs.
Decision properties: classify the input before attempting the MCQs

Input | Property | Decision status | Reason or procedure |
|---|---|---|---|
DFA/NFA | Equivalence | Decidable | Build the symmetric difference, then test emptiness. |
CFG | Membership | Decidable | Use a terminating parser such as CYK after suitable normalisation. |
CFG | Emptiness | Decidable | Mark productive variables. |
CFG | Finiteness | Decidable | Remove useless symbols, then check useful recursion. |
CFG | Ambiguity | Undecidable | No decider works for every CFG. |
CFG | Equivalence, inclusion and universality | Undecidable | No general decider exists for these properties. |
PDA | Whether its language is regular | Undecidable | Regularity of an arbitrary PDA language has no general decider. |
DPDA | Whether its language is finite | Decidable | CFL finiteness is decidable, including for this subclass. |
Calibrate the method on G = (V={S,A,B}, Sigma={a,b}, P={S->AB, A->aA|a, B->b}, start=S). In the productive-variable pass, mark A and B first because A => a and B => b. Then mark S through S->AB. Thus S => AB => ab, so L(G) is non-empty and contains ab.
For finiteness, the useful recursion A->aA, followed eventually by A->a, gives ab, aab, aaab, and so on. Each additional use adds one a, so the language is infinite. This is a property of the displayed grammar. It is not the same as asking whether one algorithm decides the property for every CFG. For more grammar mechanics, practise with Context-Free Grammar MCQs: 11 Solved GATE Questions.
Decision Properties MCQs 1-3: CFG algorithms versus equivalence
Question 1
UGC NET 2017, November
Which of the following problems is undecidable ?
A. To determine if two finite automata are equivalent
B. Membership problem for context free grammar
C. Finiteness problem for finite automata
D. Ambiguity problem for context free grammar
Answer: D. Ambiguity problem for context free grammar.
Finite-automata equivalence is decided through symmetric difference and emptiness. CFG membership is decidable, and an FA language is infinite exactly when a reachable cycle can still reach acceptance. Only arbitrary CFG ambiguity lacks a general decider.
Question 2
GATE 2025, Set 2
Let G1 and G2 be context-free grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G.
Which ONE among the following questions is decidable?
A. Is L(G1) = L(G2)?
B. Is L(G1) intersect L(G2) empty?
C. Is L(G1) = L(R)?
D. Is L(G1) empty?
Answer: D. Is L(G1) empty?
Mark productive variables and check whether the start symbol is marked. This decides CFG emptiness. The other choices are undecidable; in C, choosing R = Sigma* would decide CFG universality.
Question 3
UGC NET 2013
Assume the statements S1 and S2 given as:
S1: Given a context-free grammar G, an algorithm can determine whether L(G) is infinite
S2: An algorithm can determine whether two context-free grammars generate the same language
Which of the following is true?
A. S1 is correct and S2 is not correct
B. Both S1 and S2 are correct
C. Both S1 and S2 are not correct
D. S1 is not correct and S2 is correct
Answer: A. S1 is correct and S2 is not correct.
After useless symbols are removed, useful recursion decides CFG finiteness, as A->aA showed. Arbitrary CFG equivalence is undecidable, so S1 is true and S2 false.
Decision Properties MCQs 4-6: ambiguity, universality and Rice's theorem
Question 4
GATE 2014, Set 3
Which one of the following problems is undecidable?
A. Deciding if a given context-free grammar is ambiguous.
B. Deciding if a given string is generated by a given context-free grammar.
C. Deciding if the language generated by a given context-free grammar is empty.
D. Deciding if the language generated by a given context-free grammar is finite.
Answer: A. Deciding if a given context-free grammar is ambiguous.
Membership, emptiness and finiteness have terminating CFG algorithms. Ambiguity asks whether some generated string has two distinct parse trees, and no algorithm settles it for every CFG.
Question 5
GATE 2007
Which of the following problems is undecidable?
A. Membership problem for CFGs
B. Ambiguity problem for CFGs.
C. Finiteness problem for FSAs.
D. Equivalence problem for FSAs.
Answer: B. Ambiguity problem for CFGs.
CFG membership is decidable. Finiteness and equivalence are also decidable for finite-state automata. Arbitrary CFG ambiguity is the only listed problem without a general decider.
Question 6
GATE 2013 and BARC 2013
Which of the following is/are undecidable?
G is a CFG. Is L(G) empty?
2. G is a CFG. Is L(G) = Sigma*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
A. 3 only
B. 3 and 4 only
C. 1, 2 and 3 only
D. 2 and 3 only
Answer: D. 2 and 3 only.
CFG emptiness in 1 is decidable, while CFG universality in 2 is undecidable. Statement 3 is a non-trivial semantic property of a TM language, so Rice's Theorem for GATE: Two-Part Undecidability Test applies. Both automata in 4 denote regular languages, making their equivalence decidable.
Decision Properties MCQs 7-8: ambiguity and deterministic CFL boundaries
Question 7
Which of the following is undecidable?
A. To prove certain languages are non regular
B. To prove certain languages are non-CFL
C. To prove that the given CFG is ambiguous
D. To prove that the given CFG is finite or infinite
Answer: C. To prove that the given CFG is ambiguous.
Read C as the general CFG ambiguity problem, which is undecidable. Pumping arguments can prove particular languages non-regular or non-context-free, while CFG finiteness is decidable.
Question 8
Consider the statements
S1: An unambiguous CFG will always generate DCFL.
S2: A CFG for a DCFL will always be unambiguous.
Which of the above statements is/are TRUE
A. Neither S1 nor S2
B. Only S1
C. Only S2
D. Both S1 and S2
Answer: A. Neither S1 nor S2.
S1 is false because DCFLs form a proper subset of unambiguous CFLs. S2 is false because the deterministic language a* can be described by the ambiguous grammar S->SS | a | epsilon; for example, a has both the direct derivation and derivations that introduce an epsilon branch.
Decision Properties MCQs 9-10: PDA regularity, DPDA finiteness and CFL relations
Question 9
Consider the following languages.
L1= {<M> | M is a PDA and L(M) is regular }
L2={<M> | M is a DPDA and L(M) is infinite }
Select the correct option.
A. Both L1 and L2 are decidable
B. Both L1 and L2 are undecidable
C. L1 is decidable but L2 is undecidable
D. L1 is undecidable but L2 is decidable
Answer: D. L1 is undecidable but L2 is decidable.
L1 asks whether an arbitrary PDA language is regular, an undecidable property. L2 asks finiteness for a DPDA language. Finiteness is decidable for CFLs, including the deterministic subclass.
Question 10
UGC NET 2020, June
Let G1 and G2 be arbitrary context-free grammars and R an arbitrary regular language. Consider the following problems:
(A) Is L(G1) = L(G2)?
(B) Is L(G2) contained in L(G1)?
(C) Is L(G1) = R?
Which of the problems are undecidable?
Choose the correct answer from the options given below:
A. (A) Only
B. (B) Only
C. (A) and (B) Only
D. (A), (B) and (C)
Answer: D. (A), (B) and (C).
CFL equality in (A) and the keyed containment relation in (B) are undecidable for arbitrary CFGs. Equality with a regular language in (C) is also undecidable because choosing R = Sigma* would otherwise decide CFG universality.
Decision Properties MCQ answer key and the traps these questions expose

Question | Answer | Tested contrast |
|---|---|---|
Q1 | D | Ambiguity |
Q2 | D | CFG emptiness |
Q3 | A | Finiteness versus equivalence |
Q4 | A | Ambiguity |
Q5 | B | Ambiguity |
Q6 | D | Universality plus Rice's theorem |
Q7 | C | Ambiguity |
Q8 | A | Unambiguous CFG versus DCFL |
Q9 | D | PDA regularity versus DPDA finiteness |
Q10 | D | CFL equality, containment and equality with a regular language |
Use this four-step timed routine: identify the representation (DFA/NFA, CFG, PDA/DPDA, TM); identify the property; recall one theorem or terminating algorithm; eliminate choices only after both columns are fixed. Do not give membership, emptiness, finiteness, equivalence, universality, ambiguity and regularity one memorised answer. This keeps a true theorem for one model from becoming a false blanket rule.
Keep three contrast pairs ready: CFG emptiness = decidable versus CFG universality = undecidable; FA equivalence = decidable versus CFG equivalence = undecidable; CFG finiteness = decidable versus CFG ambiguity = undecidable.
Decision Properties MCQs: the next practice step
Redo Questions 2, 3, 6, 8, 9 and 10 without looking. Together they test emptiness, finiteness, universality, Rice's theorem, DCFL boundaries, PDA regularity, CFL equality and containment. Write one named theorem or algorithm beside every answer letter.
For a sequenced Theory of Computation route that places Decision Properties after CFG and PDA foundations, use GATE Guidance by Sanchit Sir. If you are preparing specifically for UGC NET Computer Science, NTA-UGC-NET Paper - 2 is the relevant alternative.
The short version: classify the input model first, then the property, then recall the applicable result. Most wrong answers come from remembering a slogan such as "CFG is decidable" or "equivalence is undecidable" without asking which exact object and property the question supplies.
Keep learning
Decision Properties in Theory of Computation: DFA Tests, CFG Boundaries and Turing Machine Undecidability
Learn an algorithm-first way to classify membership, emptiness, finiteness, inclusion, equivalence and universality for DFAs, CFGs and Turing machines.
Context-Free Grammar MCQs: 11 solved questions on CFG, CFL and PDA
Context-free grammar solved MCQs with explanations: 11 GATE PYQs on CFGs, the Chomsky hierarchy, CFL closure properties, pushdown automata and decidability.
Turing Machine Decision Properties MCQs: 12 Solved Questions with Explanations
Solve 12 Turing machine Decision Properties MCQs with explanations of bounded simulation, Rice's theorem, complements, dovetailing and mapping reductions.
Regular Language Properties: Closure, Decision Tests, and Worked Examples
Connect closure properties, decision tests, and proof tools through product automata, pumping arguments, Myhill-Nerode reasoning, and checked string traces.





