Breaking News
Home / MCQ Computer Science / Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-44

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-44

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

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

Explanation: A turing machine can have many applications like : Enumerator (A turing machine with an output printer), function computer, etc.

3. Which of the following grammars are in Chomsky Normal Form:
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

Explanation: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and so on.

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

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.

5. If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned

Explanation: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.

6. The language accepted by a turing machine is called ____________
a) Recursive Ennumerable
b) Recursive
c) Both (a) and (b)
d) None of the mentioned

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.

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

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

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

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

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

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

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

Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.

14. The moves in the PDA is technically termed as:
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned

Explanation: A turnstile notation is used for connecting pairs od ID’s taht represents one or many moves of a PDA.

15. Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned