edited by
15,391 views
56 votes
56 votes

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

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

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

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

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

edited by

4 Answers

Best answer
88 votes
88 votes

Option A is correct .

  1. A. is regular 
    $L = \{1, 10, 100, 1000, 10000, \dots \}$ 
    Regular expression $10^*$

    $\textsf{DFA}:$
  2. $L=\{1,11,1111,11111111, \dots \}= \{1^i \mid i =2^n, n \geq 0 \}$ is non regular language
  3. Equal - Equal is CFL, and non regular as here we have to compare the counts which need not be finite 
  4. $L=\{1^i01^i   \mid i>0\}\cup \{1\}$ is also CFL, and non regular 
edited by
5 votes
5 votes

A)   as 1 in binary is 1

            2 = 10

            4= 100

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

4 votes
4 votes

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.

0 votes
0 votes
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:

Related questions

36 votes
36 votes
2 answers
1
39 votes
39 votes
4 answers
2
Kathleen asked Sep 25, 2014
17,226 views
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$...
37 votes
37 votes
4 answers
3
Kathleen asked Sep 25, 2014
11,110 views
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is t...
20 votes
20 votes
4 answers
4
Kathleen asked Sep 25, 2014
6,955 views
The rank of the matrix given below is:$$\begin{bmatrix} 1 &4 &8 &7\\ 0 &0& 3 &0\\ 4 &2& 3 &1\\ 3 &12 &24 &21 \end{bmatrix}$$$3$$1$$2$$4$