edited by
599 views
6 votes
6 votes

Which of the following languages over the alphabet $A = $$\left \{ 0,1 \right \}$ is regular ?
 

  1.     $\{ w ∈ A^* : w$ contains a $1$ in every position that is a power of $2\}$
  2.     $\{ w ∈  A^* : w$ contains a prime number of $1’s \}$
  3.     $\{ w ∈ A^* :$  $\exists u\in A^{\ast }$such that $w = uu \}$
  4.     $\{ w ∈ A^* : w$ does not contain any $1’s$ in even positions, where the leftmost position is $1 \}$
edited by

2 Answers

Best answer
2 votes
2 votes

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 .

2 votes
2 votes

here i guess people have confusion between A and D

Consider A:

to get '1' in power of 2, is NOT same as 1 in even position,which many people is assuming(what i assumed in first go also)

so we need '1' in place of 2,4,8,16,32... which can not even done by a PDA also..so no question of being regular

Consider D:

Here we can construct an a FA easily ,just by making every even transition anything other than 1 and it is so Regular

So D is correct answer here

Answer:

Related questions

5 votes
5 votes
1 answer
2
1 votes
1 votes
5 answers
3
Bikram asked Jan 24, 2017
714 views
$S\rightarrow A0 B$$A\rightarrow BB \mid 0$$B\rightarrow AA \mid 1$ The number of terminal strings of length $5$ generated by the context-free grammar shown above is ____...
3 votes
3 votes
1 answer
4
Bikram asked Jan 24, 2017
796 views
Consider these three grammars.$$\begin{array}{|c|c|c|} \hline \textbf{Grammar G1:} & \textbf{Grammar G2:} & \textbf{Grammar G3:} \\ \hline E\rightarrow E+T \mid T & E\r...