Multiple choice question for engineering
Set 1
1. If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct
Answer
Answer: c [Reason:] Lr is defined as the reversal of a language. Lr is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}
2. If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned
Answer
Answer: d [Reason:] Lr, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.
3. If E=F+G;
Er=?
a) Fr+Gr
b) (F+G)r
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of reversals, concatenation and Kleene.
4. If E= FG, Er=?
a) FrGr
b) GrFr
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: b [Reason:] If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R
5. Simplify the following identity:
E=01*+10*
ER=?
a) (1*0+0*1)
b) (01*10*)R
c) (0*1+10*)
d) All of the mentioned
Answer
Answer: a [Reason:] 01*+10*
ER=(01*)R+(10*)R=>(1*)R0R+(0*)R1R=>1*0+0*1
6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
Answer
Answer: d [Reason:] Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.
7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned
Answer
Answer:
abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.
8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned
Answer
Answer: b [Reason:] h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).
9. While proving Inverse Homomorphism, which of the following steps are needed?
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned
Answer
Answer: d [Reason:] While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.
10. 8. 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) Homomorphism
b) Inverse Homomorphism
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: b [Reason:] Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.
Set 2
1. According to the rice’s theorem, If P is a non trivial property, Lp is :
a) infinite
b) decidable
c) undecidable
d) none of the mentioned
Answer
Answer: c [Reason:] Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.
2. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
a) partial functions
b) piecewise functions
c) both (a) and (b)
d) none of the mentioned
Answer
Answer: a [Reason:] A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.
3. Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
a) there exists a TM that recognizes the language in S
b) there exists a TM that recognizes the language not in S
c) both (a) and (b)
d) none of the mentioned
Answer
Answer: c [Reason:] According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.
4. Which of the following set of computable functions are decidable?
a) The class of computable functions that are constant, and its complement
b) The class of indices for computable functions that are total
c) The class of indices for recursively enumerable sets that are cofinite
d) All of the mentioned
Answer
Answer: d [Reason:] According to Rice’s theorem, if there exists atleast one computable function in a particular class C of computable functions and another computable function not in C then the problem deciding whether a particular program computes a function in C is undecidable.
5. Which of the following statements are undecidable?
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned
Answer
Answer: d [Reason:] All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
6. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned
Answer
Answer: b [Reason:] Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.
7. State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.
a) true
b) false
Answer
Answer: a [Reason:] The MPCP is : Given lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?
8. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
Answer
Answer: a [Reason:] PCP or Post Correspondence problem is an undecidable decision problem.
9. Can a Modified PCP problem be reduced to PCP?
a) yes
b) no
Answer
Answer: a [Reason:] Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
a) C is undecidable if C is reducible to B
b) C is undecidable if B is reducible to C
c) C is decidable if A is reducible to C
d) C is decidable if C is reducible to B’s complement.
Answer
Answer: b [Reason:] As B is undecidable and it can be reduced to C, C is also an undecidable problem.
Set 3
1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
Answer
Answer: a [Reason:] A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.
2. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned
Answer
Answer: c [Reason:] Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.
3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned
Answer
Answer: d [Reason:] The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.
4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
Answer
Answer: c [Reason:] The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
5. For the given Regular expression, the minimum number of terminals required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
Answer
Answer: b [Reason:] The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a
a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned
Answer
Answer: b [Reason:] The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.
7. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned
Answer
Answer: c [Reason:] We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.
8. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned
Answer
Answer: a [Reason:] The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.
9. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned
Answer
Answer: c [Reason:] L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
10. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
Answer
Answer: a [Reason:] It is just required to put the value in the variables in the question and check if it satisfies or not.
Set 4
1.Given Language: L= {xϵ∑= {a, b} |x has a substring ‘aa’ in the production}. Which of the corresponding representation notate the same?
a)
b)
c)
d)
Answer
Answer: a [Reason:] The states transited has been written corresponding to the transitions as per the row and column. The row represents the transitions made and the ultimate.
2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information what is the identity element for the string?
a) u-1
b) v-1
c) u-1v-1
d) ε
Answer
Answer: d [Reason:] Identity relation: εw = wε = w, thus the one satisfying the given relation will be the identity element.
3.Which of the following substring will the following notation result?
a) 0101011
b) 0101010
c) 010100
d) 100001
Answer
Answer: c [Reason:] The given DFA notation accepts the string of even length and prefix ‘01’.
4.Predict the following step in the given bunch of steps which accepts a strings which is of even length and has a prefix=’01’
δ (q0, ε) =q0 < δ(q0,0) =δ (δ (q0, ε),0) =δ(q0,0) =q1 < _______________
a) δ (q0, 011) =δ (δ (q0,1), 1) =δ (q2, 1) =q3
b) δ (q0, 01) =δ (δ (q0, 0), 1) = δ (q1, 1) =q2
c) δ (q0, 011) =δ (δ (q01, 1), 1) =δ (q2, 0) =q3
d) δ (q0, 0111) =δ (δ (q0, 011), 0) = δ (q3, 1) =q2
Answer
Answer: b [Reason:] Here, δ refers to transition function and results into new state or function when an transition is performed over its state.
5. Fill the missing blank in the given Transition Table:
Language L= {xϵ∑= {0,1} |x accepts all the binary strings not divisible by 3}
a) Q0
b) Q1
c) Q2
d) No Transition
Answer
Answer: Q1 [Reason:] The tabular representation of DFA is quite readable and can be used to some ore complex problems. Here, we need to form the transition graph and fill up the given blank.
6.Which among the following is the missing transition in the given DFA?
L= {xϵ∑= {a, b} | x starts with a and ends with b}
a) δ (q0, a) =q0
b) δ (F, a) =q1
c) δ (F, a) =D
d) δ (q1, a) =D
Answer
Answer: b [Reason:] For the given Language, the transition missing is δ (F, a) =q1.
7.The complement of a language will only be defined when and only when the __________ over the language is defined.
a) String
b) Word
c) Alphabet
d) Grammar
Answer
Answer: c [Reason:] It is not possible to define the complement of a language without defining the input alphabets. Example: A language which does not consist of substring ‘ab’ while the complement would be the language which does contain a substring ‘ab’.
8.Which among the following is not notated as infinite language?
a) Palindrome
b) Reverse
c) Factorial
d) L={ab}*
Answer
Answer: Factorial [Reason:] Factorial, here is the most appropriate non-infinite domain. Otherwise, palindrome and reverse have infinite domains.
9.Which among the following states would be notated as the final state/acceptance state?
L= {xϵ∑= {a, b} | length of x is 2}
a) q1
b) q2
c) q1, q2
d) q3
Answer
Answer: b [Reason:] According to the given language, q2 Is to become the final/acceptance state in order to satisfy.
10.Which of the following are the final states in the given DFA according to the Language given.?
L= {xϵ∑= {a, b} |length of x is at most 2}
a) q0, q1
b) q0, q2
c) q1, q2
d) q0, q1, q2
Answer
Answer: d [Reason:] According to the given language, the length is at most 2, thus the answer is found accordingly.
Set 5
1. Fill in the blank with an appropriate option.
In automata theory, ___________ is said to be Computationally Universal if can be used to simulate any single taped Turing Machine.
a) Computer’s instruction set
b) A programming language
c) Cellular Automaton
d) All of the mentioned
Answer
Answer: d [Reason:] Computationally Universal or Turing Complete is a set of data manipulation rules if it can be used to simulate a single-taped turing machine.
2. Give a classic example of the concept of turing complete.
a) lambda calculus
b) C++
c) Lisp
d) All of the mentioned
Answer
Answer: d [Reason:] Most of the programming languages, conventional or unconventional are turing complete. Functional languages like Lisp and Haskell are also turing complete.
3. Let two machines be P and Q. The state in which P can simulate Q and Q can simulate P is called:
a) Turing Equivalence
b) State Equivalence
c) Universal Turing Machine
d) None of the mentioned
Answer
Answer: a [Reason:] It is a closely related concept with Turing complete. It says, two computers P and Q are called equivalent if P can simulate Q and Q can simulate P.
4. Which of the following remarks the given statement?
Statement: Any function whose values can be computed by an algorithm, can be computed by a Turing machine.
a) Smn theorem
b) Structured Program theorem
c) Church-Turing thesis
d) None of the mentioned
Answer
Answer: c [Reason:] The following conclusion is laid down from the Church-Turing thesis:
Any function whose values can be computed by an algorithm, can be computed by a Turing machine. If any real world computer can be simulated by a turing machine, it is Turing equivalent to a Turing Machine.
5. Which of the following can be used to simulate any turing machine?
a) Finite State Automaton
b) Universal Turing Machine
c) Counter machines
d) All of the mentioned
Answer
Answer: b [Reason:] The computational aspect of any possible real world computer can be simulated using an Universal Turing Machine so can be any turing machine.
6. State true or false:
Statement: Inorder to show something is Turing complete, it is enough to demonstrate that it can be used to simulate some Turing complete system.
a) true
b) false
Answer
Answer: a [Reason:] Yes it is. For instance, an imperative language is called Turing complete if it tends to have conditional branching and an ability to maintain an arbitrary number of symbols.
7. Which of the following can lack in a Universal computer?
a) Turing Complete Instruction set
b) Infinite memory
c) Infinite time
d) None of the mentioned
Answer
Answer: d [Reason:] Real computers which are manufactured till date, all are similar to single taped turing machine. However, they have limited physical resources so they are linearly bounded complete on the contrary.
8. Which among are not the results of computational theory?
a) In general, it is impossible to predict that what a Turing-complete program will do over an arbitrarily long time.
b) It is impossible to determine for every input, whether the program will eventually stop or continue forever.
c) It is not possible to determine whether a program will return true or false.
d) None of the mentioned
Answer
Answer: d [Reason:] All of the following mentioned are the conclusions of automata theory or computability theory.
9. Which of the games fill under the category of Turing-complete?
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) All of the mentioned
Answer
Answer: d [Reason:] Many games fall under the category og turing complete:
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) Conway’s Game of Life
e) Pokemon Yellow, etc.
10. Which of the following a Non-turing Complete language?
a) Regular Language
b) Context free grammars
c) Epigram
d) All of the mentioned
Answer
Answer: There exists some computational languages which are not turing complete. Regular language which is accepted by finite automata tops the list. Other examples are pixel shader languages embedded in Direct3D and OpenGL extensions.
