Properties of context-free languages MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

Properties of Context-Free Languages
Which of the following is true about context-free languages (CFLs)?

A) CFLs are closed under union.
B) CFLs are closed under intersection.
C) CFLs are closed under complement.
D) CFLs are closed under Kleene star.
Answer: A

A language L is context-free if and only if:

A) There exists a deterministic pushdown automaton (DPDA) that accepts L.
B) There exists a nondeterministic finite automaton (NFA) that accepts L.
C) There exists a deterministic finite automaton (DFA) that accepts L.
D) There exists a regular expression that describes L.
Answer: A

Context-free languages are closed under which of the following operations?

A) Intersection with a regular language.
B) Complementation.
C) Reversal.
D) Subtraction.
Answer: C

If L1 and L2 are context-free languages, which of the following is necessarily context-free?

A) L1 ∪ L2 (Union of L1 and L2)
B) L1 ∩ L2 (Intersection of L1 and L2)
C) L1 – L2 (Set difference of L1 and L2)
D) All of the above
Answer: D

Which of the following is a property that context-free languages do not possess?

A) Closure under concatenation.
B) Closure under Kleene star.
C) Closure under homomorphism.
D) Closure under complement.
Answer: D

The pumping lemma for context-free languages states that:

A) Every context-free language can be pumped to generate infinitely many strings.
B) Every sufficiently long string in a context-free language can be pumped.
C) Every context-free language can be recognized by a finite automaton.
D) Every context-free language has an unambiguous grammar.
Answer: B

Which of the following is a characteristic feature of context-free grammars?

A) They can generate languages with unbounded stack usage.
B) They can generate languages with infinite alphabet.
C) They can generate languages that are not recursively enumerable.
D) They can generate languages that are not closed under complement.
Answer: A

Context-free languages are not closed under:

A) Intersection with regular languages.
B) Union.
C) Kleene star.
D) Homomorphism.
Answer: A

The Chomsky hierarchy places context-free languages at which level?

A) Type 0
B) Type 1
C) Type 2
D) Type 3
Answer: C

Which of the following is not a property of context-free languages?

A) Closure under union.
B) Closure under intersection.
C) Closure under reversal.
D) Closure under subtraction.
Answer: B

The language {a^n b^n c^n | n ≥ 0} is:

A) Context-free
B) Regular
C) Context-sensitive
D) None of the above
Answer: C

A context-free grammar is ambiguous if:

A) It generates exactly one parse tree for every string.
B) It generates more than one parse tree for some string.
C) It has no parse tree for some string.
D) It has no start symbol.
Answer: B

Which of the following is true regarding the languages generated by context-free grammars?

A) They can be recognized by a deterministic pushdown automaton (DPDA).
B) They always have finite automata that recognize them.
C) They are always regular.
D) They are never recursively enumerable.
Answer: A

The language L = {a^i b^j c^k | i ≠ j or j ≠ k} is:

A) Context-free
B) Regular
C) Context-sensitive
D) None of the above
Answer: C

A context-free grammar is equivalent to a regular grammar if:

A) It has the same start symbol.
B) It generates the same language.
C) It has no non-terminals.
D) It has no terminals.
Answer: B

 

Related Posts: