Theory of Computation Online Test - Set 02 - ObjectiveBooks

Theory of Computation Online Test - Set 02

Practice Test: Question Set - 02


1. A grammar that produces more than one parse tree for some sentence is called
    (A) Ambiguous
    (B) Unambiguous
    (C) Regular
    (D) None of these

2. If e1 and e2 are the regular expressions denoting the languages L1 and L2 respectively, then which of the following is wrong?
    (A) (e1) | (e2) is a regular expression denoting L∪ L2
    (B) (e1) .(e2) is a regular expression denoting L1​. L2
    (C) φ is not a regular expression
    (D) {ex} is a regular expression denoting L1*

3. R1 and R2 are regular sets. Which of the following is not true?
    (A) R1 n R2 need not be regular
    (B) S* – R1 is regular
    (C) R1 ? R2 is regular
    (D) Is regular

4. The following grammar
    G = (N, T, P, S)
     N = {S, A, B}
     T = {a, b, c}
     P : S ? aSa
     S ? aAa
     A ? bB
     B ? bB
     B ? c is
    (A) Is type 3
    (B) Is type 2 but not type 3
    (C) Is type 1 but not type 2
    (D) Is type 0 but not type 1

5. If L1 = {x  | x is a palindrome in (0 + 1)*}
    L2 = {letter (letter + digit)* };
    L3 = (0n 1n 2n | n > 1}
    L4 = {ambnam+n | m, n > 1}
then which of the following statement is correct ?
    (A) L1 is context free language and L3 is context sensitive language
    (B) L2 is a regular set and L4 is not a context free language
    (C) Both L1 and L2 are regular sets
    (D) Both L3 and L4 are context-sensitive languages

6. Consider the following language,
    L = {anbmcpdq|n, m, p, q = 1}
L is?
    (A) CFL but not regular
    (B) CSL but not CFL
    (C) Regular
    (D) Type 0 language but not type 1

7. In the following grammar:
    x : : = x  ⊕ y |  4
    y : : = z * y I 2
    z : : = id
which of the following is true?
    (A) ⊕ is left associative while * is right associative
    (B) Both ⊕ and * are left associative
    (C) ⊕ is right associative while * is left associative
    (D) None of these

8. The concept of FSA is much used in this part of the compiler
    (A) Lexical analysis
    (B) Parser
    (C) Code generation
    (D) Code optimization

9. Pumping lemma is generally used for proving that
    (A) Given grammar is regular
    (B) Given grammar is not regular
    (C) Whether two given regular expressions are equivalent or not
    (D) None of these

10. A language is represented by a regular expression (a)*(a + ba). Which of the following string does not belong to the regular set represented by the above expression.
    (A) aaa
    (B) aba
    (C) ababa
    (D) aa

Show and hide multiple DIV using JavaScript View All Answers

 Next Tests: