Advertisement

Automata Theory Quiz | Automata Theory Multiple Choice Questions and Answers

Advertisement
Questions
1 For a given input, it provides the compliment of Boolean AND output.
A AND box
B DELAY box
C OR box
D NAND box (NOT AND)

Answer: NAND box (NOT AND)
2 It delays the transmission of signal along the wire by one step (clock pulse).
A DELAY box
B OR box
C NAND box (NOT AND)
D AND box

Answer: DELAY box
Advertisement
3 The terminals are designated by ________ letters, while the non-terminals are designated by ________ letters.
A Capital, small
B Small, bold
C Small, capital
D Capital, bold

Answer: Small, capital
4 Grammatical rules which do not involve the meaning of words are called ---------------
A Syntactic
B Semantics
C Both a and b
D None of given

Answer: Syntactic
5 The symbols that can’t be replaced by anything are called -----------------
A Terminals
B Non-terminals
C Productions
D All of above

Answer: Terminals
6 The symbols that must be replaced by other things are called __________
A Non-terminals
B Terminals
C Productions
D None of the above

Answer: Non-terminals
7 The grammatical rules are often called_____________
A Non-terminals
B Terminals
C Productions
D None of given

Answer: Productions
8 The productions of the form nonterminal → one nonterminal, is called _________
A Unit production
B Null able production
C Null production
D None of given

Answer: Unit production
9 CNF is stands for
A Context Normal Form
B Complete Normal Form
C Chomsky Normal Form
D None of the above

Answer: Chomsky Normal Form
10 Which of the following statement is NOT true about TG? Select correct option:
A There exists exactly one path for certain string
B There may exist more than one paths for certain string
C There may exist no path for certain string
D There may be no final state

Answer: There exists exactly one path for certain string
11 Kleene’s theorem states Select correct option:
A Finite Automata are less powerful than Pushdown Automata.
B All representations of a context free language are equivalent.
C All representations of a recursive language are equivalent
D All representations of a regular language are equivalent.

Answer: Finite Automata are less powerful than Pushdown Automata.
12 In new format of an FA (discussed in lecture 37), This state is like dead-end non final state
A REJECT
B ACCEPT
C READ
D STATR

Answer: REJECT
13 The major problem in the earliest computers was
A To display mathematical formulae
B To store the contents in the registers
C To calculate the mathematical formula
D To load the contents from the registers

Answer: To display mathematical formulae
14 Between the two consecutive joints on a path
A Any no. of characters can be pushed and one character can be popped
B One character can be pushed and any no. of characters can be popped
C One character can be pushed and one character can be popped
D Any no. of characters can be pushed and any no. of characters can be popped

Answer: Any no. of characters can be pushed and one character can be popped
15 Identify the TRUE statement:
A A PDA is non-deterministic, if there are more than one REJECT states in PDA
B Like TG, A PDA can also be non-deterministic
C A PDA is non-deterministic, if there are more than one READ states in PDA
D A PDA is never non-deterministic

Answer: Like TG, A PDA can also be non-deterministic
16 If an effectively solvable problem has answered in yes or no, then this solution is called ---------
A Decision making
B Decision method
C Decision problem
D Decision procedure

Answer: Decision procedure
17 The following problem(s) ------------- is/are called decidable problem(s).
A The two FAs are equivalent
B The two regular expressions define the same language
C Both a and b
D None of the above

Answer: Both a and b
18 To examine whether a certain FA accepts any words, it is required to seek the paths from ------- state.
A Initial to final
B Final to final
C Final to initial
D Initial to initial

Answer: Initial to final
19 Grammatical rules which involve the meaning of words are called ---------------
A Semantics
B Syntactic
C Both a and b
D None of given

Answer: Semantics
20 ___________ states are called the halt states.
A ACCEPT AND WRITE
B ACCEPT and READ
C ACCEPT AND START
D ACCEPT and REJECT

Answer: ACCEPT and REJECT
Advertisement
Advertisement

Important EBooks for Competitive Exams

VIEW ALL