Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 19
Q261:
Fill in the blank: If there are n distinguishable strings with respect to language L, then any FA recognizing L must have at least _______ states.
A. n
B. n/2
C. 2n
D. n+1
Correct Answer:
A
Chapter: 19
Q262:
According to the theorem, if a language L over an alphabet ∑ has n distinguishable strings, then the FA recognizing L must have at least _______ states.
A. n states
B. n/2 states
C. 2n states
D. n+1 states
Correct Answer:
A
Chapter: 19
Q263:
Fill in the blank: In proving the theorem about FA states, if two strings x and y are distinguishable with respect to L, they must end in _______ states in the FA.
A. Different
B. Same
C. Either
D. Uncertain
Correct Answer:
A
Chapter: 19
Q264:
What does the proof of the theorem show about an FA recognizing a language with n distinguishable strings?
A. It must have at least n states
B. It must have exactly n states
C. It can have fewer than n states
D. It must have at least n+1 states
Correct Answer:
A
Chapter: 19
Q265:
Fill in the blank: The language L of strings ending in 01 and the strings 110 and 010011 are _______ with respect to L.
A. Distinguishable
B. Indistinguishable
C. Identical
D. Not related
Correct Answer:
A
Chapter: 20
Q266:
How many states must any FA accepting L20 have at least?
A. 2^20 states
B. 2^10 states
C. 2^15 states
D. 2^5 states
Correct Answer:
A
Chapter: 20
Q267:
In a Moore machine, what does the output table show?
A. What character is printed by each state
B. What state is entered next
C. The transition between states
D. The final state of the machine
Correct Answer:
A
Chapter: 20
Q268:
How does the output string length compare to the input string length in the given Moore machine example?
A. The output string is longer by 1
B. The output string is shorter by 1
C. The output string is the same length
D. The output string is twice as long
Correct Answer:
A
Chapter: 20
Q269:
Fill in the blank: In a Moore machine, if the machine starts from state q0 and processes the string 'abbabbba', the output string is ________.
A. 100010101
B. 10101010
C. 101010101
D. 111000111
Correct Answer:
A
Chapter: 20
Q270:
For the language L20, how are any two distinct strings x and y differentiated with respect to L20?
A. By differing in their 20th letter from the right
B. By their lengths
C. By the presence of specific substrings
D. By their first letters
Correct Answer:
A
Chapter: 20
Q271:
Fill in the blank: The set of all strings of length 20, defined over Σ, is __________ for any two strings x and y.
A. Distinguishable w.r.t. L20
B. Indistinguishable w.r.t. L20
C. Identical w.r.t. L20
D. Unrelated w.r.t. L20
Correct Answer:
A
Chapter: 20
Q272:
How many states are required for the FA to recognize the language L20, according to the example given?
A. At least 2^20 states
B. At least 2^10 states
C. At least 2^15 states
D. At least 2^5 states
Correct Answer:
A
Chapter: 20
Q273:
What is the primary difference between a Moore machine and a finite automaton discussed so far?
A. A Moore machine generates output strings
B. A Moore machine does not have states
C. A finite automaton generates output
D. A finite automaton has a transition table
Correct Answer:
A
Chapter: 21
Q274:
In the given Moore machine example, how many times does the state q3 need to be entered to get a 1 in the output string?
A. Once
B. Twice
C. Thrice
D. Four times
Correct Answer:
B
Chapter: 21
Q275:
Fill in the blank: The output string length in a Mealy machine is __________ compared to the input string length.
A. Equal
B. Longer
C. Shorter
D. Doubled
Correct Answer:
A
Chapter: 21
Q276:
What does a Mealy machine's pictorial representation include?
A. Directed edges labeled by input letters and output characters
B. Only input letters
C. Only output characters
D. Transition tables
Correct Answer:
A
Chapter: 21
Q277:
For the input string 'abbabbba', what is the output string in the given Mealy machine example?
A. 11011010
B. 10101010
C. 11100000
D. 11111
Correct Answer:
A
Chapter: 21
Q278:
Fill in the blank: The incrementing machine adds 1 to a binary number by reading the string __________.
A. From right to left
B. From left to right
C. Randomly
D. Backwards
Correct Answer:
A
Chapter: 21
Q279:
What happens when the rightmost bit of a binary number is 1 in the incrementing machine?
A. The 1 and all concatenated 1’s are converted to 0’s
B. The 1 is left unchanged
C. The binary number is reversed
D. The machine enters a no change state
Correct Answer:
A
Chapter: 21
Q280:
How many states does the incrementing machine have in the example provided?
A. 3
B. 2
C. 4
D. 1
Correct Answer:
A