Theory Of Computation (Toc) Quiz

Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Sathya Bama
S
Sathya Bama
Community Contributor
Quizzes Created: 1 | Total Attempts: 3,585
| Attempts: 3,587
SettingsSettings
Please wait...
  • 1/20 Questions

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

    • Ab*b*
    • A*b*
    • B*b
    • B*ab*
Please wait...
About This Quiz

This Theory of Computation quiz assesses understanding of Finite State Machines, regular expressions, and grammars with questions from past ISRO exams. It evaluates skills in designing and analyzing computational models, crucial for advanced studies in computer science.

Theory Of Computation (Toc) Quiz - Quiz

Quiz Preview

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

    Correct Answer
    A. 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."

    Rate this question:

  • 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

    Correct Answer
    A. 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.

    Rate this question:

  • 4. 
    The given finite automata represent which of the languages? - ProProfs

    The given finite automata represent which of the languages?

    • {1, 0}* {01}

    • {1, 0}* {1}

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

    • 1*0* {0, 1}

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

    Rate this question:

  • 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? - ProProfs

    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

    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.

    Rate this question:

  • 6. 

    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

    Correct Answer
    A. (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.

    Rate this question:

  • 7. 
    The DFA generated from the following NFA? ISRO CS2013 - ProProfs

    The DFA generated from the following NFA? ISRO CS2013

    • Q0, q1, q2

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

    • Q0, [q1, q2]

    • [q0, q1], q2

    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.

    Rate this question:

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

    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

    Correct Answer
    A. 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.

    Rate this question:

  • 9. 
    The FSM (Finite State Machine) machine pictured in the figure below represents what language? (ISRO-2018)   - ProProfs

    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

    Correct Answer
    A. 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.

    Rate this question:

  • 10. 

    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*

    Correct Answer
    A. 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.

    Rate this question:

  • 11. 

    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

    Correct Answer
    A. 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.

    Rate this question:

  • 12. 

    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

    Correct Answer
    A. 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.

    Rate this question:

  • 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

    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.

    Rate this question:

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

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

    • A

    • B

    • C

    • D

    Correct Answer
    A. 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.

    Rate this question:

  • 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

    Correct Answer
    A. 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.

    Rate this question:

  • 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

    Correct Answer
    A. (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.

    Rate this question:

  • 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

    Correct Answer
    A. 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.

    Rate this question:

  • 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. - ProProfs

    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

    Correct Answer
    A. 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.

    Rate this question:

  • 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

    Correct Answer
    A. 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.

    Rate this question:

  • 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

    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.

    Rate this question:

Quiz Review Timeline (Updated): Aug 29, 2023 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

  • Current Version
  • Aug 29, 2023
    Quiz Edited by
    ProProfs Editorial Team
  • Jul 26, 2019
    Quiz Created by
    Sathya Bama
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.