Hello,
regarding theory questions in past exams, like define, provide the definition, and prove that..
for example:
With reference to the membership problem for context-free languages, answer the following
two questions.
(a) Specify the dynamic programming algorithm reported in the textbook for the solution of this
problem.
With reference to push-down automata (PDA), answer the following questions.
(a) Provide the definition of language accepted by final state and language accepted by empty stack.
(b) Prove that if PN is a PDA accepting the language N(PN) by empty stack, then there exists a
PDA PF accepting the language L(PF ) by final state such that L(PF ) = N(PN).
Introduce the definition of multi-tape TM. Highlight the basic idea behind the proof of
equivalence between multi-tape TM and standard TM, discussing also the total computation time of
the construction.
Define the Post correspondence problem (PCP) and discuss a simple example.
Provide the construction we have seen in the context-free lectures that converts a regular
expression E into a CFG G such that L(E) = L(G). The construction uses structural induction on E.
I have two questions:
the first is
a. since some of them are answered in previous exams with answer referral to section or proof in specific chapter in the John Hopcroft's book, in which the answer is too long to write in the exam, it also may contains formula, or/and diagram or/and text.... etc
my questions are :-
1. what is the sufficient answer to such questions that could be enough to get the whole mark?
2. anyone has a one consolidated document of these theory/proof question type and able to share it for convenience?
thanks