Download PDF
Free download in PDF Automata Theory Multiple Choice Questions and Answers for competitive exams. These short objective type questions with answers are very important for Board exams as well as competitive exams. These short solved questions or quizzes are provided by Gkseries.
(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
(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
(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
(5)
The symbols that can’t be replaced by anything are called -----------------
[A]
Terminals
[B]
Non-terminals
[C]
Productions
[D]
All of above
(6)
The symbols that must be replaced by other things are called __________
[A]
Non-terminals
[B]
Terminals
[C]
Productions
[D]
None of the above
(7)
The grammatical rules are often called_____________
[A]
Non-terminals
[B]
Terminals
[C]
Productions
[D]
None of given
(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
(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
(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
(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
(19)
Grammatical rules which involve the meaning of words are called ---------------
[A]
Semantics
[B]
Syntactic
[C]
Both a and b
[D]
None of given
(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
Please share this page