Test: Deterministic PDA


10 Questions MCQ Test Theory of Computation | Test: Deterministic PDA


Description
This mock test of Test: Deterministic PDA for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Deterministic PDA (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Deterministic PDA quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Deterministic PDA exercise for a better result in the exam. You can find other Test: Deterministic PDA extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

The transition a Push down automaton makes is additionally dependent upon the:

Solution:

A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.

QUESTION: 2

A PDA machine configuration (p, w, y) can be correctly represented as:

Solution:

 A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).

QUESTION: 3

|-* is the __________ closure of |-

Solution:

 A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)

QUESTION: 4

With reference of a DPDA, which among the following do we perform from the start state with an empty stack?

Solution:

The empty stack in the end is our requirement relative to finite state automatons.

QUESTION: 5

A DPDA is a PDA in which:

Solution:

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

QUESTION: 6

Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.

Solution:

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

QUESTION: 7

 If the PDA does not stop on an accepting state and the stack is not empty, the string is 

Solution:

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.

QUESTION: 8

A language accepted by Deterministic Push down automata is closed under which of the following?

Solution:

 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.

QUESTION: 9

Which of the following is a simulator for non deterministic automata?

Solution:

JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.

QUESTION: 10

 Finite-state acceptors for the nested words can be:

Solution:

The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.