GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 21

Question

Consider the language $L$ over $\Sigma = \{0, 1\}$ consisting of strings with equal number of $0's$ and $1s.$ You are using the pumping lemma to show that $L$ is not regular. You begin by supposing $L$ were accepted by a DFA with $k$ states. What would be a good choice of a string $xyz$ that would allow you to obtain a contradiction?

• A. $0011$
• B. $000111$
• C. $0^k1^{2k}$
• D. $0^k1^k$

Answer 1

The string to be chosen must be in $L$ and this rules out option C. Now pumping lemma says that if a language $L$ is accepted by a DFA with $k$ states and $w = xyz$ is in $L$ and $\textbf{of length at least $k,$}$ then

1. $xy^iz$ is in $L$ for $i \geq 0$

2. $\mid xy \mid \leq k$

3. $\mid y \mid > 0$

Due to $w$ requiring length at least $k,$ we can rule out options A and B. For option D, we can see that $x y$ consist only of $0s$ and hence $y$ also consist of only $0s$ and when we pump more $y$ by increasing $i$ in $y^i$ or making $i = 0$ we get a string with unequal number of $0's$ and $1's$ which is not in $L,$ violating pumping lemma. Hence, correct answer is D.

Comments

why not C

if we take |x| = k-2 0’s and |y| = 2 0’s then if we pump y then the string does not belong to given regular expression so it proves that lanreguage is not regular.

---

@Vaibhav98 , We can’t take C) Bcz, C is not belongs to the given language.

We must take a string ‘w’ which belongs to given language

---

yup, C is not in L, taking C is of no use while proving L as non-regular..

(Even written in first line of the given solution)