1.
The FSM (Finite State Machine) machine pictured in the figure below represents what language? (ISRO-2018)
Correct Answer
B. Finds 2’s complement of a given bit pattern
Explanation
The FSM machine pictured in the figure represents the process of finding the 2's complement of a given bit pattern. The 2's complement is a mathematical operation used in digital systems to represent negative numbers. This operation involves flipping the bits of the given pattern and adding 1 to the result. The FSM machine in the figure likely follows a specific set of states and transitions to perform this operation on the input bit pattern.
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)
Correct Answer
B. 0*(10*10*)*
Explanation
The regular expression 0*(10*10*)* represents the language L. This regular expression allows for any number of 0's at the beginning (including none), followed by any number of occurrences of the pattern 10*10* (which ensures an even number of 1's), and finally allows for any number of 0's at the end (including none). This covers all possible strings in L.
3.
S → aSa âˆ£ bSb âˆ£ a âˆ£ b The language generated by the above grammar over the alphabet is the set of (ISRO 2016)
Correct Answer
B. All odd length palindromes
Explanation
The given grammar generates strings that are palindromes. This is because the production rules allow for the creation of strings that have the same symbol at the beginning and end (aSa or bSb), as well as individual symbols (a or b). Since palindromes are strings that read the same forwards and backwards, the language generated by this grammar is the set of all odd length palindromes.
4.
The DFA generated from the following NFA? ISRO CS2013
Correct Answer
A. Q0, q1, q2
Explanation
The given answer q0, q1, q2 represents the states of the DFA generated from the given NFA. In the NFA, q0 is the initial state and q1 and q2 are the other states. The answer correctly lists all the states of the DFA.
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?
Correct Answer
C. 2^mn
Explanation
A Finite State Machine (FSM) is a mathematical model used to describe the behavior of a system. In this question, we are simulating the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits.
To represent all possible combinations of 'm' words, each of length 'n' bits, we need 2^n states. For each word, we have 2 possible values for each bit (0 or 1), so the total number of states required is 2^n.
Since we have 'm' words, we multiply the number of states required for one word (2^n) by 'm'. Therefore, the correct answer is 2^mn.
6.
The given finite automata represent which of the languages?
Correct Answer
A. {1, 0}* {01}
Explanation
The given finite automata represents the language consisting of all strings that start with any number of 1s or 0s, followed by the string "01".
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)
Correct Answer
C. 7
Explanation
The set S consists of seven bit binary strings where the first, fourth, and last bits are 1. To find the number of strings in S that are accepted by M, we need to consider all possible combinations for the remaining four bits. Since each bit can be either 0 or 1, there are 2^4 = 16 possible combinations. However, we need to exclude the strings where all four remaining bits are 0, as they do not satisfy the condition. Therefore, the number of strings in S that are accepted by M is 16 - 1 = 15.
8.
The finite state machine given in figure below recognizes :
Correct Answer
D. Any string of odd number of a’s and odd number of b’s
Explanation
The finite state machine shown in the figure recognizes any string of odd number of a's and odd number of b's. This is because the machine has two states, one for even number of a's and one for odd number of a's. Similarly, it has two states for even and odd number of b's. By transitioning between these states based on the input characters, the machine can determine if the number of a's and b's in the string is odd.
9.
The automata represent which of the languages given below? Nielit Scentist-B [02-12-2018]
Correct Answer
D. B*ab*
Explanation
The automaton represents the language consisting of strings that start with zero or more occurrences of 'b', followed by 'a', and ending with zero or more occurrences of 'b'.
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]
Correct Answer
C. The set of all strings containing at least two 1’s
Explanation
The regular expression (0+1)*1(0+1)*1 matches any string that contains at least two occurrences of the symbol 1. This means that the correct answer is "The set of all strings containing at least two 1's."
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)
Correct Answer
C. 1, 2 and 4
Explanation
The language L* represents the set of all possible strings that can be formed by concatenating zero or more strings from L. In this case, the language L contains three strings: ab, aa, and baa.
Option 1 (baaaba) is in L* because it can be formed by concatenating the string baa from L with the string aba from L*.
Option 2 (aabaaaa) is in L* because it can be formed by concatenating the string aa from L with the string abaaa from L*.
Option 3 (baaabaaaabaa) is not in L* because it cannot be formed by concatenating any combination of strings from L.
Option 4 (baaabaaa) is in L* because it can be formed by concatenating the string baa from L with the string abaa from L*.
Therefore, the correct answer is 1, 2, and 4.
12.
Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2*U L1*
Correct Answer
B. B
Explanation
The correct answer is B because L1 represents the empty language, which means it contains no strings. L2* represents any number of occurrences of the string "a" or no occurrence at all. U represents the union operation, so L1 L2*U L1* will include any string from L1 followed by any number of "a"s or no "a"s at all, or any number of occurrences of "a" or no occurrence at all. Therefore, the language represented by B is the correct answer.
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.
Correct Answer
D. 3 and 4 only
Explanation
Option 3 is false because the minimal DFA for the language accepted by A would have fewer states than the given DFA. Option 4 is false because the DFA does not accept all strings over {0, 1} of length at least 2. The string "0" is not accepted by the DFA. Therefore, the correct answer is 3 and 4 only.
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?
Correct Answer
A. Option 1
Explanation
Option 1 is a valid minimal DFA which accepts the same language as D because it has the same number of states as D, and the transitions and accepting states are also the same. The only difference is that option 1 has a different arrangement of states, but it still represents the same language.
15.
Which of the following statements is false? GATE CS 2008
Correct Answer
D. Every subset of a recursively enumerable set is recursive
Explanation
Every subset of a recursively enumerable set is recursive. This statement is false because not every subset of a recursively enumerable set is recursive. A recursively enumerable set is a set for which there exists a Turing machine that can enumerate all the elements of the set. However, a recursive set is a subset of a recursively enumerable set for which there exists a Turing machine that can decide membership in the set. Therefore, while every recursive set is a subset of a recursively enumerable set, not 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:
Correct Answer
C. Q0 and q2 respectively
Explanation
The initial state of the automata is q0, which means that the automata starts in state q0. The final state of the automata is q2, which means that the automata accepts a string if it ends in state q2. Therefore, the initial and final states of the automata are q0 and q2 respectively.
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.
Correct Answer
B. (A), (B) and (C) only
Explanation
(A) Strings of even number of a's - This language is not regular because it cannot be recognized by a finite automaton. It requires counting the number of a's, which is beyond the capabilities of a finite automaton.
(B) Strings of a's, whose length is a prime number - This language is not regular because it requires checking whether the length of the string is a prime number, which is not possible with a finite automaton.
(C) Set of all palindromes made up of a's and b's - This language is not regular because it requires checking whether a string is a palindrome, which is not possible with a finite automaton.
(D) Strings of a's whose length is a perfect square - This language is regular because it can be recognized by a finite automaton.
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.
Correct Answer
D. (B) and (D) only
Explanation
Option (B) states that the strings of a's, whose length is a prime number, are not regular. Regular languages can be recognized by finite automata, but the language of strings with a prime length cannot be recognized by any finite automaton. This is because the length of a prime number cannot be expressed as a product of smaller numbers, making it impossible to determine the number of states required to recognize such strings.
Option (D) states that the strings of a's whose length is a perfect square are not regular. Similar to option (B), the language of strings with a perfect square length cannot be recognized by any finite automaton. This is because the number of states required to recognize such strings would need to be proportional to the square root of the length, which is not possible in a finite automaton.
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 __________________
Correct Answer
A. 2
Explanation
The regular expression (0+1)*(0+1)(0+1)* represents a language that accepts any combination of 0s and 1s, as long as it starts and ends with either a 0 or a 1. In a DFA, there would be two states: one for the starting and ending state, and another for the intermediate states. The DFA would transition between these two states based on the input symbols 0 and 1. Therefore, the correct answer is 2.
20.
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
Correct Answer
A. 7
Explanation
The regular expression (x+y)*y(a+ab)* describes a language that consists of strings that start with any number of x's or y's, followed by a y, and then followed by any number of a's or ab's. To find the number of strings of length less than 4 that belong to this language, we need to consider all possible combinations of these characters. There are 3 possible lengths for the strings: 1, 2, or 3. For each length, we can count the number of strings that satisfy the regular expression. For length 1, the only possible string is "y". For length 2, the possible strings are "yy", "ya", "yb", and "yab". For length 3, the possible strings are "yyy", "yya", "yyb", "yyab", "yaa", "yab", and "yabb". Therefore, there are a total of 7 strings of length less than 4 that contain the language described by the regular expression.