Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A