Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

Which one of the following is a top-down parser?

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:

$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$

For the correct answer strings to the previous question, how many derivation trees are there?

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute (bⁿ mod m),$$0 \le b,n \le m$$?