Theory Of Computation (Toc) Quiz

1. The automata represent which of the languages given below? Nielit Scentist-B [02-12-2018]

Ab*b*

A*b*

B*b

B*ab*

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'.

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'.

2. 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]

The set of all strings containing the substrings 11

The set of all string containing at most two 1’s

The set of all strings containing at least two 1’s

The set of all strings that begins and ends with only 0.

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."

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."

3. 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?

M x 2^n

2m+n

2^mn

M+n

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.

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.

4. 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.

(A) and (B) only

(A), (B) and (C) only

(B), (C) and (D) only

(B) and (D) only

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.

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.

5. 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?

Option 1

Option 2

Option 3

Option 4

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.

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.

6. The DFA generated from the following NFA? ISRO CS2013

Q0, q1, q2

[q0, q1], [q0, q2], [ ]

Q0, [q1, q2]

[q0, q1], q2

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.

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.

7. The given finite automata represent which of the languages?

{1, 0}* {01}

{1, 0}* {1}

{1}{1, 0}* {1}

1*0* {0, 1}

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".

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".

8. The finite state machine given in figure below recognizes :

Any string of odd number of a’s

Any string of odd number of b’s

Any string of even number of a’s and odd number of b’s

Any string of odd number of a’s and odd number of b’s

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.

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 FSM (Finite State Machine) machine pictured in the figure below represents what language? (ISRO-2018)

Complements a given bit pattern

Finds 2’s complement of a given bit pattern

Increments a given bit pattern by 1

Changes the sign bit

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.

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.

10. 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)

1

5

7

8

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.

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.

11. 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)

(0*10*1)*

0*(10*10*)*

0*(10*1*)*0*

0*1(10*1)10*

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.

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.

12. S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of (ISRO 2016)

All palindromes

All odd length palindromes

Strings that begin and end with the same symbol

All even length palindromes

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.

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.

13. 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 __________________

2

3

4

5

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.

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.

14. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2*U L1*

A

B

C

D

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.

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.

15. 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)

1, 2 and 3

2, 3 and 4

1, 2 and 4

1, 3 and 4

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.

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.

16. 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.

(A) and (B) only

(A), (B) and (C) only

(B), (C) and (D) only

(B) and (D) only

(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.

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.

17. Which of the following statements is false? GATE CS 2008

Every NFA can be converted to an equivalent DFA

Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

Every regular language is also a context-free language

Every subset of a recursively enumerable set is recursive

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.

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.

18. 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.

1 and 3 only

2 and 4 only

2 and 3 only

3 and 4 only

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.

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.

19. 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:

Q0 and q0 respectively

Q0 and q1 respectively

Q0 and q2 respectively

Q0 and q3 respectively

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.

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.

20. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

7

10

12

11

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.

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.