PyQdeck LogoPyQdeckSubjects

2021 question paper

Formal Language & Automata Theory

27 questions

  1. Q1a. Which of the following statements is/are False? A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 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 4: Turing machines

    Which of the following statements is/are False?

    A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
    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 is a Turing machine with (i) an output printer (ii) 5 input tapes (iii) a stack (iv) None of the above20212m

    Module 4: Turing machines

    Enumerator is a Turing machine 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 \{a^mb^nc^{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 2: Context-free languages and pushdown automata

    The language {ambncm+n∣m,n≥1}\{a^mb^nc^{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 and finite automata

    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 L1 and L2 are context-free languages, L1-L2 is \_\_\_\_ context-free. (i) always (ii) sometimes (iii) never (iv) None of the above20212m

    Module 2: Context-free languages and pushdown automata

    If L1 and L2 are context-free languages, L1-L2 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 recursions? (i) Chomsky normal form (ii) Greibach normal form (iii) Backus-Naur form (iv) All of the above20212m

    Module 2: Context-free languages and pushdown automata

    Which of the following does not have left recursions?

    (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. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n20212m

    Module 1: Introduction, Regular languages and finite automata

    Let NN be an NFA with nn states and let MM be the minimized DFA with mm states recognizing the same language. Which of the following is necessarily true?

    (i) m≤2nm \le 2^n
    (ii) n≤mn \le m
    (iii) MM has 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 and pushdown automata

    ____ 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 deterministic FA accepting the language L = \{w \mid w \in \{0, 1\}^*\} where number of 0's and 1's in w are divisible by 3 and 5 respectively, has (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20212m

    Module 1: Introduction, Regular languages and finite automata

    A minimum state deterministic FA accepting the language

    L={w∣w∈{0,1}∗}L = \{w \mid w \in \{0, 1\}^*\}

    where number of 0's and 1's in ww are divisible by 3 and 5 respectively, 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 an equivalent NFA (m number of node) is (i) O(m^2) (ii) O(2^m) (iii) O(m) (iv) O(\log m)20212m

    Module 1: Introduction, Regular languages and finite automata

    The construction time for DFA from an equivalent NFA (mm number of node) 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 Chomsky hierarchy of grammar with an example for each.20217m

    Module 1: Introduction, Regular languages and finite automata

    Tabulate Chomsky hierarchy of grammar with an example for each.

    View this question on its own page →
    Search GoogleAsk AI
  13. Q2b. Design a finite state machine or abstract model for Parity checker.20217m

    Module 1: Introduction, Regular languages and finite automata

    Design a finite state machine or abstract model for Parity checker.

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3a. Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.20217m

    Module 1: Introduction, Regular languages and finite automata

    Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.

    View this question on its own page →
    Search GoogleAsk AI
  15. Q3b. Construct a push-down automata that accepts the following language: L = \{uawb : u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}20217m

    Module 2: Context-free languages and pushdown automata

    Construct a push-down automata that accepts the following language:

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

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

    Module 4: Turing machines

    Design a Turing machine (TM) to compute n mod 2n \bmod 2.

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

    Module 1: Introduction, Regular languages and finite automata

    Design a DFA corresponding to regular expression 1∗(10)∗1^*(10)^*.

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5a. Consider the grammar: S \to AB \mid BC A \to BA \mid a B \to CC \mid b C \to AB \mid a Use the CYK algorithm to determine whether the given string "baaba" is in L(G) or not.202114m

    Module 2: Context-free languages and pushdown automata

    Consider the grammar:

    S→AB∣BCS \to AB \mid BC
    A→BA∣aA \to BA \mid a
    B→CC∣bB \to CC \mid b
    C→AB∣aC \to AB \mid a

    Use the CYK algorithm to determine whether the given string "baaba" is in L(G)L(G) or not.

    View this question on its own page →
    Search GoogleAsk AI
  19. Q5b. Suppose L is context free and R is regular, justify your answer with the help of example: (i) Is L-R necessarily context free? (ii) Is R-L necessarily context free?202114m

    Module 2: Context-free languages and pushdown automata

    Suppose LL is context free and RR is regular, justify your answer with the help of example:

    (i) Is L−RL-R necessarily context free?
    (ii) Is R−LR-L necessarily context free?

    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 language.20217m

    Module 1: Introduction, Regular languages and finite automata

    Show that the language L={an!:n≥0}L = \{a^{n!} : n \ge 0\} is not regular or not context-free language.

    View this question on its own page →
    Search GoogleAsk AI
  21. Q6b. Let G be a context-free grammar in Chomsky normal form that contains b variable. Show that if G generates some string using a derivation with at least 2^b steps, then L(G) is infinite.20217m

    Module 2: Context-free languages and pushdown automata

    Let GG be a context-free grammar in Chomsky normal form that contains bb variable. Show that if GG generates some string using a derivation with 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 pumping lemma for regular sets.20217m

    Module 1: Introduction, Regular languages and finite automata

    State and prove pumping lemma for regular sets.

    View this question on its own page →
    Search GoogleAsk AI
  24. Q7b. Show given grammar over alphabet \{a, b\}, verify whether it is ambiguous or unambiguous: S \to aSa \mid bSb \mid a \mid b \mid \epsilon20217m

    Module 2: Context-free languages and pushdown automata

    Show given grammar over alphabet {a,b}\{a, b\}, verify whether it is ambiguous or unambiguous:

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

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

    Module 4: Turing machines

    Show that the sum function

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

    is primitive recursive.

    View this question on its own page →
    Search GoogleAsk AI
  26. Q8b. Construct a PDA that accepts the language L = \{a^{2n}bc \mid n \ge 0\} by final state and empty stack.20217m

    Module 2: Context-free languages and pushdown automata

    Construct a PDA that accepts the language L={a2nbc∣n≥0}L = \{a^{2n}bc \mid n \ge 0\} by final state and empty stack.

    View this question on its own page →
    Search GoogleAsk AI
  27. Q9a. Write a short note on: Post-correspondence problem20213.5m

    Module 5: Undecidability

    Write a short note on: Post-correspondence problem

    View this question on its own page →
    Search GoogleAsk AI
  28. Q9b. Write a short note on: Chomsky normal form20213.5m

    Module 2: Context-free languages and pushdown automata

    Write a short note on: Chomsky normal form

    View this question on its own page →
    Search GoogleAsk AI
  29. Q9c. Write a short note on: Multistack Turing machine20213.5m

    Module 4: Turing machines

    Write a short note on: Multistack Turing machine

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