Theory of Computation Quiz | Theory of Computation Objective Type Questions and Answers

Sports GK Questions and Answers 2024 (Latest Updated)

Awards & Honours GK Questions 2024 (Latest Updated)

Questions
21 If two finite state machines are equivalent they should have the same number of
A States
B Edges
C States and edges
D None of these

Answer: None of these
22 Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
A a*b
B a*baa*
C a*ba*
D None of the above

Answer: None of the above
Advertisement
Article and Schedule Quiz Start Test!
DOWNLOAD CURRENT AFFAIRS PDF FROM APP
23 Finite state machine___________recognize palindromes.
A Can
B Cannot
C May
D May not

Answer: Cannot
24 Which of the following statements is/are FALSE?

(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

(2) Turing recognizable languages are closed under union and complementation.

(3) Turing decidable languages are closed under intersection and complementation

(4) Turing recognizable languages are closed under union and intersection.

A 1 and 4 only
B 1 and 3 only
C 2 only
D 3 only

Answer: 2 only
25 Which of the following is most powerful?
A DFA
B NDFA
C 2PDA
D DPDA

Answer: 2PDA
26 Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below : The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
A 5
B 4
C 3
D 2

Answer: 3
27 Context free languages are not closed under
A Union
B Concatenation
C Closure
D Iteration

Answer: Iteration
28 An FSM can be used to add two given integers.This remark is
A True
B False
C May be true
D None of the above

Answer: False
29 The following CFG S®aB|bA, A®a|as|bAA, B®b|bs|aBB generates strings of terminals that have
A Odd number of a’s and odd number of b’s
B Even number of a’s and even number of b’s
C Equal number of a’s and b’s
D Not equal number of a’s and b’s

Answer: Equal number of a’s and b’s
30 The language accepted by finite automata is
A Context free
B Regular
C Non regular
D None of these

Answer: Regular
31 Which of the following permanent database that has an entry for each terminal symbol ?
A Literal table
B Identifier table
C Terminal table
D Source table

Answer: Terminal table
32 A PDM behaves like a TM when the number of auxiliary memory it has is
A Zero
B One or more
C Two or more
D None of these

Answer: Two or more
33 Two finite states are equivalent if they
A Have same number of states
B Have same number of edges
C Have same number of states and edges
D Recognize same set of tokens

Answer: Have same number of states and edges
34 Finite automata are used for pattern matching in text editors for
A Compiler lexical analysis
B Programming in localized application
C Both A and B
D None of the above

Answer: Compiler lexical analysis
35 A formal grammar is a___________for rewriting strings.
A Set of rules
B Set of functions
C Both A and B
D None of the above

Answer: Set of rules
36 Which is not the correct statement(s) ?

(i) Every context sensitive language is recursive.

(ii) There is a recursive language that is not context sensitive.

A is true, (ii) is false.
B is true and (ii) is true.
C is false, (ii) is false.
D is false and (ii) is true.

Answer: is true and (ii) is true.
37 Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

A 1, 2 and 3
B 2, 3 and 4
C 1, 2 and 4
D 1, 3 and 4

Answer: 1, 2 and 4
38 Which one of the following statement is false ?
A Context-free languages are closed under union
B Context-free languages are closed under concatenation
C Context-free languages are closed under intersection
D Context-free languages are closed under Kleene closure

Answer: Context-free languages are closed under Kleene closure
39 How many states can a process be in ?
A 2
B 3
C 4
D 5

Answer: 5
40 The basic limitation of a FSM is that
A It cannot remember arbitrary large amount of information
B It sometimes recognizes grammar that are not regular
C It sometimes fails to recognize grammars that are regular
D All of the above

Answer: It cannot remember arbitrary large amount of information

Random GK Questions

Q. When a constitutional amendment bill goes to the President, he
Q. The maximum strength of Rajya Sabha is
Q. Production function is the relationship between
Q. ‘Dandia’ is popular dance of
Q. Which one of the following was not authored by Annie Besant?
Q. The Iron and Steel Industry at which of the following places was developed with German technical collaboration ?
Assam Direct Recruitment Test Series

Teacher Eligibility Test

Assam Direct Recruitment Test Series