Explore topic-wise InterviewSolutions in .

Right CHOICE is (a) L={a^ib^i|i>=0}

To elaborate: NONE.

Correct OPTION is (b) transitive and reflexive

Easiest explanation: A STRING w is accepted by a PDA if and only if (s,w, E) |-* (F, e, e)

Right answer is (a) End symbol

The explanation: The tuple DEFINITION of context free grammar is: (V, T, P, S) where V=set of VARIABLES, T=set of terminals, P=production, S= STARTING Variable.

Right choice is (a) ACCEPT and REJECT

For explanation: Halting states are the new tuple members introduced in turing MACHINE and is of TWO types: Accept Halting STATE and Reject Halting State.

Correct answer is (d) 10

To elaborate: The 10-tuple can be STATED as: NSA=‹Q,Σ,Γ,δ,q0,Z0,F,[,],]›.

Right choice is (a) Statement: The operations of PDA NEVER work on elements, other than the top.

For explanation I WOULD say: The term pushdown refers to the fact that the elements are pushed down in the stack and as PER the LIFO principle, the operation is always performed on the top ELEMENT of the stack.

Correct answer is (c) ((a+b)(a+b)(a+b)(a+b))*

Best EXPLANATION: Other mentioned options do not MANY of the combinations while OPTION c SEEMS most RELIABLE.

Correct OPTION is (b) 625

To ELABORATE: USING the permutation rule, we can calculate that there will be TOTAL of 625 permutations on 5 elements TAKING 4 as the length.

Correct answer is (a) MOVES

To EXPLAIN: Using this NOTATION, we can DEFINE moves and further acceptance of a string by the machine.

The CORRECT OPTION is (a) * represents that the left hand side PRODUCTION rule has no RIGHT or left context.

The best explanation: Here the production P is from the DEFINITION of Context free grammar and thus, has no right or left context.

The CORRECT option is (a) = L(M) and vice versa.

To elaborate: There exists TWO lemma’s such that:

a) Given a grammar G, construct the PDA and SHOW the equivalence

b) Given a PDA, construct a grammar and show the equivalence

Right answer is (d) all of the mentioned

The best I can EXPLAIN: The empty STACK in the END is our requirement relative to finite state automatons.

Right choice is (d) All of the mentioned

To explain: CONTEXT FREE GRAMMARS are CLOSED under kleene operation, union and CONCATENATION too.

The correct option is (d) Stack

The explanation is: A push down automata uses a stack to carry out its OPERATIONS. They are more CAPABLE than the finite AUTOMATONS but LESS than the turing model.

The CORRECT OPTION is (b) Context Sensitive Language

The explanation is: A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production RULES may be surrounded by a context of terminal and non terminal symbols. Context-sensitive GRAMMARS are more general than context-free grammars, in the SENSE that there are some languages that cannot be described by context-free grammars, but can be described by CSG.

Right answer is (c) CHOMSKY

For explanation I would say: Chomsky HIERARCHY DECIDE four type of language :Type 3- REGULAR Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively Ennumerable language.

Correct choice is (a) (CURRENT STATE, unprocessed input, STACK content)

To ELABORATE: A machine CONFIGURATION is an element of K×Σ*×Γ*.

(p,w,γ) = (current state, unprocessed input, stack content).

Correct choice is (b) eR=E

For explanation I WOULD say: e is the IDENTITY for concatenation. Thus, eR=R.

The CORRECT choice is (c) Nested Stack Automaton

To EXPLAIN: In computational theory, a nested stack automaton is a finite automaton which makes USE of stack containing data which can be ADDITIONAL STACKS.

The CORRECT option is (b) Sentential form

For explanation: Example: For any grammar, productions be:

S->AB

A->AAA| ^

B->Bb| ^

The partial derivation TREE can be drawn as:

SINCE it has the root as S, this can be said to be in sentential form.

The CORRECT answer is (b) Unit production

Explanation: A->ε is termed as NULL production while A->B is termed as Unit production.

The correct option is (a) STRING

To explain I would say: Null production is ALWAYS TAKEN as a string in computational THEORY.

Right ANSWER is (a) No state p has two OUTGOING transitions

The explanation is: A DETERMINISTIC Push Down AUTOMATA is a Push Down Automata in which no state p has two or more transitions.

Correct answer is (d) Counter Automaton

Easy explanation: This CLASS of AUTOMATA can recognize a set of CONTEXT FREE languages like {anbn|n belongs to N}

Correct choice is (d) All of the mentioned

For EXPLANATION I would say: NSPACE or NON DETERMINISTIC space is the COMPUTATIONAL resource describing the memory space for a non deterministic TURING machine.

Right answer is (b) {abnc|n=1}

Easy explanation: Here, the FIRST mentioned b is FIXED while the other can be ZERO or can be repeated any number of TIME.

The correct choice is (a) Complement

Easiest explanation: Deterministic CONTEXT free LANGUAGES(one accepted by PDA by FINAL state), are drastically different from the context free languages. For example they are closed under COMPLEMENTATION and not union.

Right option is (c) Turing machine

Explanation: Pushdown Automaton USES stack as an AUXILIARY storage for its operations. Turing machines USE Queue for the same.

The correct option is (a) Statement: EVERY context free GRAMMAR can be TRANSFORMED into an equvalent non deterministic push down automata.

Explanation: Push down automata is the automaton machine for all the context free grammar or Type 2 languages.

Right option is (d) All of the MENTIONED

To EXPLAIN: All the assertions mentioned are THEOREMS or COROLLARY.

The correct option is (d) All of the mentioned

The explanation: The instantaneous description of a PDA is represented by 3 tuple:

(q,w,s)

where q is the STATE, w is the unconsumed input and s is the stack content.

The correct answer is (a) Statement: Counter Automaton can exist for the language L={0^i1^i|i>=0}

The EXPLANATION: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a SURPLUS of. The STATE q0 is the initial state and the only accepting state.

The correct choice is (d) All of the mentioned

The explanation is: Yes, a PDA can be REPRESENTED USING a TRANSITION DIAGRAM, transition table and an instantaneous DESCRIPTION.

Correct answer is (C) Both (a) and (b)

Easiest explanation: A linearly bounded AUTOMATA is a restricted non deterministic turing MACHINE which is capable of accepting ant CONTEXT free grammar.

Correct CHOICE is (d) Two of the MENTIONED is correct

Explanation: The LANGUAGE is recursive and every recursive language is a CFL.

The correct answer is (a) rejected

To explain: To accept a string, PDA NEEDS to HALT at an ACCEPTING state and with a STACK EMPTY, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.

Right CHOICE is (d) None of the mentioned

Explanation: Here are some process used to simplify a CFG but to produce an equivalent grammar:

a) REMOVAL of useless symbols(non TERMINAL) b) Removal of Unit productions and C) Removal of Null productions.

The correct option is (a, d)

The EXPLANATION: PUSH and pop are the OPERATIONS we perform to operate a stack. A stack follows the LIFO principle, which states its RULE as: Last In First Out.

Right OPTION is (c) DISJOINT

Easiest explanation: TWO sets are CALLED disjoint if they have no elements in common i.e.RÇT=Æ.