Crowdly

Which of the folowing is a bottom-up parser / algorithm? [There can be more than one answer]

Chomsky Normal Form

All of the above

Shift-reduce parser

CYK-algorithm

What is (are) the job(s) of a parser? [There can be more than one answer]

None of the above.

to divide string into different parts

to find a parse tree, or a derivation for a string.

to determine is a string is in the CFL

Suppose I have a machine (let's call it Monash-Sunway Machine - MSM) that can simulate all the operations in a PDA (i.e., read, push, and pop letters). Does that mean that MSM can also recognize all context-free languages?

Similar to DFA, PDA is deterministic in nature.

If a problem can be solved in polynomial time by a deterministic machine, it is in Class P.

Which of the following is true about Class NP?

Class NP contains problems that are solvable in constant time.

Class NP includes problems for which a solution can be verified in polynomial time.

✅

Every problem in NP is also in P.

Class NP includes all problems that cannot be solved.

Which of the following is a correct definition of a Polynomial Time Reduction?

A reduction where one problem can be solved by guessing the solution of another problem.

A reduction where one problem can be transformed into another problem in logarithmic time.

A reduction where the transformation of one problem to another can be done in polynomial time.

✅

A reduction where the verification of a problem's solution takes polynomial time.

Which of the following best describes Class P?

Problems that can only be verified in polynomial time.

Problems that are solvable in exponential time.

Problems that can be solved by a deterministic Turing machine in polynomial time.

Problems that require non-deterministic algorithms.

When we do a proof by contradiction using the pumping lemma for CFL, as long as we can reach a contradiction (i.e., the resulting string is NOT in the language assumed to be context-free) for just one way to divide the string W = uvxyz, then we are done.