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

  1. What are alphabets in a formal language? — 2 marks
  2. Name any two key components of a Pushdown Automaton (PDA). — 2 marks
  3. Explain the difference between a DFA and a Non-deterministic Finite Automaton (NFA). — 2 marks
  4. Discuss the abstract computational devices in Automata. — 2 marks
  5. List examples of NP Hard and NP Complete problems. — 2 marks
  6. What is a derivation tree? — 2 marks
  7. Discuss the transition function difference in case of DFA and NFA. — 2 marks
  8. How regular expressions are used to represent languages? — 2 marks
  9. What is LHAT? — 2 marks
  10. What is intractability? — 2 marks
  11. Differentiate between DFA and NFA. — 5 marks
  12. Write down the steps of convert this NFA into DFA. — 5 marks
  13. What is a Turing Machine (TM) and what makes it a universal model of computation? — 5 marks
  14. What are closure properties? Explain any four. — 5 marks
  15. Give examples of Hamiltonian paths and Hamiltonian circuits. — 5 marks
  16. Design PDA for \{wcw^T \mid w = \{a,b ^*\} — 10 marks
  17. Discuss various types of grammars and the languages which are associated with them. — 10 marks
  18. Check whether the given FA accepts the language set L=\{0, 10, 110, 1100\}. Also discuss the importance of Language acceptance. — 5 marks
  19. What is a formal language and how it is different from natural languages? — 2 marks
  20. Explain how a grammar (G) is represented in formal language theory. — 2 marks
  21. What is the difference between Regular and context free grammar? — 2 marks
  22. Explain Arden's theorem. — 2 marks
  23. Recall Chomsky's Normal Form. Give an example. — 2 marks
  24. 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
  25. Outline the restrictions on tape movement in a LBA. — 2 marks
  26. Compare and contrast Finite Automata with Turing Machines. — 2 marks
  27. Explain Cook-Levin theorem. — 2 marks
  28. When is a problem said to be NP-hard? — 2 marks
  29. Identify the language L = \{a^n b^n \mid n \geq 0, over alphabet \Sigma = \{a, b, c\}\} as per Chomsky hierarchy. — 5 marks
  30. 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
  31. 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
  32. 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
  33. Identify the validity of the Church-Turing Thesis in modern computation models. — 5 marks
  34. Identify the automata machines that accept different languages according to the Chomsky hierarchy. — 10 marks
  35. 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
  36. 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

Related