CS401 T03

1. Which of the following is NOT a characteristic of regular languages?

• Can be described using a finite number of states

• Can be recognized by a DFA

• Can have an infinite memory requirement

• Can be recognized by an NFA

2. Which of the following languages over the alphabet {0,1} is not regular?

• The set of all strings containing an even number of 0s.

• The set of all strings where the number of 0s equals the number of 1s.

• The set of all strings ending with '01'.

• The set of all strings where every 0 is immediately followed by a 1.

3. Which of the following languages is regular?

• 
• 
• 
• 

4. What is the primary use of the Pumping Lemma?

• To generate regular languages

• To prove that a language is regular

• To prove that a language is not regular

• To minimize the number of states in a DFA

5. In the pumping lemma for regular languages, a string s in language L can be divided into three parts
s = uvw such that certain conditions are met. Which of the following is not one of those conditions?

• 
• |v | > 0

• ∣uv ∣ ≤ p (where p is the pumping length)

• |x | ≥ 1

6. Suppose we use the pumping lemma to show that a language 𝐿 is non-regular. Which of the following is a valid approach?

• Assume that 𝐿 is non-regular and derive a contradiction.

• Find a string s in 𝐿 that cannot be pumped according to the pumping lemma.

• Show that 𝐿 can be accepted by a finite automaton.

• Prove that the complement of 𝐿 is regular.

7. For the pumping lemma, which of the following conditions must be true for the string v in the decomposition s = uvw ?

• v can be empty.

• v must consist of only one symbol.

• The length of v is greater than zero.

• v must be equal to w

8. Why is the condition ∣v ∣>0 important in the pumping lemma for regular languages?

• It ensures that the string can be pumped (repeated)

• It guarantees that v is the entire string s

• It allows v to be an empty string

• It limits the decomposition to finite languages

• The language L is infinite

• The substring v can be repeated any number of times, including zero

• The substring w must be empty

• The substring u must be variable

10. Which of the following describes the importance of ∣uv ∣ ≤k ?

• It ensures u and v are prefixes within the first k symbols.

• It guarantees that v is the last segment of the string.

• It ensures that w contains v as a prefix.

• It enforces v to be empty.