Formal Language and Automata theroy — End Sem 2026
Formal Language and Automata theroy (BTCS-502-18) End Sem 2026 question paper from I.K. Gujral Punjab Technical University. Read it online or download the PDF; an answer key is included.
Questions in this paper
- What are alphabets in a formal language? — 2 marks
- Name any two key components of a Pushdown Automaton (PDA). — 2 marks
- Explain the difference between a DFA and a Non-deterministic Finite Automaton (NFA). — 2 marks
- Discuss the abstract computational devices in Automata. — 2 marks
- List examples of NP Hard and NP Complete problems. — 2 marks
- What is a derivation tree? — 2 marks
- Discuss the transition function difference in case of DFA and NFA. — 2 marks
- How regular expressions are used to represent languages? — 2 marks
- What is LHAT? — 2 marks
- What is intractability? — 2 marks
- Differentiate between DFA and NFA. — 5 marks
- Write down the steps of convert this NFA into DFA. — 5 marks
- What is a Turing Machine (TM) and what makes it a universal model of computation? — 5 marks
- What are closure properties? Explain any four. — 5 marks
- Give examples of Hamiltonian paths and Hamiltonian circuits. — 5 marks
- Design PDA for \{wcw^T \mid w = \{a,b ^*\} — 10 marks
- Discuss various types of grammars and the languages which are associated with them. — 10 marks
- Check whether the given FA accepts the language set L=\{0, 10, 110, 1100\}. Also discuss the importance of Language acceptance. — 5 marks
- What is a formal language and how it is different from natural languages? — 2 marks
- Explain how a grammar (G) is represented in formal language theory. — 2 marks
- What is the difference between Regular and context free grammar? — 2 marks
- Explain Arden's theorem. — 2 marks
- Recall Chomsky's Normal Form. Give an example. — 2 marks
- 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
- Outline the restrictions on tape movement in a LBA. — 2 marks
- Compare and contrast Finite Automata with Turing Machines. — 2 marks
- Explain Cook-Levin theorem. — 2 marks
- When is a problem said to be NP-hard? — 2 marks
- Identify the language L = \{a^n b^n \mid n \geq 0, over alphabet \Sigma = \{a, b, c\}\} as per Chomsky hierarchy. — 5 marks
- 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
- 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
- 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
- Identify the validity of the Church-Turing Thesis in modern computation models. — 5 marks
- Identify the automata machines that accept different languages according to the Chomsky hierarchy. — 10 marks
- 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
- 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
Other Formal Language and Automata theroy papers
- Formal Language and Automata theroy — End Sem 2026 — with answer key
- Formal Language and Automata theroy — Mid Sem 1 2026 · Section A
- Formal Language and Automata theroy — Mid Sem 2 2026
- Formal Language and Automata theroy — End Sem 2025
- Formal Language and Automata theroy — Mid Sem 1 2025 — session 2024-25
- Formal Language and Automata theroy — Mid Sem 2 2025 · Section A — session 2025-26
- Formal Language and Automata theroy — End Sem 2024
- Formal Language and Automata theroy — End Sem 2023