Pumping Lemma for context-free languages MCQs

By: Prof. Dr. Fazal Rehman | 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  
All Copyrights Reserved 2025 Reserved by T4Tutorials