GATE CSE 1998 | Question: 1.10

Question

Which of the following set can be recognized by a Deterministic Finite state Automaton?

• A. The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary

• B. The numbers $1, 2, 4, 8,\dots 2^n, \dots$  written in unary

• C. The set of binary string in which the number of zeros is the same as the number of ones.

• D. The set $\{1, 101, 11011, 1110111, \dots\}$

Comments

MSB to LSB

https://gateoverflow.in/1695/gate1998-4

---

For C,D  we can clearly see that PDA is required to store and compare the input quantities.B is a non regular language. So, option A is correct answer.

---

Option A can be done By DFA

and Option Can be done by CFL not by DFA

Answer 1

Option A is correct .

• A. A. is regular 
  $L = \{1, 10, 100, 1000, 10000, \dots \}$ 
  Regular expression $10^*$
  
  $\textsf{DFA}:$
  
• B. $L=\{1,11,1111,11111111, \dots \}= \{1^i \mid i =2^n, n \geq 0 \}$ is non regular language
• C. Equal - Equal is CFL, and non regular as here we have to compare the counts which need not be finite 
• D. $L=\{1^i01^i   \mid i>0\}\cup \{1\}$ is also CFL, and non regular 

Comments

The language for $A$ must be $0^*10^*$.

---

on upper solution DFA state q0 on transition 0 make self loop may be

---

The language in option 'D' requires matching the number of 1s before and after 0. This requires storing an unbounded count, which is impossible for a finite automaton. Hence the language is non-regular and cannot be accepted by a DFA.

 

Answer 2

A)   as 1 in binary is 1

            2 = 10

            4= 100

and so on so language is  10*  so DFA can be formed.

Answer 3

The memory for any DFA is its state which can store some finite amount of data(present situation of the machine), if we want to store infinite data then the number of states require will be infinite, so dfa not possible. Now you may be thinking what about Infinite language, if a language is infinite then there must be a pattern that exists and we will use a loop in our dfa to tackle this without pattern dfa for infinite language is not possible.

Answer 4

i will add one point for option B

when an UNARY alphabet is given...the strings in the language must follow ARITHMETIC PROGRESSION then it is REGULAR otherwise not

so here strings are not in AP..so option B is not regular language

Answer 5

For the first Option , we can Easily create DFA, Regular Expression( 10* ).

For all Remaining three of them, there exist a "Infinite Distinguishable Set of Strings".Hence they are Not Regular Language.

 

Answer 6

the Language is of the form of 10* for binary numbers {1,2,4,8,.....}

• The string w=1(0^p) is chosen to have a clear pattern: a 1 followed by zeros.
• Pumping y just increases or decreases the number of zeros, but the string remains valid because the pattern "1 followed by zeros" is preserved.
• Therefore, L satisfies the pumping lemma, proving it is regular.