Test: Deterministic PDA - Computer Science Engineering (CSE) MCQ

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.

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

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

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

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

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

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.

 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.

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

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