2024 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

26 questions

1. Q1a. If an infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is: (i) Compiler (ii) Interpreter (iii) Loader and Linkers (iv) None of the mentioned20242m

   Module 4: Turing Machines (TM)

   If an infinite language is passed to Machine $M$, the subsidiary which gives a finite solution to the infinite input tape is:

   (i) Compiler
   (ii) Interpreter
   (iii) Loader and Linkers
   (iv) None of the mentioned

   View this question on its own page →

   CopySearch GoogleAsk AI
2. Q1b. Which of the following is a regular language? (i) Strings whose length is a sequence of prime numbers (ii) Palindrome strings (iii) Strings containing substring ww^r (iv) Strings with even number of 0’s20242m

   Module 1: Introduction & Regular Languages

   Which of the following is a regular language?

   (i) Strings whose length is a sequence of prime numbers
   (ii) Palindrome strings
   (iii) Strings containing substring $ww^r$
   (iv) Strings with even number of $0$’s

   View this question on its own page →

   CopySearch GoogleAsk AI
3. Q1c. NFA has 'non-deterministic' in its name because: (i) The result is undetermined (ii) The choice of path is nondeterministic (iii) The next state is nondeterministic (iv) All of the mentioned20242m

   Module 1: Introduction & Regular Languages

   NFA has 'non-deterministic' in its name because:

   (i) The result is undetermined
   (ii) The choice of path is nondeterministic
   (iii) The next state is nondeterministic
   (iv) All of the mentioned

   View this question on its own page →

   CopySearch GoogleAsk AI
4. Q1d. Which of the following is NOT a component of a finite automaton? (i) States (ii) Input alphabet (iii) Transition function (iv) Output tape20242m

   Module 1: Introduction & Regular Languages

   Which of the following is NOT a component of a finite automaton?

   (i) States
   (ii) Input alphabet
   (iii) Transition function
   (iv) Output tape

   View this question on its own page →

   CopySearch GoogleAsk AI
5. Q1e. A DFA can have: (i) Multiple start states (ii) Multiple accepting states (iii) Transitions on \varepsilon (iv) None of the above20242m

   Module 1: Introduction & Regular Languages

   A DFA can have:

   (i) Multiple start states
   (ii) Multiple accepting states
   (iii) Transitions on $\varepsilon$
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1f. Which of the following is a type of grammar in the Chomsky hierarchy? (i) Regular (ii) Context-Free (iii) Context-Sensitive (iv) All of the above20242m

   Module 1: Introduction & Regular Languages

   Which of the following is a type of grammar in the Chomsky hierarchy?

   (i) Regular
   (ii) Context-Free
   (iii) Context-Sensitive
   (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1g. A Turing Machine has: (i) A finite tape (ii) An infinite tape (iii) A stack (iv) A queue20242m

   Module 4: Turing Machines (TM)

   A Turing Machine has:

   (i) A finite tape
   (ii) An infinite tape
   (iii) A stack
   (iv) A queue

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q1h. Which of the following problems is undecidable? (i) DFA acceptance (ii) NFA acceptance (iii) The Halting Problem (iv) Regular expression matching20242m

   Module 5: Undecidability

   Which of the following problems is undecidable?

   (i) DFA acceptance
   (ii) NFA acceptance
   (iii) The Halting Problem
   (iv) Regular expression matching

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q1i. Which of these represents a regular language? (i) \{ a^n b^n \mid n \ge 0 \} (ii) Strings with equal number of a’s and b’s (iii) \{ a^n \mid n \text{ is prime} \} (iv) \{ w \mid w \text{ starts with 'a' and ends with 'b'} \}20242m

   Module 1: Introduction & Regular Languages

   Which of these represents a regular language?

   (i) $\{ a^n b^n \mid n \ge 0 \}$
   (ii) Strings with equal number of $a$’s and $b$’s
   (iii) $\{ a^n \mid n \text{ is prime} \}$
   (iv) $\{ w \mid w \text{ starts with 'a' and ends with 'b'} \}$

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q1j. Which of the following is a PDA? (i) Finite automaton with a stack (ii) Turing machine with a stack (iii) Finite automaton with a queue (iv) Turing machine with a queue20242m

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

    Which of the following is a PDA?

    (i) Finite automaton with a stack
    (ii) Turing machine with a stack
    (iii) Finite automaton with a queue
    (iv) Turing machine with a queue

    View this question on its own page →

    CopySearch GoogleAsk AI
12. Q2a. What is Automata? Explain classification of Automata.20247m

    Module 1: Introduction & Regular Languages

    What is Automata? Explain classification of Automata.

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q2b. Tabulate the Chomsky hierarchy of grammars with an example of each.20247m

    Module 1: Introduction & Regular Languages

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

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q3a. Construct DFA for all strings over \{0,1\} interpreted as binary numbers divisible by 4.20247m

    Module 1: Introduction & Regular Languages

    Construct DFA for all strings over $\{0,1\}$ interpreted as binary numbers divisible by $4$.

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q3b. Construct DFA that accepts strings over \Sigma = \{a,b\} which start with aba.20247m

    Module 1: Introduction & Regular Languages

    Construct DFA that accepts strings over $\Sigma = \{a,b\}$ which start with $aba$.

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Prove that L = \{ a^i b^i \mid i \ge 0 \} is not regular using the pumping lemma.20247m

    Module 1: Introduction & Regular Languages

    Prove that $L = \{ a^i b^i \mid i \ge 0 \}$ is not regular using the pumping lemma.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Convert the following NFA to DFA. 20247m

    Module 1: Introduction & Regular Languages

    Convert the following NFA to DFA.

    

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. Design a Turing Machine that increments a binary number by 1.20247m

    Module 4: Turing Machines (TM)

    Design a Turing Machine that increments a binary number by $1$.

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q5b. Write the difference between Pushdown Automata and Finite Automata.20247m

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

    Write the difference between Pushdown Automata and Finite Automata.

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6a. Construct a PDA for the language: L = \{ 0^m 1^n 0^k \mid k \ge 1, m \ge 1, m > n + 2 \}20247m

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

    Construct a PDA for the language:

    $$L = \{ 0^m 1^n 0^k \mid k \ge 1, m \ge 1, m > n + 2 \}$$

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q6b. Explain the various types of Turing Machines.20247m

    Module 4: Turing Machines (TM)

    Explain the various types of Turing Machines.

    View this question on its own page →

    CopySearch GoogleAsk AI
23. Q7a. Construct a PDA for the grammar: S \to 0BB B \to 0S \mid 1S \mid 0 Test whether 0104 is accepted by this PDA.20247m

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

    Construct a PDA for the grammar:

    $S \to 0BB$
    $B \to 0S \mid 1S \mid 0$

    Test whether $0104$ is accepted by this PDA.

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q7b. Check whether the grammar is ambiguous: S \to a \mid abSb \mid aAb A \to bS \mid aAAb20247m

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

    Check whether the grammar is ambiguous:

    $S \to a \mid abSb \mid aAb$
    $A \to bS \mid aAAb$

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8a. Define NFA with \varepsilon-transitions with an example.20247m

    Module 1: Introduction & Regular Languages

    Define NFA with $\varepsilon$-transitions with an example.

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8b. Prove the pumping lemma for regular languages.20247m

    Module 1: Introduction & Regular Languages

    Prove the pumping lemma for regular languages.

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write short notes on: 1. Minimization of DFA 2. Type 2 grammar (Context-Free Grammar)20247m

    Module 1: Introduction & Regular Languages

    Write short notes on:

    1. Minimization of DFA
    2. Type 2 grammar (Context-Free Grammar)

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write short notes on: 1. Post Correspondence Problem (PCP) 2. NP-hard problem20247m

    Module 5: Undecidability

    Write short notes on:

    1. Post Correspondence Problem (PCP)
    2. NP-hard problem

    View this question on its own page →

    CopySearch GoogleAsk AI