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
- Design PDA for \{wcw^T \mid w = \{a,b ^*\} — 10 marks · asked 1× (End Sem 2026)
- Discuss various types of grammars and the languages which are associated with them. — 10 marks · asked 1× (End Sem 2026)
- Identify the automata machines that accept different languages according to the Chomsky hierarchy. — 10 marks · asked 1× (End Sem 2026)
- 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)
- 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)
- Compare the different classes of languages in the Chomsky hierarchy and explain their corresponding computational machines. — 8 marks · asked 1× (Mid Sem 1 2026)
- 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)
- 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)
- 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)
- Differentiate between DFA and NFA. — 5 marks · asked 1× (End Sem 2026)
Unit 1 — Introduction
- Discuss various types of grammars and the languages which are associated with them. — 10 marks · asked 1× (End Sem 2026)
- Identify the automata machines that accept different languages according to the Chomsky hierarchy. — 10 marks · asked 1× (End Sem 2026)
- Compare the different classes of languages in the Chomsky hierarchy and explain their corresponding computational machines. — 8 marks · asked 1× (Mid Sem 1 2026)
- 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)
- Explain alphabet, string, and language with examples. Also write the closure properties of language. — 4 marks · asked 1× (Mid Sem 1 2026)
- What is meant by derivation? — 2 marks · asked 1× (Mid Sem 1 2026)
- What is a start symbol in a grammar? — 2 marks · asked 1× (Mid Sem 1 2026)
- What are alphabets in a formal language? — 2 marks · asked 1× (End Sem 2026)
- Discuss the abstract computational devices in Automata. — 2 marks · asked 1× (End Sem 2026)
- What is a formal language and how it is different from natural languages? — 2 marks · asked 1× (End Sem 2026)
- Explain how a grammar (G) is represented in formal language theory. — 2 marks · asked 1× (End Sem 2026)
- Discuss in detail the hierarchy representing various types of Grammar, Languages and Machines. — 10 marks · asked 1× (End Sem 2025)
- 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)
- Differentiate between type 1 and 2 grammar. — 2 marks · asked 1× (End Sem 2025)
- Give any 2 uses of Automata theory. — 2 marks · asked 1× (End Sem 2025)
- What is a formal language? — 2 marks · asked 1× (End Sem 2025)
- Give an example of production rule in automata. — 2 marks · asked 1× (End Sem 2025)
- Explain in brief about languages and grammars — 2 marks · asked 1× (Mid Sem 1 2025)
- Define the term "alphabet" in the context of formal languages. — 2 marks · asked 1× (Mid Sem 1 2025)
- Explain the Chomsky hierarchy of grammars with the help of writing rules for each type of grammars. — 5 marks · asked 1× (End Sem 2024)
- Define Grammar. — 2 marks · asked 1× (End Sem 2024)
- Discuss the different applications of Formal Language and Automata Theory — 10 marks · asked 1× (End Sem 2023)
- What is a formal language and how is it different from a natural language? — 2 marks · asked 1× (End Sem 2023)
- Define the term "alphabet" in the context of formal languages. — 2 marks · asked 1× (End Sem 2023)
- How do we represent Grammar? — 2 marks · asked 1× (End Sem 2023)
Unit 2 — Regular Languages and Finite Automata
- 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)
- Differentiate between DFA and NFA. — 5 marks · asked 1× (End Sem 2026)
- Write down the steps of convert this NFA into DFA. — 5 marks · asked 1× (End Sem 2026)
- What are closure properties? Explain any four. — 5 marks · asked 1× (End Sem 2026)
- 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)
- 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)
- Construct a DFA for the language. L = \{w \in \{0, 1\}^* \mid w \text{ contains } 101\} — 4 marks · asked 1× (Mid Sem 1 2026)
- with the help of diagram explain the function of DFA, why it is called as deterministic? — 4 marks · asked 1× (Mid Sem 1 2026)
- Difference between DFA and NFA. — 2 marks · asked 1× (Mid Sem 1 2026)
- Define a regular language. — 2 marks · asked 1× (Mid Sem 1 2026)
- Explain the difference between a DFA and a Non-deterministic Finite Automaton (NFA). — 2 marks · asked 1× (End Sem 2026)
- Discuss the transition function difference in case of DFA and NFA. — 2 marks · asked 1× (End Sem 2026)
- How regular expressions are used to represent languages? — 2 marks · asked 1× (End Sem 2026)
- Explain Arden's theorem. — 2 marks · asked 1× (End Sem 2026)
- Differentiate between Moore and mealy machine and steps for conversion to each other. — 10 marks · asked 1× (End Sem 2025)
- Convert this NFA to DFA: — 5 marks · asked 1× (End Sem 2025)
- Convert the given Mealy machine into Moore machine: — 5 marks · asked 1× (End Sem 2025)
- 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)
- What are closure properties? Explain any four — 5 marks · asked 1× (End Sem 2025)
- What is the significance of pumping lemma for checking regular languages? — 5 marks · asked 1× (End Sem 2025)
- Explain with example procedure to convert a Moore machine to a Mealy machine. — 4 marks · asked 1× (Mid Sem 2 2025)
- Discuss the procedure to convert NDFA to DFA with the help of suitable example. — 4 marks · asked 1× (Mid Sem 1 2025)
- 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)
- 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)
- State Kleene's theorem — 2 marks · asked 1× (End Sem 2025)
- Discuss the importance of Arden's theorem — 2 marks · asked 1× (End Sem 2025)
- Write closure properties of regular language. — 2 marks · asked 1× (Mid Sem 1 2025)
- What do you mean by Regular Expression — 2 marks · asked 1× (Mid Sem 1 2025)
- Write short note on Applications of Regular Expressions. — 5 marks · asked 1× (End Sem 2024)
- What is the meaning of acceptability of string by FA? — 2 marks · asked 1× (End Sem 2024)
- \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)
- 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)
- 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)
- Define NDFA. — 2 marks · asked 1× (End Sem 2023)
- The regular expression ab^*c will give ______? — 2 marks · asked 1× (End Sem 2023)
- Define NFA. — 2 marks · asked 1× (End Sem 2023)
Unit 3 — Context-Free Languages and Pushdown Automata
- Design PDA for \{wcw^T \mid w = \{a,b ^*\} — 10 marks · asked 1× (End Sem 2026)
- 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)
- 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)
- Name any two key components of a Pushdown Automaton (PDA). — 2 marks · asked 1× (End Sem 2026)
- What is a derivation tree? — 2 marks · asked 1× (End Sem 2026)
- Define the closure properties of Context-Free Languages (CFLs) with two examples — 2 marks · asked 1× (Mid Sem 2 2026)
- What is the difference between Regular and context free grammar? — 2 marks · asked 1× (End Sem 2026)
- Recall Chomsky's Normal Form. Give an example. — 2 marks · asked 1× (End Sem 2026)
- 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)
- 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)
- Compare PDA with FA. — 2 marks · asked 1× (End Sem 2025)
- What is a PDA? Discuss with example. — 2 marks · asked 1× (End Sem 2025)
- What is ambiguity in context free grammar? — 2 marks · asked 1× (End Sem 2025)
- What is left recursion? — 2 marks · asked 1× (End Sem 2025)
- What is ambiguity in CFG? — 2 marks · asked 1× (Mid Sem 2 2025)
- 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)
- 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)
- Construct the DPDA for "Accepting the language of balanced parentheses". — 5 marks · asked 1× (End Sem 2024)
- Write a short note on: FA vs PDA — 5 marks · asked 1× (End Sem 2024)
- Define Derivation Tree and yield of tree. — 2 marks · asked 1× (End Sem 2024)
- List closure properties of CFL. — 2 marks · asked 1× (End Sem 2024)
- 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
- 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)
- 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)
- 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)
- What are context sensitive Grammars. — 2 marks · asked 1× (Mid Sem 2 2026)
- Outline the restrictions on tape movement in a LBA. — 2 marks · asked 1× (End Sem 2026)
- Define LBA. — 2 marks · asked 1× (Mid Sem 2 2025)
- Write a short note on: Context Sensitive Languages. — 5 marks · asked 1× (End Sem 2024)
- 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)
- What is context sensitive grammar? — 2 marks · asked 1× (End Sem 2023)
- Define LBA. — 2 marks · asked 1× (End Sem 2023)
Unit 5 — Turing Machines
- 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)
- 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)
- 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)
- What is a Turing Machine (TM) and what makes it a universal model of computation? — 5 marks · asked 1× (End Sem 2026)
- Compare and contrast Finite Automata with Turing Machines. — 2 marks · asked 1× (End Sem 2026)
- 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)
- Design Turing Machine of \{WcW \mid W \in \{a, b\}^*\} — 4 marks · asked 1× (Mid Sem 2 2025)
- 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)
- Define Decidability. — 2 marks · asked 1× (End Sem 2024)
- 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
- Give examples of Hamiltonian paths and Hamiltonian circuits. — 5 marks · asked 1× (End Sem 2026)
- Identify the validity of the Church-Turing Thesis in modern computation models. — 5 marks · asked 1× (End Sem 2026)
- What are P, NP, NP-complete and NP-hard Problems? — 4 marks · asked 1× (Mid Sem 2 2026)
- List examples of NP Hard and NP Complete problems. — 2 marks · asked 1× (End Sem 2026)
- What is LHAT? — 2 marks · asked 1× (End Sem 2026)
- What is intractability? — 2 marks · asked 1× (End Sem 2026)
- State the Church-Turing Thesis and briefly explain its significance. — 2 marks · asked 1× (Mid Sem 2 2026)
- Define a Universal Turing Machine (UTM) and state its purpose. — 2 marks · asked 1× (Mid Sem 2 2026)
- Explain Cook-Levin theorem. — 2 marks · asked 1× (End Sem 2026)
- When is a problem said to be NP-hard? — 2 marks · asked 1× (End Sem 2026)
- Discuss church Turing thesis in detail along with various types of TM. — 10 marks · asked 1× (End Sem 2025)
- Cook Levin Theorem for satisfiability. — 8 marks · asked 1× (Mid Sem 2 2025)
- What is Church Turing thesis states? — 2 marks · asked 1× (Mid Sem 2 2025)
- Define NP-complete problem. — 2 marks · asked 1× (Mid Sem 2 2025)
- What do you understand by Tractable and Intractable problems with reference to Turing Machines. — 5 marks · asked 1× (End Sem 2024)
- Define Universal Turing Machine. — 2 marks · asked 1× (End Sem 2024)
- What is NP hard problem? — 2 marks · asked 1× (End Sem 2024)
- State Rice' Theorem. — 2 marks · asked 1× (End Sem 2024)
- What is halting problem? — 2 marks · asked 1× (End Sem 2024)
- Explain the concept of Hamiltonian Cycle in Graphs. — 5 marks · asked 1× (End Sem 2023)
- Write a short note on: Difference between Decidability and undecidability. — 5 marks · asked 1× (End Sem 2023)
- Write a short note on: Cook Levin Theorem for satisfiability. — 5 marks · asked 1× (End Sem 2023)
- What is NP Complete problem? — 2 marks · asked 1× (End Sem 2023)
- Define Intractability. — 2 marks · asked 1× (End Sem 2023)