Theory of Computation

• Chapter 1: Basic Foundations. Notes and past questions on Basic Foundations for TU BSc CSIT Theory of Computation.
• Chapter 2: Introduction to Finite Automata. Notes and past questions on Introduction to Finite Automata for TU BSc CSIT Theory of Computation.
• Chapter 3: Regular Expressions. Notes and past questions on Regular Expressions for TU BSc CSIT Theory of Computation.
• Chapter 4: Context Free Grammar. Notes and past questions on Context Free Grammar for TU BSc CSIT Theory of Computation.
• Chapter 5: Push Down Automata. Notes and past questions on Push Down Automata for TU BSc CSIT Theory of Computation.
• Chapter 6: Turing Machines. Notes and past questions on Turing Machines for TU BSc CSIT Theory of Computation.
• Chapter 7: Undecidability and Intractability. Notes and past questions on Undecidability and Intractability for TU BSc CSIT Theory of Computation.

• Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA.S→AS∣εS \rightarr... (2081)
• List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.[10] (2081)
• Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q0, q1, q2}, {a, b}, {a, b, B}, δ, q2, B,... (2081)
• Does machine always refer to hardware? Justify. Define positive closure and Kleene closure. [5] (2081)
• What is undecidable problem? Discuss about Post Correspondence Problem. [5] (2081)
• Define the language of a grammar. For the grammar , show the leftmost derivation for the string 00100 with its parse tree. S→0S0∣1∣εS \ri... (2081)
• Define ε\varepsilonε-closure of a state. Differentiate between Moore and Mealy machine. [5] (2081)
• Represent the following regular grammar to finite automata. S→aA∣aB∣εS \rightarrow aA \mid aB \mid \varepsilonS→aA∣aB∣εA→aA∣aSA \rightarr... (2081)
• Design the DFA that accepts binary string ending with '00' and show its extended transition function for the string 111000. [5] (2081)
• Convert the following grammar to CNF. S→AAB,A→aA∣ε,B→ab∣aS \rightarrow AAB, \quad A \rightarrow aA \mid \varepsilon, \quad B \rightarrow... (2081)
• Turing Machine Analysis (2081)
• Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA. [5] (2081)
• What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.[10] (2080)
• How does Turing machine accept a string? Design a Turing Machine over the alphabet {0,1,a} that processes the string defined by L = {a01a... (2080)
• Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.[10] (2080)

Frequently asked questions

Based on the official syllabus.