Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 30
Q381:
The string "aa" is accepted by an FA. What does this imply about the language of the FA?
A. The language is empty
B. The FA accepts finite words
C. The FA accepts some strings
D. The language is infinite
Correct Answer:
C
Chapter: 30
Q382:
If an FA has N states, what is the maximum length of the word that needs to be tested to determine if it accepts an infinite language?
A. N
B. 2N
C. N^2
D. 3N
Correct Answer:
B
Chapter: 30
Q383:
What is a sufficient condition for an FA to accept no word?
A. The FA has no initial state
B. The FA has no final state
C. The FA has an infinite loop
D. The FA has multiple initial states
Correct Answer:
B
Chapter: 30
Q384:
The Pumping Lemma is used to prove that ______.
A. FAs accept infinite languages
B. FAs reject certain words
C. FAs accept finite languages
D. FAs accept regular expressions
Correct Answer:
A
Chapter: 30
Q385:
A regular expression that contains the symbol * usually defines ______.
A. finite language
B. infinite language
C. empty language
D. singular language
Correct Answer:
B
Chapter: 30
Q386:
In a given FA, which of the following is NOT accepted by the FA?
A. aa
B. baa
C. bbb
D. aaa
Correct Answer:
C
Chapter: 30
Q387:
If an FA with N states accepts no word, how many strings of length less than N should be tested?
A. m^N
B. N^m
C. mN + mN+1
D. m^2N
Correct Answer:
C
Chapter: 31
Q388:
What does CFG stand for in automata theory?
A. Context Free Grammar
B. Computer Functional Grammar
C. Complex Finite Grammar
D. Control Flow Grammar
Correct Answer:
A
Chapter: 31
Q389:
What are the symbols called that cannot be replaced by anything in CFG?
A. NonTerminals
B. Terminals
C. Productions
D. Start symbols
Correct Answer:
B
Chapter: 31
Q390:
Which of the following generates a Context-Free Language (CFL)?
A. DFA
B. CFG
C. PDA
D. NFA
Correct Answer:
B
Chapter: 31
Q391:
In CFG, what is the role of 'S'?
A. A terminal symbol
B. Start symbol
C. Nonterminal
D. End symbol
Correct Answer:
B
Chapter: 31
Q392:
What is the meaning of the production rule N → Λ?
A. N can be deleted from the string
B. N must repeat
C. N generates a nonterminal
D. N generates a terminal
Correct Answer:
A
Chapter: 31
Q393:
Which of the following is a non-terminal symbol in CFG?
A. a
B. S
C. b
D. ∧
Correct Answer:
B
Chapter: 31
Q394:
What is the main purpose of a compiler in programming?
A. To translate assembly language
B. To translate high-level language
C. To compile machine code
D. To execute code
Correct Answer:
B
Chapter: 31
Q395:
Which of the following is an example of a Context Free Grammar (CFG) production rule?
A. S → aS
B. a → S
C. X → a + S
D. Y → a + Λ
Correct Answer:
A
Chapter: 31
Q396:
In CFG, what is the set of rules that define valid strings called?
A. Productions
B. Nonterminals
C. Syntax
D. Semantics
Correct Answer:
A
Chapter: 31
Q397:
What does S → SS mean in a context-free grammar?
A. S generates two S symbols
B. S generates two terminals
C. S generates a nonterminal and a terminal
D. S generates Λ
Correct Answer:
A
Chapter: 31
Q398:
A grammar where S → aS and S → Λ generates which of the following languages?
A. a*
B. b*
C. a+b
D. (a+b)*
Correct Answer:
A
Chapter: 31
Q399:
Which production rule allows deletion of nonterminal N?
A. N → a
B. N → Λ
C. N → S
D. N → b
Correct Answer:
B
Chapter: 31
Q400:
What type of language is generated by the grammar Σ = {a, b} with productions S → a, S → b, S → Λ?
A. Finite strings of a’s and b’s
B. Infinite strings of a’s
C. Only one a and one b
D. Only empty string
Correct Answer:
A