1. Σ = {a,b} Productions
S→XaaX
X→aX
X→bX
X→Λ
This grammar defines the language expressed by___________
a. (a+b)aa(a+b)aa
b. (a+b)aba+b)
c. (a+b)aa(a+b)
d. (a+b)a(a+b)a
Correct Answer: c
2. “CFG” stands for _________
a. Context Finite Grammar
b. Context Free Grammar
c. Context Free Graph
d. Context Finite Graph
Correct Answer: b
3. ___________ states are called the halt states.
a. ACCEPT and REJECT
b. ACCEPT and READ
c. ACCEPT AND START
d. ACCEPT AND WRITE
Correct Answer: a
4. _____________ is obviously infinite language.
a. FACTORIAL
b. PALINDROME
c. EQUAL-EQUAL
d. EVEN-EVEN
Correct Answer: b
5. A binary string is divisible by 4 if and only if it ends with:
a. 1100
b. 11
c. 100
d. 1000
Correct Answer: c
6. A deterministic turing machine is:
a. unambiguous turing machine
b. Ambiguous turing machine
c. non-deterministic
d. None
Correct Answer: a
7. A PDA machine configuration (p, w, y) can be correctly represented as:
a. (current state, unprocessed input, stack content)
b. (unprocessed input, stack content, current state)
c. (current state, stack content, unprocessed input)
d. None
Correct Answer: a
8. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation
a. Kleene*
b. All of the mentioned
c. Union
d. Concatenation
Correct Answer: b
9. A->aAa|bAb|a|b|e
Which among the following is the correct option for the given production?
a. Left most derivation
b. Right most derivation
c. Recursive inference
d. None
Correct Answer: a
10. Complement of a DFA can be obtained by
a. making starting state as final state.
b. no trival method.
c. make final as a starting state.
d. making final states non-final and non-final to final.
Correct Answer: d
11. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a. 0,2
b. 0,2,4
c. 0,1,2,3
d. 0
Correct Answer: c
12. Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
a. 3
b. 2
c. 5
d. 4
Correct Answer: c
13. If L is a regular language then, ——— is also a regular language.
a. Ls
b. Lm
c. Lx
d. L’
Correct Answer: d
14. If L1 and L2 are regular languages is/are also regular language(s).
a. L1 + L2
b. L1
c. L1L2
d. All of above
Correct Answer: d
15. If L1 and L2 are regular sets then intersection of these two will be
a. Regular
b. Non Regular
c. Recursive
d. Non Recursive
Correct Answer: a
16. If L1 and L2 are two regular languages, then L1 U L2 is not a regular.
a. FALSE
b. True
c.
d.
Correct Answer: a
17. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be
a. Regular
b. Empty set
c. Decidable
d. CFG
Correct Answer: a
18. In NFA, this very state is like dead-end non final state:
a. DISTINCT
b. START
c. REJECT
d. ACCEPT
Correct Answer: c
19. Kleene’s theorem states
Select correct option:
a. All representations of a context free language are equivalent.
b.
c. All representations of a regular language are equivalent.
d. Finite Automata are less powerful than Pushdown Automata.
Correct Answer: d
20. Language of finite automata is.
a. Type 1
b. Type 2
c. Type 3
d. Type 0
Correct Answer: c
21. Languages of a automata is
a. If it is accepted by automata
b. If it halts
c. If automata touch final state in its life time
d. All language are language of automata
Correct Answer: a
22. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:
a. {Hello, World, ε}
b. {Hello, World, Input, Output, ε}
c. {}
d. {Input, Output, ε}
Correct Answer: c
23. Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of
Select correct option:
a. FA1 and FA2
b. FA1 or FA2
c. FA2 only
d. FA1 only
Correct Answer: b
24. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’ having no e productions.
a. e ∈ L(G)
b. w ∉ L(G)
c. w ∈ L(G)
d. e ∉ L(G)
Correct Answer: d
25. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)= the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a. Inverse Homomorphism
b. Homomorphism
c. none
d.
Correct Answer: a
26. Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L,
is called Complement of the language L, denoted by Lc or L’.
a. True
b. FALSE
c.
d.
Correct Answer: a
27. NFA, in its name has ’non-deterministic’ because of :
a. The choice of path is non-deterministic
b. The state to be transited next is non-deterministic
c. The result is undetermined
d. All of the mentioned
Correct Answer: a
28. Number of final state require to accept Φ in minimal finite automata.
a. 2
b. 3
c. None of the mentioned
d. 1
Correct Answer: c
29. Number of states require to accept string ends with 10.
a. can’t be represented.
b. 3
c. 2
d. 1
Correct Answer: b
30. Predict the number of transitions required to automate the following language using only 3 states:
L= {w | w ends with 00}
a. 4
b. 5
c. 3
d. 2
Correct Answer: c
31. The Grammar can be defined as: G=(V, ∑, p, S) In the given definition, what does S represents?
a. Starting Variable
b. Sensitive Grammar
c. Accepting State
d. None of these
Correct Answer: a
32. The grammatical rules are often called_____________
a. Productions
b. Terminals
c. Non-terminals
d. All of above
Correct Answer: a
33. The language of all words (made up of a’s and b’s) with at least two a’s can not be described by the regular expression.
a. a(a+b)a(a+b)(a+b)ab
b. (a+b)aba(a+b)
c. baba(a+b)
d. NONE
Correct Answer: d
34. The language that can be expressed by any regular expression is called a Non regular language.
a. FALSE
b. True
c.
d.
Correct Answer: a
35. The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
a. 2
b. 4
c. 3
d. 1
Correct Answer: c
36. The productions of the form nonterminal → one nonterminal, is called _________
a. Unit production
b. Null production
c. Null able production
d. None
Correct Answer: a
37. The symbols that can’t be replaced by anything are called —————–
a. Non-terminals
b. Productions
c. Terminals
d. All of above
Correct Answer: a
38. The symbols that must be replaced by other things are called __________
a. Terminals
b. Productions
c. Non-terminals
d. All of above
Correct Answer: a
39. The terminals are designated by ________ letters, while the non-terminals are designated by ________ letters.
a. Capital, bold
b. Capital, small
c. Small, bold
d. Small, capital
Correct Answer: d
40. The transition a Push down automaton makes is additionally dependent upon the:
a. Stack
b. Input tape
c. terminals
d. None
Correct Answer: a
41. There are ________ tuples in finite state machine.
a. 6
b. unlimited
c. 5
d. 4
Correct Answer: c
42. What is the output for the given language?
Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output “for every occurrence of a, b as its substring. (INPUT: abaaab)
a. 0111010
b. 0010000
c. 0010001
d. 0101010
Correct Answer: c
43. Which among the following is not notated as infinite language?
a. L={ab}*
b. Factorial
c. Palindrome
d. Reverse
Correct Answer: b
44. Which of the following can accept even palindrome over {a,b}
a. NDFA
b. Push down Automata
c. Turing Machine
d. All
Correct Answer: a
45. Which of the following does not obey pumping lemma for context free languages ?
a. Unrestricted languages
b. Finite Languages
c. Context free languages
d. None
Correct Answer: a
46. Which of the following is a correct statement?
a. Mealy machine has accepting states
b. We can convert Mealy to Moore but not vice versa
c. All oh the mentioned
d. Moore machine has no accepting states
Correct Answer: d
47. Which of the following is a not a part of 5-tuple finite automata?
a. Initial State
b. Output Alphabet
c. Transition function
d. Input alphabet
Correct Answer: b
48. Which of the following is analogous to the following?
:NFA and NPDA
a. Regular language and Context Free language
b. Context free language and Context Sensitive language
c. Regular language and Context Sensitive language
d. None
Correct Answer: a
49. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a. ((a+b)(a+b)(a+b)(a+b))*
b. (bbbb+aaaa)*
c. (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
d. None
Correct Answer: a
50. Which of the following relates to Chomsky hierarchy?
a. Regular<CFL<CSL<Unrestricted
b. CFL<CSL<Unrestricted<Regular
c. CSL<Unrestricted<CF<Regular
d. None
Correct Answer: a
