1.
The FSM (Finite State Machine) machine pictured in the figure below represents what language? (ISRO-2018)
A.
Complements a given bit pattern
B.
Finds 2’s complement of a given bit pattern
C.
Increments a given bit pattern by 1
D.
2.
Let L = {w = (0+1)* | w has even number of 1’s}, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ? (ISRO-2016)
3.
S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of (ISRO 2016)
A.
B.
All odd length palindromes
C.
Strings that begin and end with the same symbol
D.
All even length palindromes
4.
The DFA generated from the following NFA? ISRO CS2013
5.
The number of states required by a Finite State Machine, to simulate the behaviour of a computer with a memory capable of storing ‘m’ words, each of length ‘n’ bits is?
6.
The given finite automata represent which of the languages?
7.
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is ( GATE-CS-2003)
8.
The finite state machine given in figure below recognizes : UGC-NET JUNE Paper-2
A.
Any string of odd number of a’s
B.
Any string of odd number of b’s
C.
Any string of even number of a’s and odd number of b’s
D.
Any string of odd number of a’s and odd number of b’s
9.
The automata represent which of the languages given below? Nielit Scentist-B [02-12-2018]
10.
Which of the following languages over the alphabet {0,1} is described by the given regular expression: (0+1)*1(0+1)*1? Nielit Scentist-B [02-12-2018]
A.
The set of all strings containing the substrings 11
B.
The set of all string containing at most two 1’s
C.
The set of all strings containing at least two 1’s
D.
The set of all strings that begins and ends with only 0.
11.
In the given language L={ab,aa,baa}, __ number of strings are in L* (1) baaaba (2) aabaaaa (3) baaabaaaabaa (4) baaabaaa (GATE CS 2012)
12.
Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2*U L1*
13.
Consider the DFA given. GATE CS 2013
Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.
14.
A deterministic finite automation (DFA)D with alphabet {a,b} is given below
Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
15.
Which of the following statements is false? GATE CS 2008
A.
Every NFA can be converted to an equivalent DFA
B.
Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
C.
Every regular language is also a context-free language
D.
Every subset of a recursively enumerable set is recursive
16.
The transition function for the language L = {w|na (w) and nb(w) are both odd} is given by: UGC NET CS 2015 Jun
δ (q0, a) = q1 ; δ (q0, b) = q2
δ (q1, a) = q0 ; δ (q1, b) = q3
δ (q2, a) = q3 ; δ (q2, b) = q0
δ (q3, a) = q2 ; δ (q3, b) = q1
The initial and final states of the automata are:
17.
Which of the following are not regular? UGC NET CS 2017 Jan
(A) Strings of even number of a’s.
(B) Strings of a’s, whose length is a prime number.
(C)Set of all palindromes made up of a’s and b’s.
(D)Strings of a’s whose length is a perfect square.
18.
Which of the following are not regular? UGC NET CS 2017 Jan
(A) Strings of even number of a’s.
(B) Strings of a’s, whose length is a prime number.
(C) Set of all palindromes made up of a’s and b’s.
(D) Strings of a’s whose length is a perfect square.
19.
The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________
20.
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?