FORMAL LANGUAGE AND AUTOMATA THEORY
MCQ
1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
2. A language can be generated from simple primitive language in a simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
3. Which of the following does not represent the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
4. According to the given language, which among the following expressions does it corresponds
to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
6. If R represents a regular language, which of the following represents the Venn-diagram most
correctly?
a) An Irregular Set
b) R*
c) R complement
d) R reverse
7. The given NFA corresponds to which of the following Regular expressions?
a) (0+1) *(00+11) (0+1) *
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
Answer: a
11. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
12. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
13. Number of states require to accept string ends with 10.
a) 3
b) 2
c) 1
d) can’t be represented.
14. Extended transition function is .
a) Q * Σ* -> Q
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ
15. δ*(q,ya) is equivalent to .
a) δ((q,y),a)
b) δ(δ*(q,y),a)
c) δ(q,ya)
d) independent from δ notation
16. String X is accepted by finite automata if .
a) δ*(q,x) E A
b) δ(q,x) E A
c) δ*(Q0,x) E A
d) δ(Q0,x) E A
17. 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
18. Language of finite automata is.
a) Type 0
b) Type 1
c) Type 2
d) Type 3
19. Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned
20. Number of final state require to accept Φ in minimal finite automata.
a) 1
b) 2
c) 3
d) None of the mentioned
21. Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba
b) ab(ab)*bba
c) ab(a+b)*bba
d) All of the mentioned
22. How many DFA’s exits with two states over input alphabet {0,1} ?
a) 16
b) 26
c) 32
d) 64
23. The basic limitation of finite automata is that
a) It can’t remember arbitrary large amount of information.
b) It sometimes recognize grammar that are not regular.
c) It sometimes fails to recognize regular grammar.
d) All of the mentioned
24. Number of states require to simulate a computer with memory capable of storing ‘3’ words
each of length ‘8’.
a) 3 * 28
b) 2(3*8)
c) 2(3+8)
d) None of the mentioned
25. FSM with output capability can be used to add two given integer in binary representation.
This is
a) True
b) False
c) May be true
d) None of the mentioned
26. All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv
27. Which of the technique can be used to prove that a language is non regular?
a) Ardens theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned
28. Which of the following language regular?
a) {aibi|i>=0}
b) {aibi|0<i<5}
c) {aibi|i>=1}
d) None of the mentioned
29. Which of the following are non regular?
a) The set of strings in {a,b}* with an even number of b’s
b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3.
Interpret the empty strings e as the number 0.
d) None of the mentioned
30. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
31. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes.
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L
must have atmost k states.
c) A language L is NFA-regular if and only if it is DFA-regular.
d) None of the mentioned
32. Myphill Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) None of the mentioned
33. Which of the following are related to tree automaton?
a) Myphill Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned
34. Given languages:
i) {anbn|n>=0}
ii) <div>n</div>n
iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii
35. Finite state machine are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitarily large amount of data
c) Even if the mid point is known, it cannot find whether the second half matches the first
d) All of the mentioned
36. Which of the following regular expression resembles the given diagram?
a) {a}*{b}*{a,b}
b) {a,b}*{aba}
c) {a,b}*{bab}
d) {a,b}*{a}*{b}*
37. Lexemes can be referred to as:
a) elements of lexicography
b) sequence of alphanumeric characters in a token
c) lexical errors
d) none of the mentioned
38. The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using
finite automata:
a) 4
b) 3
c) 5
d) 6
39. The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) Both (a) and (b)
d) None of the mentioned
40. d(q,X)=(r,Y,D) where D cannot be:
a) L
b) R
c) S
d) None of the mentioned
41. Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned
42. Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol
43. If T1 and T2 are two turing machines. The composite can be represented using the
expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned
44. The following turing machine acts like:
a) Copies a string
b) Delete a symbol
c) Insert a symbol
d) None of the mentioned
45. What does the following transition graph shows:
a) Copies a symbol
b) Reverses a string
c) Accepts a pal
d) None of the mentioned
46. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
47. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
48. Which of the following allows stacked values to be sub-stacks rather than just finite
symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
49. A non deterministic two way, nested stack automaton has n-tuple definition. State the value
of n.
a) 5
b) 8
c) 4
d) 10
50. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
51. The class of languages not accepted by non deterministic, nonerasing stack automata is
_______
a) NSPACE(n2)
b) NL
c) CSL
d) All of the mentioned
52. A push down automaton with only symbol allowed on the stack along with fixed symbol.
a) Embedded PDA
b) Nested Stack automata
c) DPDA
d) Counter Automaton
53. Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Pop
54. A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned
55. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned
Answers:
1. (a) 15. (b) 29. (d) 43. (a)
2. (b) 16. (c ) 30. (b) 44. (b)
3. (d) 17. (a) 31. (b) 45. (c )
4. (d) 18. (d) 32. (c ) 46. (d)
5. (a) 19. (b) 33. (d) 47. (a)
6. (b) 20. (d) 34. (d) 48. (c )
7. (a) 21. (c ) 35. (d) 49. (d)
8. (b) 22. (d) 36. (b) 50. (b)
9. (b) 23. (a) 37. (b) 51. (d)
10. (a) 24. (b) 38. (a) 52. (d)
11. (b) 25. (a) 39. (c ) 53. (a)(d)
12. (d) 26. (d) 40. (c ) 54. (c)
13. (a) 27. (b) 41. (c ) 55. (c )
14. (a) 28. (b) 42. (d)