2025 question paper

Formal Language & Automata Theory

28 questions

1. Q1a. Which of the following is the smallest unit in the definition of a language? (i) Grammar (ii) Alphabet (iii) String (iv) Production20252m

   Module 1: Introduction, Regular languages and finite automata

   Which of the following is the smallest unit in the definition of a language?

   (i) Grammar
   (ii) Alphabet
   (iii) String
   (iv) Production

   View this question on its own page →

   CopySearch GoogleAsk AI
2. Q1b. A language is a (i) Set of alphabets (ii) Set of strings over an alphabet (iii) Set of grammars (iv) Set of automata20252m

   Module 1: Introduction, Regular languages and finite automata

   A language is a

   (i) Set of alphabets
   (ii) Set of strings over an alphabet
   (iii) Set of grammars
   (iv) Set of automata

   View this question on its own page →

   CopySearch GoogleAsk AI
3. Q1c. Which grammar type is the most powerful? (i) Type-0 (ii) Type-1 (iii) Type-2 (iv) Type-320252m

   Module 1: Introduction, Regular languages and finite automata

   Which grammar type is the most powerful?

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

   View this question on its own page →

   CopySearch GoogleAsk AI
4. Q1d. Epsilon (\varepsilon) transitions are allowed in (i) DFA only (ii) Both DFA and NFA (iii) NFA only (iv) None20252m

   Module 1: Introduction, Regular languages and finite automata

   Epsilon ($\varepsilon$) transitions are allowed in

   (i) DFA only
   (ii) Both DFA and NFA
   (iii) NFA only
   (iv) None

   View this question on its own page →

   CopySearch GoogleAsk AI
5. Q1e. Context-Free Grammars are equivalent to (i) Finite Automata (ii) Turing Machines (iii) Linear Bounded Automata (iv) Pushdown Automata20252m

   Module 2: Context-free languages and pushdown automata

   Context-Free Grammars are equivalent to

   (i) Finite Automata
   (ii) Turing Machines
   (iii) Linear Bounded Automata
   (iv) Pushdown Automata

   View this question on its own page →

   CopySearch GoogleAsk AI
6. Q1f. Pumping Lemma for CFLs is used to prove a language is (i) Not Context-Free (ii) Regular (iii) Decidable (iv) Turing recognizable20252m

   Module 2: Context-free languages and pushdown automata

   Pumping Lemma for CFLs is used to prove a language is

   (i) Not Context-Free
   (ii) Regular
   (iii) Decidable
   (iv) Turing recognizable

   View this question on its own page →

   CopySearch GoogleAsk AI
7. Q1g. Which of the following requires context sensitivity? (i) a^n b^n (ii) a^n b^n c^n (iii) (a+b)^* (iv) a^*20252m

   Module 3: Context sensitive langauges

   Which of the following requires context sensitivity?

   (i) $a^n b^n$
   (ii) $a^n b^n c^n$
   (iii) $(a+b)^*$
   (iv) $a^*$

   View this question on its own page →

   CopySearch GoogleAsk AI
8. Q1h. Recursively Enumerable languages are also called (i) Turing Recognizable (ii) Turing Decidable (iii) Regular (iv) Context-Free20252m

   Module 4: Turing machines

   Recursively Enumerable languages are also called

   (i) Turing Recognizable
   (ii) Turing Decidable
   (iii) Regular
   (iv) Context-Free

   View this question on its own page →

   CopySearch GoogleAsk AI
9. Q1i. The Halting Problem is (i) Decidable (ii) Undecidable (iii) Context-Free (iv) Regular20252m

   Module 5: Undecidability

   The Halting Problem is

   (i) Decidable
   (ii) Undecidable
   (iii) Context-Free
   (iv) Regular

   View this question on its own page →

   CopySearch GoogleAsk AI
10. Q1j. Which of the following is used to prove many undecidability results? (i) Pumping Lemma (ii) Rice's Theorem (iii) Chomsky Normal Form (iv) Subset Construction20252m

    Module 5: Undecidability

    Which of the following is used to prove many undecidability results?

    (i) Pumping Lemma
    (ii) Rice's Theorem
    (iii) Chomsky Normal Form
    (iv) Subset Construction

    View this question on its own page →

    CopySearch GoogleAsk AI
12. Q2a. Define the terms: Alphabet, Language, Grammar, and Derivation. Explain the relationship between them with suitable examples.20257m

    Module 1: Introduction, Regular languages and finite automata

    Define the terms: Alphabet, Language, Grammar, and Derivation. Explain the relationship between them with suitable examples.

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q2b. Explain Chomsky Hierarchy of languages with examples of each type and their corresponding automata.20257m

    Module 1: Introduction, Regular languages and finite automata

    Explain Chomsky Hierarchy of languages with examples of each type and their corresponding automata.

    View this question on its own page →

    CopySearch GoogleAsk AI
