Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. The languages -------------- are the examples of non regular languages.
a. PALINDROME and PRIME
b. PALINDROME and EVEN-EVEN
c. EVEN-EVEN and PRIME
d. FACTORIAL and SQURE
Q. Languages are proved to be regular or non regular using pumping lemma.
a. True
b. False
c. Not always true
d. can’t say anything
Q. ___________ states are called the halt states.
a. ACCEPT and REJECT
b. ACCEPT and READ
c. ACCEPT AND START
d. ACCEPT AND WRITE
Q. The part of an FA, where the input string is placed before it is run, is called _______
a. State
b. Transition
c. Input Tape
d. Output Tape
Q. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state
a. START or READ
b. POP or REJECT
c. READ or POP
d. PUSH or POP
Q. If an effectively solvable problem has answered in yes or no, then thissolution is called
a. Decision procedure
b. Decision method
c. Decision problem
d. Decision making
Q. The symbols that can’t be replaced by anything are called -----------------
a. Productions
b. Terminals
c. Non-terminals
d. All of above
Q. Left hand side of a production in CFG consists of:
a. One terminal
b. More than one terminal
c. One non-terminal
d. Terminals and non-terminals
Q. Choose the incorrect statement.
a. A Mealy machine generates no language as such
b. A Mealy machine has no terminal state
c. For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine
d. All of these
Q. In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called
a. Dead State
b. Waste Basket
c. Davey John Locker
d. All of these
Q. Which statement is true?
a. The tape of turing machine is infinite.
b. The tape of turing machine is finite.
c. The tape of turing machine is infinite when the language is regular
d. The tape of turing machine is finite when the language is nonregular.
Q. If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option:
a. (r1)(r2)
b. (r1 + r2)
c. (r2)(r1)
d. (r1)
Q. Which of the following will be used for text searching application-?
a. NFA
b. DFA
c. PDA
d. None of these
Q. Context free grammar is used for-
a. Lexical analyzer
b. Document type definition (DTD)
c. Text pattern searching
d. Both a & c
Q. The set strings of 0's and 1's with atmost one pair consecutive one's-
a. (0+1)*(01)(10)(0+1)*
b. (0+1)*(01)*(10)(0+1)*
c. (0+1)*(01)(10)*(0+1)*
d. (0+!)(01)*(10)*(0+1)