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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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.