PyQdeck LogoPyQdeckSubjects

2022 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

29 questions

  1. Q1a. The minimum number of states required to recognize an octal number divisible by 3 is: (i) 1 (ii) 3 (iii) 5 (iv) 720222m

    Module 1: Introduction & Regular Languages

    The minimum number of states required to recognize an octal number divisible by 3 is:

    (i) 1
    (ii) 3
    (iii) 5
    (iv) 7

    View this question on its own page →
    Search GoogleAsk AI
  2. Q1b. For a given Moore machine, given input = 101010, the output would be of length: (i) |Input| + 1 (ii) |Input| (iii) |Input| − 1 (iv) Cannot be predicted20222m

    Module 1: Introduction & Regular Languages

    For a given Moore machine, given input = 101010, the output would be of length:

    (i) |Input| + 1
    (ii) |Input|
    (iii) |Input| − 1
    (iv) Cannot be predicted

    View this question on its own page →
    Search GoogleAsk AI
  3. Q1c. The total number of states and transitions required to form a Moore machine that produces residue mod 3 are: (i) 3 and 6 (ii) 3 and 5 (iii) 2 and 4 (iv) 2 and 520222m

    Module 1: Introduction & Regular Languages

    The total number of states and transitions required to form a Moore machine that produces residue mod 3 are:

    (i) 3 and 6
    (ii) 3 and 5
    (iii) 2 and 4
    (iv) 2 and 5

    View this question on its own page →
    Search GoogleAsk AI
  4. Q1d. Which of the following is a correct statement? (i) Moore machine has no accepting states. (ii) Mealy machine has accepting states. (iii) We can convert Mealy to Moore but not vice versa. (iv) All of the above20222m

    Module 1: Introduction & Regular Languages

    Which of the following is a correct statement?

    (i) Moore machine has no accepting states.
    (ii) Mealy machine has accepting states.
    (iii) We can convert Mealy to Moore but not vice versa.
    (iv) All of the above

    View this question on its own page →
    Search GoogleAsk AI
  5. Q1e. The minimum number of transitions to reach the final state as per the regular expression: \{a, b\}^* baaa is: (i) 4 (ii) 5 (iii) 6 (iv) 320222m

    Module 1: Introduction & Regular Languages

    The minimum number of transitions to reach the final state as per the regular expression:

    {a,b}∗baaa \{a, b\}^* baaa

    is:

    (i) 4
    (ii) 5
    (iii) 6
    (iv) 3

    View this question on its own page →
    Search GoogleAsk AI
  6. Q1f. Let w = xyz, y is the middle portion and |y| > 0. Repeating y zero or more times before checking membership in L is known as: (i) Generating (ii) Pumping (iii) Producing (iv) None of the above20222m

    Module 1: Introduction & Regular Languages

    Let w=xyzw = xyz, yy is the middle portion and ∣y∣>0|y| > 0. Repeating yy zero or more times before checking membership in LL is known as:

    (i) Generating
    (ii) Pumping
    (iii) Producing
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  7. Q1g. A Turing machine that is able to simulate other Turing machines is called: (i) nested Turing machine (ii) universal Turing machine (iii) counter machine (iv) None of the above20222m

    Module 4: Turing Machines (TM)

    A Turing machine that is able to simulate other Turing machines is called:

    (i) nested Turing machine
    (ii) universal Turing machine
    (iii) counter machine
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  8. Q1h. A recursively enumerable language L is recursive if: (i) L' is recursively enumerable (ii) every sequence of moves of T halts (iii) Both (i) and (ii) (iv) None of the above20222m

    Module 5: Undecidability

    A recursively enumerable language LL is recursive if:

    (i) L′L' is recursively enumerable
    (ii) every sequence of moves of TT halts
    (iii) Both (i) and (ii)
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  9. Q1i. RASP stands for: (i) Random Access Storage Program (ii) Random Access Stored Program (iii) Randomly Accessed Stored Program (iv) Random Access Storage Programming20222m

    Module 4: Turing Machines (TM)

    RASP stands for:

    (i) Random Access Storage Program
    (ii) Random Access Stored Program
    (iii) Randomly Accessed Stored Program
    (iv) Random Access Storage Programming

    View this question on its own page →
    Search GoogleAsk AI
  10. Q1j. A language L is Turing decidable if: (i) recursive (ii) TM recognizes L (iii) TM accepts L (iv) None of the above20222m

    Module 4: Turing Machines (TM)

    A language LL is Turing decidable if:

    (i) recursive
    (ii) TM recognizes LL
    (iii) TM accepts LL
    (iv) None of the above

    View this question on its own page →
    Search GoogleAsk AI
  12. Q2a. Design a DFA for strings over \{a, b\} containing at least three occurrences of bbb (overlapping allowed). Example: bbbbbb is accepted.20227m

    Module 1: Introduction & Regular Languages

    Design a DFA for strings over {a,b}\{a, b\} containing at least three occurrences of bbb (overlapping allowed). Example: bbbbbb is accepted.

    View this question on its own page →
    Search GoogleAsk AI
  13. Q2b. Let L \subseteq \{0,1,2\}^* be strings without consecutive identical symbols (no 00, no 11, no 22). Design a DFA for L.20227m

    Module 1: Introduction & Regular Languages

    Let L⊆{0,1,2}∗L \subseteq \{0,1,2\}^* be strings without consecutive identical symbols (no 0000, no 1111, no 2222). Design a DFA for LL.

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3a. Prove that if L is accepted by a PDA, then L can be generated by a CFG.20227m

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

    Prove that if LL is accepted by a PDA, then LL can be generated by a CFG.

    View this question on its own page →
    Search GoogleAsk AI
  15. Q3b. Design an NPDA (empty stack and final state acceptance) for: L = \{\text{palindromes over } \{a,b\}\}20227m

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

    Design an NPDA (empty stack and final state acceptance) for:

    L={palindromes over {a,b}} L = \{\text{palindromes over } \{a,b\}\}

    View this question on its own page →
    Search GoogleAsk AI
  16. Q4a. Design Mealy and Moore machines to detect the sequence 1010 (overlapping allowed). Then convert the Moore machine into a Mealy machine and prove equivalence.20227m

    Module 1: Introduction & Regular Languages

    Design Mealy and Moore machines to detect the sequence 1010 (overlapping allowed). Then convert the Moore machine into a Mealy machine and prove equivalence.

    View this question on its own page →
    Search GoogleAsk AI
  17. Q4b. Show whether the given grammar is ambiguous: S \to a \mid abSb \mid aAb \\ A \to bS \mid aAAb20227m

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

    Show whether the given grammar is ambiguous:

    S→a∣abSb∣aAbA→bS∣aAAb S \to a \mid abSb \mid aAb \\ A \to bS \mid aAAb

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5a. Give examples of L_1 and L_2 such that: (i) L_1 is regular, L_2 is not regular, and L_1 - L_2 is regular. (ii) L_1 and L_2 are not regular but L_1 \cup L_2 is regular.20227m

    Module 1: Introduction & Regular Languages

    Give examples of L1L_1 and L2L_2 such that:

    (i) L1L_1 is regular, L2L_2 is not regular, and L1−L2L_1 - L_2 is regular.
    (ii) L1L_1 and L2L_2 are not regular but L1∪L2L_1 \cup L_2 is regular.

    View this question on its own page →
    Search GoogleAsk AI
  19. Q5b. Show that the language of palindromes over \{a, b\} is not regular.20227m

    Module 1: Introduction & Regular Languages

    Show that the language of palindromes over {a,b}\{a, b\} is not regular.

    View this question on its own page →
    Search GoogleAsk AI
  20. Q6a. Construct a CFG for: \{ 0^i 1^j 2^k \mid i + j \ge 2k \}20227m

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

    Construct a CFG for:

    {0i1j2k∣i+j≥2k} \{ 0^i 1^j 2^k \mid i + j \ge 2k \}

    View this question on its own page →
    Search GoogleAsk AI
  21. Q6b. Convert the CFG to GNF: S \to AB \mid BC \\ A \to aB \mid bA \mid a \\ B \to bB \mid cC \mid b \\ C \to c20227m

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

    Convert the CFG to GNF:

    S→AB∣BCA→aB∣bA∣aB→bB∣cC∣bC→c S \to AB \mid BC \\ A \to aB \mid bA \mid a \\ B \to bB \mid cC \mid b \\ C \to c

    View this question on its own page →
    Search GoogleAsk AI
  23. Q7a. Design a Turing machine that accepts all palindromes over: \Sigma = \{ a, b \}20227m

    Module 4: Turing Machines (TM)

    Design a Turing machine that accepts all palindromes over:

    Σ={a,b} \Sigma = \{ a, b \}

    View this question on its own page →
    Search GoogleAsk AI
  24. Q7b. Explain the Myhill–Nerode theorem for minimization of automata with an example.20227m

    Module 1: Introduction & Regular Languages

    Explain the Myhill–Nerode theorem for minimization of automata with an example.

    View this question on its own page →
    Search GoogleAsk AI
  25. Q8a. Construct FOLLOW sets for the grammar: E \to T E' \\ E' \to +\,T\,E' \mid \varepsilon \\ T \to F T' \\ T' \to -\,F\,T' \mid \varepsilon \\ F \to (E) \mid id20227m

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

    Construct FOLLOW sets for the grammar:

    E→TE′E′→+ T E′∣εT→FT′T′→− F T′∣εF→(E)∣id E \to T E' \\ E' \to +\,T\,E' \mid \varepsilon \\ T \to F T' \\ T' \to -\,F\,T' \mid \varepsilon \\ F \to (E) \mid id

    View this question on its own page →
    Search GoogleAsk AI
  26. Q8b. Show that the language: L = \{ a^{n^2} b^n \mid n \ge 0 \} is not regular.20227m

    Module 1: Introduction & Regular Languages

    Show that the language:

    L={an2bn∣n≥0} L = \{ a^{n^2} b^n \mid n \ge 0 \}

    is not regular.

    View this question on its own page →
    Search GoogleAsk AI
  27. Q9a. Prove that the halting problem for Turing machines is recursively undecidable.20227m

    Module 5: Undecidability

    Prove that the halting problem for Turing machines is recursively undecidable.

    View this question on its own page →
    Search GoogleAsk AI
  28. Q9b(i). Write a short note on Deterministic PDA vs. Non-deterministic PDA.20227m

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

    Write a short note on Deterministic PDA vs. Non-deterministic PDA.

    View this question on its own page →
    Search GoogleAsk AI
  29. Q9b(ii). Write a short note on Chomsky Normal Form (CNF).20227m

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

    Write a short note on Chomsky Normal Form (CNF).

    View this question on its own page →
    Search GoogleAsk AI
  30. Q9b(iii). Write a short note on Multi-stack Turing Machine.20227m

    Module 4: Turing Machines (TM)

    Write a short note on Multi-stack Turing Machine.

    View this question on its own page →
    Search GoogleAsk AI
  31. Q9b(iv). Write a short note on Finite-state Machine (FSM).20227m

    Module 1: Introduction & Regular Languages

    Write a short note on Finite-state Machine (FSM).

    View this question on its own page →
    Search GoogleAsk AI
Previous year2021Next year2023