BTCS-502-18 Formal Language and Automata theroy — important questions

127 questions that keep coming back in Formal Language and Automata theroy (BTCS-502-18) PTU exams, picked from 8 past papers. Questions asked more often, and more recently, are listed first.

Most asked

  1. Design PDA for \{wcw^T \mid w = \{a,b ^*\} — 10 marks · asked 1× (End Sem 2026)
  2. Discuss various types of grammars and the languages which are associated with them. — 10 marks · asked 1× (End Sem 2026)
  3. Identify the automata machines that accept different languages according to the Chomsky hierarchy. — 10 marks · asked 1× (End Sem 2026)
  4. Build a LBA for language L having equal number of a's followed by equal number of b's followed by equal number of c's. — 10 marks · asked 1× (End Sem 2026)
  5. Evaluate the operations of a Turing Machine in terms of reading and writing symbols on the tape, state transitions and halting conditions with suitable example. — 10 marks · asked 1× (End Sem 2026)
  6. Compare the different classes of languages in the Chomsky hierarchy and explain their corresponding computational machines. — 8 marks · asked 1× (Mid Sem 1 2026)
  7. Construct an NFA for all string accepted ending with aab and convert it into an equivalent DFA. — 8 marks · asked 1× (Mid Sem 1 2026)
  8. Design a Turing Machine M to recognize the language L=\{a^n b^n c^n \mid n\ge 1\}. — 8 marks · asked 1× (Mid Sem 2 2026)
  9. Explain the different variants of a Turing Machine. Explain how they differ from the standard Turing Machine. — 8 marks · asked 1× (Mid Sem 2 2026)
  10. Differentiate between DFA and NFA. — 5 marks · asked 1× (End Sem 2026)

Unit 1 — Introduction

  1. Discuss various types of grammars and the languages which are associated with them. — 10 marks · asked 1× (End Sem 2026)
  2. Identify the automata machines that accept different languages according to the Chomsky hierarchy. — 10 marks · asked 1× (End Sem 2026)
  3. Compare the different classes of languages in the Chomsky hierarchy and explain their corresponding computational machines. — 8 marks · asked 1× (Mid Sem 1 2026)
  4. Identify the language L = \{a^n b^n \mid n \geq 0, over alphabet \Sigma = \{a, b, c\}\} as per Chomsky hierarchy. — 5 marks · asked 1× (End Sem 2026)
  5. Explain alphabet, string, and language with examples. Also write the closure properties of language. — 4 marks · asked 1× (Mid Sem 1 2026)
  6. What is meant by derivation? — 2 marks · asked 1× (Mid Sem 1 2026)
  7. What is a start symbol in a grammar? — 2 marks · asked 1× (Mid Sem 1 2026)
  8. What are alphabets in a formal language? — 2 marks · asked 1× (End Sem 2026)
  9. Discuss the abstract computational devices in Automata. — 2 marks · asked 1× (End Sem 2026)
  10. What is a formal language and how it is different from natural languages? — 2 marks · asked 1× (End Sem 2026)
  11. Explain how a grammar (G) is represented in formal language theory. — 2 marks · asked 1× (End Sem 2026)
  12. Discuss in detail the hierarchy representing various types of Grammar, Languages and Machines. — 10 marks · asked 1× (End Sem 2025)
  13. Explain the Chomsky hierarchy of grammars. Also explain the production rules of all grammars with the help of example. — 8 marks · asked 1× (Mid Sem 1 2025)
  14. Differentiate between type 1 and 2 grammar. — 2 marks · asked 1× (End Sem 2025)
  15. Give any 2 uses of Automata theory. — 2 marks · asked 1× (End Sem 2025)
  16. What is a formal language? — 2 marks · asked 1× (End Sem 2025)
  17. Give an example of production rule in automata. — 2 marks · asked 1× (End Sem 2025)
  18. Explain in brief about languages and grammars — 2 marks · asked 1× (Mid Sem 1 2025)
  19. Define the term "alphabet" in the context of formal languages. — 2 marks · asked 1× (Mid Sem 1 2025)
  20. Explain the Chomsky hierarchy of grammars with the help of writing rules for each type of grammars. — 5 marks · asked 1× (End Sem 2024)
  21. Define Grammar. — 2 marks · asked 1× (End Sem 2024)
  22. Discuss the different applications of Formal Language and Automata Theory — 10 marks · asked 1× (End Sem 2023)
  23. What is a formal language and how is it different from a natural language? — 2 marks · asked 1× (End Sem 2023)
  24. Define the term "alphabet" in the context of formal languages. — 2 marks · asked 1× (End Sem 2023)
  25. How do we represent Grammar? — 2 marks · asked 1× (End Sem 2023)

Unit 2 — Regular Languages and Finite Automata

  1. Construct an NFA for all string accepted ending with aab and convert it into an equivalent DFA. — 8 marks · asked 1× (Mid Sem 1 2026)
  2. Differentiate between DFA and NFA. — 5 marks · asked 1× (End Sem 2026)
  3. Write down the steps of convert this NFA into DFA. — 5 marks · asked 1× (End Sem 2026)
  4. What are closure properties? Explain any four. — 5 marks · asked 1× (End Sem 2026)
  5. Check whether the given FA accepts the language set L=\{0, 10, 110, 1100\}. Also discuss the importance of Language acceptance. — 5 marks · asked 1× (End Sem 2026)
  6. Examine the pumping lemma for regular grammars and infer how it can be applied to prove that a given grammar is not regular. — 5 marks · asked 1× (End Sem 2026)
  7. Construct a DFA for the language. L = \{w \in \{0, 1\}^* \mid w \text{ contains } 101\} — 4 marks · asked 1× (Mid Sem 1 2026)
  8. with the help of diagram explain the function of DFA, why it is called as deterministic? — 4 marks · asked 1× (Mid Sem 1 2026)
  9. Difference between DFA and NFA. — 2 marks · asked 1× (Mid Sem 1 2026)
  10. Define a regular language. — 2 marks · asked 1× (Mid Sem 1 2026)
  11. Explain the difference between a DFA and a Non-deterministic Finite Automaton (NFA). — 2 marks · asked 1× (End Sem 2026)
  12. Discuss the transition function difference in case of DFA and NFA. — 2 marks · asked 1× (End Sem 2026)
  13. How regular expressions are used to represent languages? — 2 marks · asked 1× (End Sem 2026)
  14. Explain Arden's theorem. — 2 marks · asked 1× (End Sem 2026)
  15. Differentiate between Moore and mealy machine and steps for conversion to each other. — 10 marks · asked 1× (End Sem 2025)
  16. Convert this NFA to DFA: — 5 marks · asked 1× (End Sem 2025)
  17. Convert the given Mealy machine into Moore machine: — 5 marks · asked 1× (End Sem 2025)
  18. Check whether the given FA accepts the language set L = \{0, 10, 110, 1100\}. Also, discuss the importance of language acceptance. — 5 marks · asked 1× (End Sem 2025)
  19. What are closure properties? Explain any four — 5 marks · asked 1× (End Sem 2025)
  20. What is the significance of pumping lemma for checking regular languages? — 5 marks · asked 1× (End Sem 2025)
  21. Explain with example procedure to convert a Moore machine to a Mealy machine. — 4 marks · asked 1× (Mid Sem 2 2025)
  22. Discuss the procedure to convert NDFA to DFA with the help of suitable example. — 4 marks · asked 1× (Mid Sem 1 2025)
  23. Discuss the concept of Pumping Lemma for regular grammars. How Pumping Lemma is used to prove weather a given grammar is not a regular grammar? — 4 marks · asked 1× (Mid Sem 1 2025)
  24. Construct DFA for the language: L = \{w \in \{a, b\}^* \mid w \text{ ends with either } aa \text{ or } bb\} — 4 marks · asked 1× (Mid Sem 1 2025)
  25. State Kleene's theorem — 2 marks · asked 1× (End Sem 2025)
  26. Discuss the importance of Arden's theorem — 2 marks · asked 1× (End Sem 2025)
  27. Write closure properties of regular language. — 2 marks · asked 1× (Mid Sem 1 2025)
  28. What do you mean by Regular Expression — 2 marks · asked 1× (Mid Sem 1 2025)
  29. Write short note on Applications of Regular Expressions. — 5 marks · asked 1× (End Sem 2024)
  30. What is the meaning of acceptability of string by FA? — 2 marks · asked 1× (End Sem 2024)
  31. \Sigma=\{0,1\}, write RE for the alphabet whose 9th symbol from the L.H.S is 1. — 2 marks · asked 1× (End Sem 2024)
  32. Explain the three key components of the Pumping Lemma: the pumping length, the string decomposition and the pumping condition. How does the Pumping Lemma help in proving that a language is not regular? — 10 marks · asked 1× (End Sem 2023)
  33. Describe the acceptance criteria for both NFAs and DFAs. How does each type of automaton determine whether a given input string is accepted or rejected? — 5 marks · asked 1× (End Sem 2023)
  34. Define NDFA. — 2 marks · asked 1× (End Sem 2023)
  35. The regular expression ab^*c will give ______? — 2 marks · asked 1× (End Sem 2023)
  36. Define NFA. — 2 marks · asked 1× (End Sem 2023)

Unit 3 — Context-Free Languages and Pushdown Automata

  1. Design PDA for \{wcw^T \mid w = \{a,b ^*\} — 10 marks · asked 1× (End Sem 2026)
  2. Evaluate the following CFG and simplify it into Chomsky Normal Form (CNF): S \rightarrow \ast S, S \rightarrow (S \ast S), S \rightarrow 1, S \rightarrow 2 — 5 marks · asked 1× (End Sem 2026)
  3. Construct a Pushdown Automaton (PDA) equivalent to the language L=\{wcw^R \mid w\in\{a,b\}^*\} — 4 marks · asked 1× (Mid Sem 2 2026)
  4. Name any two key components of a Pushdown Automaton (PDA). — 2 marks · asked 1× (End Sem 2026)
  5. What is a derivation tree? — 2 marks · asked 1× (End Sem 2026)
  6. Define the closure properties of Context-Free Languages (CFLs) with two examples — 2 marks · asked 1× (Mid Sem 2 2026)
  7. What is the difference between Regular and context free grammar? — 2 marks · asked 1× (End Sem 2026)
  8. Recall Chomsky's Normal Form. Give an example. — 2 marks · asked 1× (End Sem 2026)
  9. Demonstrate that the given grammar is ambiguous. S \rightarrow \text{a} \mid \text{Sa} \mid \text{bSS} \mid \text{SSS} \mid \text{bSb} — 2 marks · asked 1× (End Sem 2026)
  10. What is Pushdown Automata? Construct a PDA that accepts: L = \{a^n b^n \mid n \ge 0\} — 4 marks · asked 1× (Mid Sem 2 2025)
  11. Compare PDA with FA. — 2 marks · asked 1× (End Sem 2025)
  12. What is a PDA? Discuss with example. — 2 marks · asked 1× (End Sem 2025)
  13. What is ambiguity in context free grammar? — 2 marks · asked 1× (End Sem 2025)
  14. What is left recursion? — 2 marks · asked 1× (End Sem 2025)
  15. What is ambiguity in CFG? — 2 marks · asked 1× (Mid Sem 2 2025)
  16. What is a Context Free Grammar? Prove that if L1 and L2 are two context free languages, their union L1 \cup L2 will also be context free. — 10 marks · asked 1× (End Sem 2024)
  17. What are non-reachable symbols? Eliminate non-reachable symbols from S \to aS \mid A, A \to a, B \to aa. — 5 marks · asked 1× (End Sem 2024)
  18. Construct the DPDA for "Accepting the language of balanced parentheses". — 5 marks · asked 1× (End Sem 2024)
  19. Write a short note on: FA vs PDA — 5 marks · asked 1× (End Sem 2024)
  20. Define Derivation Tree and yield of tree. — 2 marks · asked 1× (End Sem 2024)
  21. List closure properties of CFL. — 2 marks · asked 1× (End Sem 2024)
  22. What is PDA? How does a PDA handle the recognition of context-free languages and what role does its stack play in this process? — 5 marks · asked 1× (End Sem 2023)

Unit 4 — Context-Sensitive Languages

  1. Build a LBA for language L having equal number of a's followed by equal number of b's followed by equal number of c's. — 10 marks · asked 1× (End Sem 2026)
  2. Construct a CSG for the language L = \{a^n b^n c^n \mid n \geq 1\}. Apply the rules of CSGs to derive the string "aabbcc" for the language. — 5 marks · asked 1× (End Sem 2026)
  3. What is a Linear Bounded Automaton (LBA)? Explain its working and its relationship with context-sensitive languages. — 4 marks · asked 1× (Mid Sem 2 2026)
  4. What are context sensitive Grammars. — 2 marks · asked 1× (Mid Sem 2 2026)
  5. Outline the restrictions on tape movement in a LBA. — 2 marks · asked 1× (End Sem 2026)
  6. Define LBA. — 2 marks · asked 1× (Mid Sem 2 2025)
  7. Write a short note on: Context Sensitive Languages. — 5 marks · asked 1× (End Sem 2024)
  8. Explain the concept of a Linear Bounded Automaton (LBA) and how it relates to the recognition of context-sensitive languages? — 5 marks · asked 1× (End Sem 2023)
  9. What is context sensitive grammar? — 2 marks · asked 1× (End Sem 2023)
  10. Define LBA. — 2 marks · asked 1× (End Sem 2023)

Unit 5 — Turing Machines

  1. Evaluate the operations of a Turing Machine in terms of reading and writing symbols on the tape, state transitions and halting conditions with suitable example. — 10 marks · asked 1× (End Sem 2026)
  2. Design a Turing Machine M to recognize the language L=\{a^n b^n c^n \mid n\ge 1\}. — 8 marks · asked 1× (Mid Sem 2 2026)
  3. Explain the different variants of a Turing Machine. Explain how they differ from the standard Turing Machine. — 8 marks · asked 1× (Mid Sem 2 2026)
  4. What is a Turing Machine (TM) and what makes it a universal model of computation? — 5 marks · asked 1× (End Sem 2026)
  5. Compare and contrast Finite Automata with Turing Machines. — 2 marks · asked 1× (End Sem 2026)
  6. Describe the operation of a Turing Machine in terms of reading and writing symbols on the tape, state transitions and halting conditions. — 4 marks · asked 1× (Mid Sem 2 2025)
  7. Design Turing Machine of \{WcW \mid W \in \{a, b\}^*\} — 4 marks · asked 1× (Mid Sem 2 2025)
  8. Explain the concept of Turing Machine. Construct a TM for L = \{0^n 1^n \mid n \ge 1\}. — 10 marks · asked 1× (End Sem 2024)
  9. Define Decidability. — 2 marks · asked 1× (End Sem 2024)
  10. Describe the operation of a Turing Machine in terms of reading and writing symbols on the tape, state transitions and halting conditions. — 5 marks · asked 1× (End Sem 2023)

Unit 6 — Undecidability and Intractability

  1. Give examples of Hamiltonian paths and Hamiltonian circuits. — 5 marks · asked 1× (End Sem 2026)
  2. Identify the validity of the Church-Turing Thesis in modern computation models. — 5 marks · asked 1× (End Sem 2026)
  3. What are P, NP, NP-complete and NP-hard Problems? — 4 marks · asked 1× (Mid Sem 2 2026)
  4. List examples of NP Hard and NP Complete problems. — 2 marks · asked 1× (End Sem 2026)
  5. What is LHAT? — 2 marks · asked 1× (End Sem 2026)
  6. What is intractability? — 2 marks · asked 1× (End Sem 2026)
  7. State the Church-Turing Thesis and briefly explain its significance. — 2 marks · asked 1× (Mid Sem 2 2026)
  8. Define a Universal Turing Machine (UTM) and state its purpose. — 2 marks · asked 1× (Mid Sem 2 2026)
  9. Explain Cook-Levin theorem. — 2 marks · asked 1× (End Sem 2026)
  10. When is a problem said to be NP-hard? — 2 marks · asked 1× (End Sem 2026)
  11. Discuss church Turing thesis in detail along with various types of TM. — 10 marks · asked 1× (End Sem 2025)
  12. Cook Levin Theorem for satisfiability. — 8 marks · asked 1× (Mid Sem 2 2025)
  13. What is Church Turing thesis states? — 2 marks · asked 1× (Mid Sem 2 2025)
  14. Define NP-complete problem. — 2 marks · asked 1× (Mid Sem 2 2025)
  15. What do you understand by Tractable and Intractable problems with reference to Turing Machines. — 5 marks · asked 1× (End Sem 2024)
  16. Define Universal Turing Machine. — 2 marks · asked 1× (End Sem 2024)
  17. What is NP hard problem? — 2 marks · asked 1× (End Sem 2024)
  18. State Rice' Theorem. — 2 marks · asked 1× (End Sem 2024)
  19. What is halting problem? — 2 marks · asked 1× (End Sem 2024)
  20. Explain the concept of Hamiltonian Cycle in Graphs. — 5 marks · asked 1× (End Sem 2023)
  21. Write a short note on: Difference between Decidability and undecidability. — 5 marks · asked 1× (End Sem 2023)
  22. Write a short note on: Cook Levin Theorem for satisfiability. — 5 marks · asked 1× (End Sem 2023)
  23. What is NP Complete problem? — 2 marks · asked 1× (End Sem 2023)
  24. Define Intractability. — 2 marks · asked 1× (End Sem 2023)

Related