Elective Theory of Computation
BE Computer (PU) Semester 43 credit hours
Theory of Computation
SyllabusComing soonUnits and teaching hours for this subject.Open NotesBeing writtenUnit-by-unit notes with examples.Open Old Questions13 questionsFrom PU Spring 2024, PU Spring 2023Open MCQ PracticeComing soonAnswer, see if you’re right straight away, and read why.Open
Recent old questions
a) Convert the following NFA to its equivalent DFA. 3 TASER RG ta é i EN Se Be aN Nina Des PADRE NS cog SO meclpa tN © wine Hep NE See eal i nab! ae (@) aC ;…PU Spring 202420a) What is CFG? Design CFG for language L=a"b"; m =1, n =1 . Test the grammar for derivation of aaaabbb and also draw equivalent parse tree. b) Convert the…PU Spring 202415a) Define PDA with block diagram. Design a PDA which accepts the language L=a"" : n =1 and test for strings aaaaaaaa and aaaaaa. b) Show that the language L=…PU Spring 20248a) Define Turing machine. Design a Turing machine that accepts the language L= a"b’c" : n =0. b) How does a Turing machine compute a function of natural…PU Spring 202415