Pumping Lemma for context-free languages MCQs

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

Pumping Lemma for Context-Free Languages
What does the Pumping Lemma for context-free languages state?

A) Every sufficiently large context-free language can be pumped to generate infinitely many strings.
B) Every context-free language contains strings that can be pumped to generate more strings in the language.
C) Every context-free language has a finite number of strings that can be generated.
D) Every context-free language has an equivalent regular language.
Answer: B

According to the Pumping Lemma for context-free languages, for every context-free language L, there exists a pumping length p such that:

A) Every string in L can be divided into p segments that can be pumped.
B) Every string in L of length at least p can be split into xyz, where |xy| ≤ p, |y| > 0, and xy^iz ∈ L for all i ≥ 0.
C) Every string in L can be pumped infinitely many times regardless of its length.
D) Every string in L can be recognized by a deterministic pushdown automaton (DPDA).
Answer: B

Which of the following is a consequence of the Pumping Lemma for context-free languages?

A) Every context-free language is regular.
B) Every regular language is context-free.
C) Every context-free language has a finite number of strings.
D) Every context-free language has an unambiguous grammar.
Answer: A

The Pumping Lemma for context-free languages is used to:

A) Prove that a language is context-free.
B) Prove that a language is regular.
C) Define the grammar for a context-free language.
D) Construct a non-deterministic pushdown automaton (NPDA).
Answer: A

Which part of the Pumping Lemma for context-free languages guarantees the existence of a decomposition xyz of a string in a context-free language?

A) |xy| ≤ p
B) |y| > 0
C) xy^i z ∈ L for all i ≥ 0
D) All of the above
Answer: D

If a language violates the conditions of the Pumping Lemma for context-free languages, it implies that the language is:

A) Regular
B) Context-free
C) Not context-free
D) Recursively enumerable
Answer: C

Which of the following statements is true regarding the Pumping Lemma for context-free languages?

A) It can be used to prove that a context-free grammar is ambiguous.
B) It can be used to prove that a context-free language is infinite.
C) It can be used to construct a deterministic pushdown automaton (DPDA).
D) It can be used to convert a regular language into a context-free language.
Answer: B

The Pumping Lemma for context-free languages is an important tool in the study of:

A) Finite automata
B) Pushdown automata
C) Turing machines
D) Regular expressions
Answer: B

Which of the following languages satisfies the conditions of the Pumping Lemma for context-free languages?

A) {a^n b^n c^n | n ≥ 0}
B) {a^n b^n | n ≥ 0}
C) {ww^R | w ∈ {a, b}*}
D) {a^i b^j | i ≠ j}
Answer: B

The Pumping Lemma for context-free languages helps to demonstrate that context-free languages are:

A) Regular
B) Recursive
C) Decidable
D) Closed under union
Answer: C

 

Related Posts: