Automata Theory MCQ (Multiple Choice Questions)
1. A language L from a grammar G = { VN, Σ, P, S} is?
a. Set of symbols over VN
b. Set of symbols over Σ
c. Set of symbols over P
d. Set of symbols over S
2. What is the transitional function of a DFA?
a. Q X Σ→Q
b. Q X Σ→2Q
c. Q X Σ→2n
d. Q X Σ→Qn
3. What is the transitional function of an NFA?
a. Q X Σ→Q
b. Q X Σ→2Q
c. Q X Σ→2n
d. Q X Σ→Qn
4. Maximum number of states of a DFA converted from an NFA with nstates is?
a. n
b. n2
c. 2n
d. None of the mentioned
5. What are the fundamental limitations of finite state machines?
a. It cannot remember arbitrarily large amounts of information
b. In cannot remember state transitions
c. In cannot remember Grammar for a language
d. It cannot remember Language generated from a grammar
6. The String WWR is not recognized by any FSM because _____________
a. An FSM cannot remember arbitrary amounts amount of information
b. An FSM cannot fix the midpoint
c. An FSM cannot match W with WR
d. An FSM cannot remember the first and last inputs
7. A finite automata recognizes ____________
a. Any Language
b. Context Sensitive Language
c. Context Free Language
d. Regular Language
8. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a. reflexive
b. transitive
c. symmetric
d. reflexive and transitive
9. The non-Kleene Star operation accepts the following String of finite length over set A = {0,1} | where string s contains an even number of 0 and 1
a. 01,0011,010101
b. 0011,11001100
c. ε,0011,11001100
d. ε,0011,11001100
10. A regular language over an alphabet ∑ cannot be obtained from the primary languages using the operation
a. Union
b. Concatenation
c. Kleene*
d. All of the mentioned
11. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be their states; Statement 3: The edges or arcs can be used for transitions
Hint: Nodes and Edges are for trees and forests, too.
Which of the following makes the correct combination?
a. Statement 1 is false, but Statements 2 and 3 are correct
b. Statements 1 and 2 are correct, while three is wrong
c. None of the mentioned statements are correct
d. All of the mentioned
12. The minimum number of states required to recognize an octal number divisible by 3 are/is
a. 1
b. 3
c. 5
d. 7
13. Which of the following is not a part of a 5-tuple finite automata?
a. Input alphabet
b. Transition function
c. Initial State
d. Output Alphabet
14. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________
a. Compiler
b. Interpreter
c. Loader and Linkers
d. None of the mentioned
15. The number of elements in the Set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is _________
a. 7
b. 6
c. 8
d. 5
16. For the following state change in FA, which of the following codes is an incorrect option?
a. δ (m, 1) = n
b. δ (0, n) = m
c. δ (m,0) = ε
d.
17. Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
a. {aa, ab, ba, bb}
b. {aaaa, abab, ε, abaa, aabb}
c. {aaa, aab, aba, bbb}
d. All of the mentioned
18. Moore Machine is an application of:
a. Finite automata without input
b. Finite automata with output
c. Non Finite automata with output
d. None of the mentioned
19. In Moore’s machine, the output is produced over the change of:
a. transitions
b. states
c. all of the mentioned
d. none of the mentioned
20. For a give Moore Machine, Given Input=’101010’, thus the output would be of length:
a. |Input|+1
b. |Input|
c. |Input-1|
d. Cannot be predicted
21. Which of the following delays signal transmission along the wire by one step (clock pulse)?
a. NAND box (NOT AND)
b. AND box
c. OR box
d. DELAY box
22. For the given input, which of the following provides the Boolean OR for the given input-output?
a. NAND box (NOT AND)
b. DELAY box
c. AND box
d. OR box
23. For a given input, which of the following provides the complement of Boolean AND output?
a. DELAY box
b. OR box
c. NAND box (NOT AND)
d. AND box
24. If L1 and L2 are regular languages, then which of the following is/are also everyday Language (s)?
a. L1 + L2
b. L1L2
c. L1
d. All of the above
25. If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.
a. True
b. False
26. A Regular Expression for the Language of words containing an even number of a’s is?
a. (a+b)aba(a+b)
b. a+bbaabaa
c. (a+b)ab(a+b)
d. (b+aba)
27. The language regular expression can express session is called a common language.
a. True
b. False
28. Which of the following languages are examples of non-regular languages?
a. PALINDROME and EVEN-EVEN
b. EVEN-EVEN and PRIME
c. PALINDROME and PRIME
d. FACTORIAL and SQURE
29. Can languages be proven regular or unstable when using a pumping lemma?
a. True
b. False
30. Which of the following is the infinite Language?
a. EQUAL-EQUAL
b. EVEN-EVEN
c. FACTORIAL
d. PALINDROME
31. Select the nearest to the Myhill Nerode theorem.
a. L partitions Σinto distinct classes.
b. If L is regular, L generates a finite number of classes.
c. If L generates a finite number of classes, then L is regular.
d. All of the above
32. If we want to describe the complement of a language, then it is essential to describe the ——————- of that Language over which the Language is defined.
a. Regular Expression
b. String
c. Word
d. Alphabet
33. “CFG” stands for _________
a. Context-Free Graph
b. Context Free Grammar
c. Context Finite Graph
d. Context Finite Grammar
34. Which of the following states are called the halt states?
a. ACCEPT AND START
b. ACCEPT and READ
c. ACCEPT and REJECT
d. ACCEPT AND WRITE
35. The part of a PDA where the input string is placed before it is run is called?
a. State
b. Transition
c. Input Tape
d. Output Tape
36. In non-deterministic PDA, there is more than one outgoing edge from which of the following states?
a. READ or POP
b. START or READ
c. POP or REJECT
d. PUSH or POP
37. Which of these machines can accept lambda?
a. Moore
b. Mealy
c. NFA
d. None
38. Which of these is the correct formula to calculate the memory required for a machine?
a. 2n
b. 2 n+1
c. 2 n+1 -1
d. None
39. If X and Y are strings of language L and XZϵL & YZ₲L, then it’s a———- language.
a. Distinguishable
b. Un-Distinguishable
c. Both A&B
d. None
40. Which of these is the right formula for De-Morgan’s law?
a. (L1c U L2c)c = L1∩L2
b. (L1∩L2c)U(L1c∩L2) c
c. (L1∩L2c)c U (L1c∩L2)
d. None
41. Machines in which the outputs are attached with transitions are known as.
a. TG
b. FA
c. NFA
d. OUTPUT machines
42. A language that has no regular expression is known as?.
a. TG
b. FA
c. Both A&B
d. None
43. ————- is an intermediate structure between FA and TG.
a. GTG
b. NFA
c. Both A & B
d. None
44. A machine in which the outputs are attached with states is known as.
a. Moore machine
b. Mealy Machine
c. Both A&B
d. None
45. If a machine takes 010 as input and produces 101 as out, what will it be known as?
a. Increment
b. Moore
c. Mealy
d. Compliment
46. ————– Have there been no final states for some?
a. FA
b. TG
c. GTG
d. All
47. If a string has no letters, it is not known as.
a. ʎ
b. Empty String
c. Null String
d. None
48. What is the written expression for the reverse of a string?
a. rev(s)
b. reverse(s)
c. reverse IsI
d.None
49. If a language contains all strings of length three, which expression will represent it?
a. (a+b)(a+b)2
b. (a+b)*
c. (a+b)(a+b)(a+b)
d. None
50. this expression (a+b)*will not define which of the following strings.
a. bbba
b. aaa
c. bbb
d. None
51. ———– Can have multiple start states?
a. GTG
b. TG
c. FA
d. Both a & b
52. What is it known as if we have multiple transitions against a single input letter?
a. NFA
b. DFA
c. Both a & b
d. None
53. Concatenation of a finite number of letters from the alphabet is called a.
a. Alphabets
b. Language
c. Grammar
d. None
54. If a production is applied in the leftmost nonterminal in the working String, then it is.
a. Left Recursion
b. Polish Notation
c. CFG
d. Left derivation
55. If a CFG has the form nonterminal , one terminal, or two , it is known as nonterminal.
a. CFG
b. CFL
c. CNF
d. None
56. If a CFG has the form nonterminal one terminal.
a. Unit Production
b. ʎ-production
c. Null able
d. Null
57. A production of the form. Nonterminal ʎ
a. Unit Production
b. ʎ-production
c. Null able
d. Null production
58. Which is the right combination for Polish Notation?
a. Operator-Operand-Operand
b. Operand-Operator-Operand
c. Operand-Operand-Operator
d. None
59. It will be known if we can draw more than one tree for Grammar.
a. Ambiguous
b. Context free
c. Both A & B
d. None
60. The Maze game is an example of this.
a. TG
b. FA
c. NFA
d. None
61. Terminals, nonterminal, and production are the terminology of
a. CFL
b. Chomsky
c. PDA
d. None
62. If L is regular, then L generates a finite no of classes of the rule.
a. Myhill Nerode Theorem
b. Pumping Lemma
c. Both A&B
d. None
63. If two machines create the same output, they will be known as.
a. Decrement
b. Moore
c. Mealy
d. Equivalent