One straightforward way to show that a language is non-regular is to use the pumping lemma.
This lemma says that if L is a regular language, there exists a positive integer p such that for any string w ∈ L, there exist
strings x, y, and z such that w = xyz and |x| < p and |y| > 0 and xynz ∈ L for any non-negative integer n.
The procedure is to suggest some string w that is in L and then to argue that no strings x, y, and z exist that satisfy these requirements.
- 1. { w ∈ A* : w contains a 1 in every position that is a power of 2 }
use w = the element in L which contains 1 in exactly p positions
So It is a Non-regular language.
- 2. { w ∈ A* : w contains a prime number of 1’s }
use w = 1r where r is the first prime number such that the next prime number exceeds p + r.
It is also non-regular.
- 3. { w ∈ A* : ∃u ∈ A* such that w = uu }
Option C is a non-regular languages. if we use w = 0p110p.
- 4. For option D : { w ∈ A* : w does not contain any 1’s in even positions, where the leftmost is position 1 }
- it can be recognized with the following deterministic finite state automaton:
so option D is a Regular Language.
Hence correct answer is D .