Decision Properties MCQs: 10 Solved CFG and PDA Questions

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.

This set gives exactly 10 solved MCQs on emptiness, finiteness, ambiguity, universality, equivalence, containment, regularity and deterministic context-free languages. Choose an option and name the deciding algorithm or undecidability result before reading each explanation. KnowledgeGate has over 10 published questions on Decision Properties. Use GATE CS Exam Preparation for the wider syllabus route. Questions 7, 8 and 9 are concept drills; the Decision Properties practice set gives you further practice.

Related reading: decision problems and CFL identification MCQs.

Decision properties: classify the input before attempting the MCQs

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 $𝐺_1, 𝐺_2$ be Context Free Grammars (CFGs) and $𝑅$ be a regular expression. For a grammar $G$, let $𝐿(𝐺)$ denote the language generated by $G$.

Which ONE among the following questions is decidable?

• A. $Is 𝐿(𝐺_1) = 𝐿(𝐺_2)?$

• B. $Is 𝐿(𝐺_1) ∩ 𝐿(𝐺_2) = ∅?$

• C. $Is 𝐿(𝐺_1) = 𝐿(𝑅)?$

• D. $Is 𝐿(𝐺_1) = ∅?$

Answer: D. $Is 𝐿(𝐺_1) = ∅?$

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 S₁ and S₂ given as:

S₁: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite

S₂: There exists an algorithm to determine whether two context free grammars generate the same language

Which of the following is true?

• A. S₁ is correct and S₂ is not correct

• B. Both S₁ and S₂ are correct

• C. Both S₁ and S₂ are not correct

• D. S₁ is not correct and S₂ is correct

Answer: A. S₁ is correct and S₂ is not correct.

After useless symbols are removed, useful recursion decides CFG finiteness, as A->aA showed. Arbitrary CFG equivalence is undecidable, so S₁ is true and S₂ 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?

1. $G$ is a CFG. Is $L(G) = \phi$?

2. $G$ is a CFG. Is $L(G) = ∑^*$ ?

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 𝐺₁ and 𝐺₂ be arbitrary context free languages and 𝑅 an arbitrary regular language. Consider the following problems:

(A) Is 𝐿(𝐺₁)=𝐿(𝐺₂)?

(B) Is 𝐿(𝐺₂)≤𝐿(𝐺₁)?

(C) Is 𝐿(𝐺₁)=𝑅?

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

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.