PyQdeck LogoPyQdeckSubjects

2025 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

28 questions

  1. Q1a. A language is said to be recursively enumerable if it is accepted by a (i) DFA (ii) Turing Machine (iii) PDA (iv) Linear Bounded Automaton20252m

    Module 4: Turing Machines (TM)

    A language is said to be recursively enumerable if it is accepted by a

    (i) DFA
    (ii) Turing Machine
    (iii) PDA
    (iv) Linear Bounded Automaton

    View this question on its own page →
    Search GoogleAsk AI
  2. Q1b. Regular languages belong to which type in the Chomsky hierarchy? (i) Type-0 (ii) Type-2 (iii) Type-1 (iv) Type-320252m

    Module 1: Introduction & Regular Languages

    Regular languages belong to which type in the Chomsky hierarchy?

    (i) Type-0
    (ii) Type-2
    (iii) Type-1
    (iv) Type-3

    View this question on its own page →
    Search GoogleAsk AI
  3. Q1c. Which of the following languages is NOT regular? (i) {a^n b^n | n \ge 0} (ii) {a, b}* (iii) Finite languages (iv) Languages accepted by DFA20252m

    Module 1: Introduction & Regular Languages

    Which of the following languages is NOT regular?

    (i) {anbn∣n≥0a^n b^n | n \ge 0}
    (ii) {a,ba, b}*
    (iii) Finite languages
    (iv) Languages accepted by DFA

    View this question on its own page →
    Search GoogleAsk AI
  4. Q1d. Context-free languages are NOT closed under (i) Union (ii) Concatenation (iii) Intersection (iv) Kleene star20252m

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

    Context-free languages are NOT closed under

    (i) Union
    (ii) Concatenation
    (iii) Intersection
    (iv) Kleene star

    View this question on its own page →
    Search GoogleAsk AI
  5. Q1e. Which production is not allowed in a CSG? (i) AB \rightarrow BA (ii) A \rightarrow \epsilon (iii) A \rightarrow a (iv) a B \rightarrow a b20252m

    Module 3: Context-Sensitive Languages

    Which production is not allowed in a CSG?

    (i) AB→BAAB \rightarrow BA
    (ii) A→ϵA \rightarrow \epsilon
    (iii) A→aA \rightarrow a
    (iv) aB→aba B \rightarrow a b

    View this question on its own page →
    Search GoogleAsk AI
  6. Q1f. A Turing Machine that prints strings of a language is called (i) Acceptor (ii) Transducer (iii) Generator (iv) Enumerator20252m

    Module 4: Turing Machines (TM)

    A Turing Machine that prints strings of a language is called

    (i) Acceptor
    (ii) Transducer
    (iii) Generator
    (iv) Enumerator

    View this question on its own page →
    Search GoogleAsk AI
  7. Q1g. If \Sigma = \{a, b\}, then \Sigma^* contains (i) Only finite strings (ii) Only infinite strings (iii) All finite strings over \Sigma including \epsilon (iv) Only strings of equal length20252m

    Module 1: Introduction & Regular Languages

    If Σ={a,b}\Sigma = \{a, b\}, then Σ∗\Sigma^* contains

    (i) Only finite strings
    (ii) Only infinite strings
    (iii) All finite strings over Σ\Sigma including ϵ\epsilon
    (iv) Only strings of equal length

    View this question on its own page →
    Search GoogleAsk AI
  8. Q1h. The \epsilon-closure of a state is (i) The set of states reachable using \epsilon only (ii) The set of unreachable states (iii) The set of final states (iv) The dead states20252m

    Module 1: Introduction & Regular Languages

    The ϵ\epsilon-closure of a state is

    (i) The set of states reachable using ϵ\epsilon only
    (ii) The set of unreachable states
    (iii) The set of final states
    (iv) The dead states

    View this question on its own page →
    Search GoogleAsk AI
  9. Q1i. Which of the following CFLs is deterministic? (i) {a^n b^n} (ii) Arithmetic expressions (iii) Palindromes (iv) {ww^R}20252m

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

    Which of the following CFLs is deterministic?

    (i) {anbna^n b^n}
    (ii) Arithmetic expressions
    (iii) Palindromes
    (iv) {wwRww^R}

    View this question on its own page →
    Search GoogleAsk AI
  10. Q1j. Multi-tape TM is (i) More powerful than single-tape TM (ii) Less powerful (iii) Equivalent in power (iv) Not equivalent20252m

    Module 4: Turing Machines (TM)

    Multi-tape TM is

    (i) More powerful than single-tape TM
    (ii) Less powerful
    (iii) Equivalent in power
    (iv) Not equivalent

    View this question on its own page →
    Search GoogleAsk AI
  12. Q2a. Given the grammar G = (\{S\}, \{a, b\}, P, S) P: S \rightarrow aSb | ab Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.20257m

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

    Given the grammar
    G=({S},{a,b},P,S)G = (\{S\}, \{a, b\}, P, S)
    P:S→aSb∣abP: S \rightarrow aSb | ab

    Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.

    View this question on its own page →
    Search GoogleAsk AI
  13. Q2b. Explain the Chomsky hierarchy of languages with examples.20257m

    Module 1: Introduction & Regular Languages

    Explain the Chomsky hierarchy of languages with examples.

    View this question on its own page →
    Search GoogleAsk AI
  14. Q3a. Design a context-free grammar (CFG) that generates all palindromes over the alphabet {0, 1}. The grammar should generate both even-length palindromes (e.g., 0110) and odd-length palindromes (e.g., 010).20257m

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

    Design a context-free grammar (CFG) that generates all palindromes over the alphabet {0, 1}. The grammar should generate both even-length palindromes (e.g., 0110) and odd-length palindromes (e.g., 010).

    View this question on its own page →
    Search GoogleAsk AI
  15. Q3b. Given the regular expression: (0+1)^*01(0+1) Describe the language generated, and construct an equivalent DFA.20257m

    Module 1: Introduction & Regular Languages

    Given the regular expression:
    (0+1)∗01(0+1)(0+1)^*01(0+1)

    Describe the language generated, and construct an equivalent DFA.

    View this question on its own page →
    Search GoogleAsk AI
  16. Q4a. Given a DFA D over the alphabet {a, b}, perform DFA minimization and draw the equivalent minimal DFA accepting the same language. ![image](https://res.cloudinary.com/djkpavwmp/image/upload/v1766402014/portfolio_assets/ixqepvuicnt6ji19qb3o.png)20257m

    Module 1: Introduction & Regular Languages

    Given a DFA D over the alphabet {a, b}, perform DFA minimization and draw the equivalent minimal DFA accepting the same language. image

    View this question on its own page →
    Search GoogleAsk AI
  17. Q4b. Use the pumping lemma to prove that the language L = \{a^n b^n : n \ge 1\} is not regular.20257m

    Module 1: Introduction & Regular Languages

    Use the pumping lemma to prove that the language L={anbn:n≥1}L = \{a^n b^n : n \ge 1\} is not regular.

    View this question on its own page →
    Search GoogleAsk AI
  18. Q5a. Show that the following grammar is ambiguous: S \rightarrow SS | aSb | bSa | \epsilon20257m

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

    Show that the following grammar is ambiguous:
    S→SS∣aSb∣bSa∣ϵS \rightarrow SS | aSb | bSa | \epsilon

    View this question on its own page →
    Search GoogleAsk AI
  19. Q5b. Construct an NFA that accepts all strings over the alphabet {0, 1, 2} that begin with one or more 0s, followed by an odd number of 1s, and end with any number of 2s.20257m

    Module 1: Introduction & Regular Languages

    Construct an NFA that accepts all strings over the alphabet {0, 1, 2} that begin with one or more 0s, followed by an odd number of 1s, and end with any number of 2s.

    View this question on its own page →
    Search GoogleAsk AI
  20. Q6a. Prove that every context-free language is context-sensitive, but the converse is not true. Support your answer with a suitable language example.20257m

    Module 3: Context-Sensitive Languages

    Prove that every context-free language is context-sensitive, but the converse is not true. Support your answer with a suitable language example.

    View this question on its own page →
    Search GoogleAsk AI
  21. Q6b. Given the following context-sensitive grammar: S \rightarrow aSBC | abc CB \rightarrow BC aB \rightarrow ab bB \rightarrow bb bC \rightarrow bc cC \rightarrow cc Identify the language generated by the grammar. Derive the string aabbcc step by step.20257m

    Module 3: Context-Sensitive Languages

    Given the following context-sensitive grammar:
    S→aSBC∣abcS \rightarrow aSBC | abc
    CB→BCCB \rightarrow BC
    aB→abaB \rightarrow ab
    bB→bbbB \rightarrow bb
    bC→bcbC \rightarrow bc
    cC→cccC \rightarrow cc

    Identify the language generated by the grammar. Derive the string aabbcc step by step.

    View this question on its own page →
    Search GoogleAsk AI
  23. Q7a. Define a Linear Bounded Automaton (LBA). Design an LBA that accepts the language L = \{a^n b^n c^n | n \ge 1\}. Explain how tape length is restricted.20257m

    Module 3: Context-Sensitive Languages

    Define a Linear Bounded Automaton (LBA). Design an LBA that accepts the language L={anbncn∣n≥1}L = \{a^n b^n c^n | n \ge 1\}. Explain how tape length is restricted.

    View this question on its own page →
    Search GoogleAsk AI
  24. Q7b. Design a Turing Machine that enumerates all strings over {a, b} in lexicographic order. Explain the working of the machine.20257m

    Module 4: Turing Machines (TM)

    Design a Turing Machine that enumerates all strings over {a, b} in lexicographic order. Explain the working of the machine.

    View this question on its own page →
    Search GoogleAsk AI
  25. Q8a. Design a single-tape Turing Machine that multiplies two unary numbers, where the input is of the form 1^m 0 1^n and the output is 1^{m \times n}. Clearly define the input alphabet, tape alphabet, and halting condition. Simulate the working of the Turing Machine on the input string 1101.20257m

    Module 4: Turing Machines (TM)

    Design a single-tape Turing Machine that multiplies two unary numbers, where the input is of the form 1m01n1^m 0 1^n and the output is 1m×n1^{m \times n}. Clearly define the input alphabet, tape alphabet, and halting condition. Simulate the working of the Turing Machine on the input string 11011101.

    View this question on its own page →
    Search GoogleAsk AI
  26. Q8b. Given the regular expression r = (a+b)^* (i) Construct a context-free grammar that generates the language described by r. (ii) Explain why the grammar correctly represents the given regular expression.20257m

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

    Given the regular expression r=(a+b)∗r = (a+b)^*

    (i) Construct a context-free grammar that generates the language described by rr.
    (ii) Explain why the grammar correctly represents the given regular expression.

    View this question on its own page →
    Search GoogleAsk AI
  27. Q9a. Write a short note on Rice's Theorem with an application.20254.66m

    Module 5: Undecidability

    Write a short note on Rice's Theorem with an application.

    View this question on its own page →
    Search GoogleAsk AI
  28. Q9b. Write a short note on Deterministic vs Nondeterministic PDA.20254.66m

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

    Write a short note on Deterministic vs Nondeterministic PDA.

    View this question on its own page →
    Search GoogleAsk AI
  29. Q9c. Write a short note on Universal Turing Machine.20254.66m

    Module 5: Undecidability

    Write a short note on Universal Turing Machine.

    View this question on its own page →
    Search GoogleAsk AI
  30. Q9d. Write a short note on Greibach Normal Form (GNF).20254.66m

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

    Write a short note on Greibach Normal Form (GNF).

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