PyQdeck LogoPyQdeckSubjects

2021 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

27 questions

  1. Q1a. Which of the following statements is/are false? A. For every nondeterministic TM, an equivalent deterministic TM exists. B. Turing recognizable languages are closed under union and complementation. C. Turing decidable languages are closed under intersection and complementation. D. Turing recognizable languages are closed under union and intersection. (i) A and D only (ii) A and C only (iii) B only (iv) C only20212m

    Module 5: Undecidability

    Which of the following statements is/are false?

    A. For every nondeterministic TM, an equivalent deterministic TM exists.
    B. Turing recognizable languages are closed under union and complementation.
    C. Turing decidable languages are closed under intersection and complementation.
    D. Turing recognizable languages are closed under union and intersection.

    (i) A and D only
    (ii) A and C only
    (iii) B only
    (iv) C only

    View this question on its own page →
    Search GoogleAsk AI
  2. Q1b. Enumerator in a Turing machine is a TM with: (i) an output printer (ii) 5 input tapes (iii) a stack (iv) None of the above20212m

    Module 4: Turing Machines (TM)

    Enumerator in a Turing machine is a TM with:

    (i) an output printer
    (ii) 5 input tapes
    (iii) a stack
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  3. Q1c. The language: L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \} is: (i) regular (ii) context-free but not regular (iii) context-sensitive but not context-free (iv) type-0 but not context-sensitive20212m

    Module 3: Context-Sensitive Languages

    The language:

    L={ambncm+n∣m,n≥1} L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \}

    is:

    (i) regular
    (ii) context-free but not regular
    (iii) context-sensitive but not context-free
    (iv) type-0 but not context-sensitive

    View this question on its own page →
    Search GoogleAsk AI
  4. Q1d. The maximum number of states of a DFA converted from an NFA with n states is: (i) n (ii) n^2 (iii) 2^n (iv) None of the above20212m

    Module 1: Introduction & Regular Languages

    The maximum number of states of a DFA converted from an NFA with nn states is:

    (i) nn
    (ii) n2n^2
    (iii) 2n2^n
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  5. Q1e. If L_1 and L_2 are CFLs, L_1 - L_2 is ____ context-free. (i) always (ii) sometimes (iii) never (iv) None of the above20212m

    Module 2: Context-Free Languages (CFL) and PDA

    If L1L_1 and L2L_2 are CFLs, L1−L2L_1 - L_2 is ____ context-free.

    (i) always
    (ii) sometimes
    (iii) never
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  6. Q1f. Which of the following does not have left recursion? (i) Chomsky Normal Form (ii) Greibach Normal Form (iii) Backus–Naur Form (iv) All of the above20212m

    Module 2: Context-Free Languages (CFL) and PDA

    Which of the following does not have left recursion?

    (i) Chomsky Normal Form
    (ii) Greibach Normal Form
    (iii) Backus–Naur Form
    (iv) All of the above

    View this question on its own page →
    Search GoogleAsk AI
  7. Q1g. For an NFA with n states, the minimized DFA has: (i) m \le 2^n (ii) n \le m (iii) one accept state (iv) m = 2^n20212m

    Module 1: Introduction & Regular Languages

    For an NFA with nn states, the minimized DFA has:

    (i) m≤2nm \le 2^n
    (ii) n≤mn \le m
    (iii) one accept state
    (iv) m=2nm = 2^n

    View this question on its own page →
    Search GoogleAsk AI
  8. Q1h. ____ is the acyclic graphical representation of a grammar. (i) Binary tree (ii) Octtree (iii) Parse tree (iv) None of the above20212m

    Module 2: Context-Free Languages (CFL) and PDA

    ____ is the acyclic graphical representation of a grammar.

    (i) Binary tree
    (ii) Octtree
    (iii) Parse tree
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  9. Q1i. A minimum state DFA for the language: L = \{ w \in \{0,1\}^* : \#0(w) \equiv 0 \mod 3,\; \#1(w) \equiv 0 \mod 5 \} has: (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20212m

    Module 1: Introduction & Regular Languages

    A minimum state DFA for the language:

    L={w∈{0,1}∗:#0(w)≡0mod  3,  #1(w)≡0mod  5} L = \{ w \in \{0,1\}^* : \#0(w) \equiv 0 \mod 3,\; \#1(w) \equiv 0 \mod 5 \}

    has:

    (i) 15 states
    (ii) 11 states
    (iii) 10 states
    (iv) 9 states

    View this question on its own page →
    Search GoogleAsk AI
  10. Q1j. The construction time for DFA from NFA with m nodes is: (i) O(m^2) (ii) O(2^m) (iii) O(m) (iv) O(\log m)20212m

    Module 1: Introduction & Regular Languages

    The construction time for DFA from NFA with mm nodes is:

    (i) O(m2)O(m^2)
    (ii) O(2m)O(2^m)
    (iii) O(m)O(m)
    (iv) O(log⁡m)O(\log m)

    View this question on its own page →
    Search GoogleAsk AI
  12. Q2a. Tabulate the Chomsky hierarchy of grammars with an example for each.20217m

    Module 1: Introduction & Regular Languages

    Tabulate the Chomsky hierarchy of grammars with an example for each.

    View this question on its own page →
    Search GoogleAsk AI
  13. Q2b. Design a finite-state machine (FSM) for a parity checker.20217m

    Module 1: Introduction & Regular Languages

    Design a finite-state machine (FSM) for a parity checker.

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3a. Construct an NFA accepting strings over \{0,1,2\} beginning with 0, followed by an odd number of 1s, ending with any number of 2s.20217m

    Module 1: Introduction & Regular Languages

    Construct an NFA accepting strings over {0,1,2}\{0,1,2\} beginning with 0, followed by an odd number of 1s, ending with any number of 2s.

    View this question on its own page →
    Search GoogleAsk AI
  15. Q3b. Construct a PDA that accepts: L = \{ u a w b : u,w \in \{a,b\}^*,\; |u| = |w| \}20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Construct a PDA that accepts:

    L={uawb:u,w∈{a,b}∗,  ∣u∣=∣w∣} L = \{ u a w b : u,w \in \{a,b\}^*,\; |u| = |w| \}

    View this question on its own page →
    Search GoogleAsk AI
  16. Q4a. Design a Turing Machine to compute n \bmod 2.20217m

    Module 4: Turing Machines (TM)

    Design a Turing Machine to compute n mod 2n \bmod 2.

    View this question on its own page →
    Search GoogleAsk AI
  17. Q4b. Design a DFA for the regular expression: 1^*(10)^*20217m

    Module 1: Introduction & Regular Languages

    Design a DFA for the regular expression:

    1∗(10)∗ 1^*(10)^*

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5a. Using the CYK algorithm, determine whether baaba is in L(G) for the grammar: `` S → AB | BC A → BA | a B → CC | b C → AB | a ``202114m

    Module 2: Context-Free Languages (CFL) and PDA

    Using the CYK algorithm, determine whether baaba is in L(G)L(G) for the grammar:

    S → AB | BC
A → BA | a
B → CC | b
C → AB | a
    View this question on its own page →
    Search GoogleAsk AI
  19. Q5b. Suppose L is CFL and R is regular: (i) Is L - R always CFL? (ii) Is R - L always CFL?202114m

    Module 2: Context-Free Languages (CFL) and PDA

    Suppose LL is CFL and RR is regular:

    (i) Is L−RL - R always CFL?
    (ii) Is R−LR - L always CFL?

    View this question on its own page →
    Search GoogleAsk AI
  20. Q6a. Show that the language: L = \{ a^{n!} : n \ge 0 \} is not regular or not context-free.20217m

    Module 1: Introduction & Regular Languages

    Show that the language:

    L={an!:n≥0} L = \{ a^{n!} : n \ge 0 \}

    is not regular or not context-free.

    View this question on its own page →
    Search GoogleAsk AI
  21. Q6b. Let G be a CFG in CNF with b variables. Show that if G derives any string using at least 2^b steps, then L(G) is infinite.20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Let GG be a CFG in CNF with bb variables. Show that if GG derives any string using at least 2b2^b steps, then L(G)L(G) is infinite.

    View this question on its own page →
    Search GoogleAsk AI
  23. Q7a. State and prove the pumping lemma for regular languages.20217m

    Module 1: Introduction & Regular Languages

    State and prove the pumping lemma for regular languages.

    View this question on its own page →
    Search GoogleAsk AI
  24. Q7b. Check whether the grammar: S \to aSa \mid bSb \mid a \mid b is ambiguous.20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Check whether the grammar:

    S→aSa∣bSb∣a∣b S \to aSa \mid bSb \mid a \mid b

    is ambiguous.

    View this question on its own page →
    Search GoogleAsk AI
  25. Q8a. Show that the function: f(x,y) = x + y is primitive recursive.20217m

    Module 5: Undecidability

    Show that the function:

    f(x,y)=x+y f(x,y) = x + y

    is primitive recursive.

    View this question on its own page →
    Search GoogleAsk AI
  26. Q8b. Construct a PDA accepting: L = \{ a^{2n}bc : n \ge 0 \}20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Construct a PDA accepting:

    L={a2nbc:n≥0} L = \{ a^{2n}bc : n \ge 0 \}

    View this question on its own page →
    Search GoogleAsk AI
  27. Q9a. Write a short note on the Post Correspondence Problem.20213.5m

    Module 5: Undecidability

    Write a short note on the Post Correspondence Problem.

    View this question on its own page →
    Search GoogleAsk AI
  28. Q9b. Write a short note on Chomsky Normal Form.20213.5m

    Module 2: Context-Free Languages (CFL) and PDA

    Write a short note on Chomsky Normal Form.

    View this question on its own page →
    Search GoogleAsk AI
  29. Q9d. Write a short note on the Pumping Lemma for CFL.20213.5m

    Module 2: Context-Free Languages (CFL) and PDA

    Write a short note on the Pumping Lemma for CFL.

    View this question on its own page →
    Search GoogleAsk AI
Next year2022