WorksheetsPumping Lemma Quiz
Total questions: 20
Worksheet time: 10mins
What is the main purpose of the Pumping Lemma for regular languages?
To prove that a language is regular
To prove that a language is not regular
To generate regular expressions
To minimize finite automata
According to the Pumping Lemma for regular languages, any string s in the language with length at least p can be divided into parts x, y, z such that:
s=xy+z
s=xyz and |xy|≤p, |y|≥1
s=xyz and |x|≥1, |y|≥1
s=x+y+z and |z|≤p
What does the “pumping length” p represent in the Pumping Lemma?
The minimum number of states in the DFA
The maximum length of any string in the language
A constant dependent on the number of states in the automaton
The total number of symbols in the alphabet
Which of the following conditions must hold for all i≥0 in the Pumping Lemma for regular languages?
xy^iz∈L
xy^iz∉L
xy^iz=xyz
xy^iz must be empty
Which of the following languages violates the Pumping Lemma for regular languages?
L={a^n b^n | n≥0}
L={a^n b^m | n,m≥0}
L={0^* 1^*}
L={a,b}^*
What is the correct way to prove that a language is not regular using the Pumping Lemma?
Find one decomposition that satisfies the lemma
Show that for all possible decompositions, the lemma holds
Show that for all possible decompositions, the lemma fails
Find a DFA that recognizes the language
Which of the following is true about the Pumping Lemma for context-free languages?
It uses three parts: x, y, z
It uses five parts: u, v, w, x, y
It only applies to regular languages
It cannot be used to show non-context-freeness
In the context-free Pumping Lemma, what property must hold for all i≥0?
u v^i w x^i y∈L
u v^i w x^i y∉L
u v^i w x^i y=u v w x y
u v^i w x^i y is empty
Which of the following languages is not context-free and can be shown using the context-free Pumping Lemma?
L={a^n b^n c^n | n≥0}
L={a^n b^m | n,m≥0}
L={a^i b^j | i
L={a^n b^n | n≥0}
What is the major limitation of the Pumping Lemma?
It can prove both regularity and non-regularity
It can only prove regularity, not non-regularity
It can only prove non-regularity, not regularity
It cannot be used for any language
Who is considered the father of theoretical computer science and artificial intelligence?
John von Neumann
Alan Turing
Alonzo Church
Stephen Kleene
What is the major contribution of Alan Turing to Automata Theory?
The concept of finite automata
The invention of digital computers
The introduction of the Turing Machine model
The design of the ENIAC computer
The Turing Machine was introduced to formalize the concept of:
Artificial Intelligence
Computability and algorithms
Programming languages
Software development
A Turing Machine consists of which of the following components?
Input tape, head, and processor
Tape, tape head, and finite control
Memory, monitor, and keyboard
State diagram, compiler, and input alphabet
What does it mean if a language is Turing recognizable (or recursively enumerable)?
A Turing Machine can decide it and always halts
A Turing Machine can accept it, but might not halt for non-members
The language is finite
It cannot be recognized by any automaton
What is the Halting Problem, as introduced by Alan Turing?
The problem of stopping an infinite tape
The problem of determining whether a Turing Machine halts on a given input
The problem of counting tape symbols
The problem of minimizing automata
Which of the following statements is true about the Halting Problem?
It is decidable by any Turing Machine
It is undecidable — no Turing Machine can solve it for all cases
It can be solved by finite automata
It applies only to regular languages
The concept of the “Universal Turing Machine” proposed by Alan Turing represents:
A machine that can simulate any other Turing Machine
A machine that can only process regular languages
A physical computer for AI experiments
A simplified DFA for all inputs
What is the significance of Turing’s work in the history of computation?
It limited computation to arithmetic operations only
It showed that all mechanical computation can be modeled mathematically
It eliminated the need for algorithms
It focused only on artificial intelligence
Which statement best describes the relationship between Alan Turing’s work and modern computers?
Turing’s model inspired the concept of general-purpose programmable machines
Turing’s model was never implemented in practice
Turing only worked on biological systems
Turing’s theory contradicted digital computation