14. Q3a. Explain the concept of a Finite Automaton. List and describe its main components. Also, differentiate between Deterministic Finite Automaton and Non-deterministic Finite Automaton with suitable examples.20257m

    Module 1: Introduction, Regular languages and finite automata

    Explain the concept of a Finite Automaton. List and describe its main components. Also, differentiate between Deterministic Finite Automaton and Non-deterministic Finite Automaton with suitable examples.

    View this question on its own page →

    CopySearch GoogleAsk AI
15. Q3b. Construct a DFA that accepts all strings over \{0,1\} containing an even number of 0s and an odd number of 1s. Also, write its formal 5-tuple definition.20257m

    Module 1: Introduction, Regular languages and finite automata

    Construct a DFA that accepts all strings over $\{0,1\}$ containing an even number of 0s and an odd number of 1s. Also, write its formal 5-tuple definition.

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Convert the regular expression (a + b)abb(a + b) into an equivalent DFA. Show all steps.20257m

    Module 1: Introduction, Regular languages and finite automata

    Convert the regular expression $(a + b)abb(a + b)$ into an equivalent DFA. Show all steps.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Using Pumping Lemma, prove that the language L = \{0^{n}1^{n} \mid n \ge 0\} is not regular.20257m

    Module 1: Introduction, Regular languages and finite automata

    Using Pumping Lemma, prove that the language $L = \{0^{n}1^{n} \mid n \ge 0\}$ is not regular.

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. Explain how ambiguity arises in the grammar E \rightarrow E + E \mid E \times E \mid id \mid (E). Remove the ambiguity by rewriting the grammar.20257m

    Module 2: Context-free languages and pushdown automata

    Explain how ambiguity arises in the grammar $E \rightarrow E + E \mid E \times E \mid id \mid (E)$. Remove the ambiguity by rewriting the grammar.

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q5b. Using Pumping Lemma for CFLs, prove that L = \{a^{n}b^{n}c^{n} \mid n \ge 0\} is not context-free.20257m

    Module 2: Context-free languages and pushdown automata

    Using Pumping Lemma for CFLs, prove that $L = \{a^{n}b^{n}c^{n} \mid n \ge 0\}$ is not context-free.

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6a. Explain Linear Bounded Automata and its relationship with Context-Sensitive Languages.20257m

    Module 3: Context sensitive langauges

    Explain Linear Bounded Automata and its relationship with Context-Sensitive Languages.

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q6b. Explain the basic model of a Turing Machine with its formal 7-tuple definition.20257m

    Module 4: Turing machines

    Explain the basic model of a Turing Machine with its formal 7-tuple definition.

    View this question on its own page →

    CopySearch GoogleAsk AI
23. Q7a. Design a Turing Machine that accepts the language L = \{a^{n}b^{n} \mid n \ge 0\}. Show the transition diagram/table and trace for input aabb.20257m

    Module 4: Turing machines

    Design a Turing Machine that accepts the language $L = \{a^{n}b^{n} \mid n \ge 0\}$. Show the transition diagram/table and trace for input aabb.

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q7b. State and explain the Church-Turing Thesis.20257m

    Module 4: Turing machines

    State and explain the Church-Turing Thesis.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8a. Explain the concept of Universal Turing Machine. How does it help in proving undecidability?20257m

    Module 5: Undecidability

    Explain the concept of Universal Turing Machine. How does it help in proving undecidability?

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8b. Discuss the power and limitations of Turing Machines. Compare Turing Machines with Pushdown Automata.20257m

    Module 4: Turing machines

    Discuss the power and limitations of Turing Machines. Compare Turing Machines with Pushdown Automata.

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write a short note on: Pushdown Automata20257m

    Module 2: Context-free languages and pushdown automata

    Write a short note on:

    Pushdown Automata

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write a short note on: Rice's theorem20257m

    Module 5: Undecidability

    Write a short note on:

    Rice's theorem

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9c. Write a short note on: Minimization of finite automata20257m

    Module 1: Introduction, Regular languages and finite automata

    Write a short note on:

    Minimization of finite automata

    View this question on its own page →

    CopySearch GoogleAsk AI
30. Q9d. Write a short note on: Closure properties of CFLs20257m

    Module 2: Context-free languages and pushdown automata

    Write a short note on:

    Closure properties of CFLs

    View this question on its own page →

    CopySearch GoogleAsk AI