Toc Quiz Questions And Answers

16 Questions | By Dheerajjetha | Updated: Oct 13, 2022 | Attempts: 1930

Questions

Settings

How much do you know about TOC? Would you like to go through these TOC quiz questions and answers that we have brought for you? In theoretical computer science and mathematics, the theory of computation is known as the branch that focuses on what problems are able to be solved on a model of computation using an algorithm and to what degree they can be solved. Let's see what you know. All the best, and have fun!

Questions and Answers

1.

Which of the following statements is true?i) If L is a regular language, then LR is also a regular languageii) If L is a regular language, then L2 may not be a regular languageiii) The grammar {G = ({S}, {a}, S, {S->Saaa | aS| a})} is not regulariv) The grammar {G = ({S}, {a, b}, S, {S->aS | bS| })} is not regular
- A.
  
  I only
- B.
  
  I and iii and iv only
- C.
  
  Ii, iii, and iv only
- D.
  
  Iii and iv only
2.

Define FOUR (w) for a finite string w, to be the string consisting of the symbols of w in positions that are multiples of four. For example, FOUR (1110011100) = 01. If L is a regular language, then { FOUR (w): w є L} must be regular.
- A.
  
  True
- B.
  
  False
- C.
  
  Can't say
- D.
  
  None of these
3.

If L is a language over an alphabet, ∑ let NoPrefix(L) = {x є L: no proper prefix of x is in L}. If L is regular, then so is NoPrefix(L).
- A.
  
  True
- B.
  
  False
- C.
  
  Can't Say
- D.
  
  None of these
4.

Consider the language defined by the regular expression (a + b)*b⁺. Which of the following regular expressions also defines that language?
- A.
  
  (a*b+) + (b*b+)
- B.
  
  (ab + bb)* b*
- C.
  
  (a + b + ba)*b+
- D.
  
  Both a and c
5.

Convert the following DFA into a regular expression
- A.
  
  0*10*1 (0 U 10*10*1)*
- B.
  
  10* (0 U 10*10*1)* 10*
- C.
  
  (0 U 10*10*1)* 0*10*1
- D.
  
  None of the above
6.

Which of the set can be recognized by DFS automata
- A.
  
  The no. 1,2,4,…………….2n,………..written in binary
- B.
  
  The set {1, 101, 11011,1110111…}
- C.
  
  The no. 1,2,4,……………. ,………..written in unary
- D.
  
  The set of binary strings in which the no. of 0’s is the same as the no. of 1’s
7.

The pumping lemma for regular languages can be used to
- A.
  
  Prove that a given language is regular
- B.
  
  Prove that a given language is not regular
- C.
  
  Prove that all CFLs have a corresponding PDA
- D.
  
  Prove that a given CFL is inherently ambiguous
8.

Read the following statements1) For every NFA with an arbitrary no. of final states there is an equivalent NFA with only one final state2) Regular sets are closed under infinite union3) Regular sets are closed under the prefix Which of the following is true?
- A.
  
  1 & 3 are only correct statements
- B.
  
  1, 2 & 3 statements are correct
- C.
  
  1 is the only correct statement
- D.
  
  None of the above is correct
9.

The finite state machine is described by the following state diagram with A as starting state where an arc label is x/y and, x stands for 1-bit input & y stands for 2-bit output.
- A.
  
  Output 01 whenever the input sequence contains 11
- B.
  
  Output 10 whenever the input sequence contains 10
- C.
  
  Output the sum of the present and previous bits of the input
- D.
  
  None of the above
10.

Which of the following statement is true?
- A.
  
  The language { : n >= 0, n !=4} is regular
- B.
  
  The set of all real numbers is a regular language.
- C.
  
  The language { : n = i+ jk; i, k fixed, j=0,1,2………….} is regular
- D.
  
  All of the above
11.

Let r = 1(1+0)*, s= 11* 0 & t= 1*0 be 3 regular expression as which one of the following is true
- A.
  
  L(s) L(r) & L(s) L (t)
- B.
  
  L(r) L(s) & L(s) L (t)
- C.
  
  L (t) L(s) & L(r) L(s)
- D.
  
  L (t) L(s) & L(s) L(r)
12.

Which of the following is true
- A.
  
  A(ab)*a = a(ba)* & (P*Q*) = (P*+Q*)*
- B.
  
  (a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)*
- C.
  
  (a+b)*ab[(a+b)*ab(a+b)*+b*a*+b*a*] = (a+b)*
- D.
  
  None of the above
13.

A finite state machine with the following states table has a single input x & single output z. If the initial state is unknown, then the shortest input sequence to reach the final state C is
- A.
  
  01
- B.
  
  10
- C.
  
  110
- D.
  
  101
14.

Consider the following FAs. Which of the following is true?
- A.
  
  FA1 FA2
- B.
  
  FA2 FA1
- C.
  
  FA1 = FA2
- D.
  
  None of the above
15.

The language accepted by push down automaton in which the stack is limited to 10 items is best described as
- A.
  
  Context Free
- B.
  
  Regular
- C.
  
  Deterministic Context free
- D.
  
  Recursive
16.

Regular expression corresponding to the following FA will be
- A.
  
  (ab + aaa*b)*(a+ )
- B.
  
  (ab + aaa*b)*
- C.
  
  (a + aaa*b)* (a+ )
- D.
  
  None of the above