1. Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?
a) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
View Answer
Explanation: Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy
|vx|>0
|vwx|<=n For any m>=0, uvnwxny ? L
2. Which of the following is/are not an application of turing machine?
a) Language Recognization
b) Computers of functions on non negative numbers
c) Generating devices
d) None of the mentioned
View Answer
Explanation: A turing machine can have many applications like : Enumerator (A turing machine with an output printer), function computer, etc.
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
View Answer
Explanation: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and so on.
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
View Answer
Explanation: 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.
a) decidable
b) solved
c) recognizable
d) none of the mentioned
View Answer
Explanation: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.
a) Recursive Ennumerable
b) Recursive
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: The language accepted by Turing machines are called recursively ennumerable (RE), and the subset of RE languages that are accepted by a turing machine that always halts are called recursive.
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
View Answer
Explanation: 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. Which of the following is a P-complete type of problem?
a) Circuit Value problem
b) Linear programming
c) Context free grammar membership
d) All of the mentioned
View Answer
Explanation: Given a context free grammar and a string, can the string be generated by the grammar? Such problems fall in the category of P-complete.
9. State true or false:
Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.
a) true
b) false
View Answer
Explanation: Handshaking lemma states that ‘Every finite undirected graph has an even number of vertices with odd degree.
10. State true or false:
S-> 0S1|01
Statement: No regular expression exists for the given grammar.
a) true
b) false
View Answer
Explanation: The grammar generates a language L such that L={0n1n|n>=1} which is not regular. Thus, no regular expression exists for the same.
11. If P is the production, for the given statement, state true or false.
P: V->(V?T)* represents that the left hand side production rule has no right or left context.
a) true
b) false
View Answer
Explanation: Here the production P is from the definition of Context free grammar and thus, has no right or left context.
12. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned
View Answer
Explanation: Other mentioned options do not many of the combinations while option c seems most reliable.
13. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
View Answer
Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned
View Answer
Explanation: A turnstile notation is used for connecting pairs od ID’s taht represents one or many moves of a PDA.
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned
View Answer
Explanation: Halting states are the new tuple members introduced in turing machine and is of two types: Accept Halting State and Reject Halting State.
