A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function I(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:

l(i,j)  = 0, if either i = 0 or j = 0
        = expr1, if i,j > 0 and X[i-1] = Y[j-1]
        = expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]

Which one of the following options is correct?

Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

Match all items in Group 1 with correct options from those given in Group 2.

Group 1

P. Regular expression
Q. Pushdown automata
R. Dataflow analysis
S. Register allocation

Group 2

1. Syntax analysis
2. Code generation
3. Lexical analysis
4. Code optimization

Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?