Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme



About Me
Course Details and Syllabus

Module-1 Foundations of Finite Automata

Introducing automata
Alphabet, Strings, and Languages

Categories of DFA






Module-2  

Regular Expressions and properties



        Arden's Theorem

Converting Regular Expressions to Finite Automata

Pumping Lemma 



Context-Free Grammars and Applications

        Ambiguous Grammar
        Resolving Ambiguity
        

Module 3

Simplification of Context-Free Languages



Push Down Automata



Properties of Context Free Languages

   

Module 4


Computability


Comments

Post a Comment

Popular posts from this blog

Motivation- Computability

 "Computability helps us understand what computers can do, what they can never do, and why . It's like learning the rules of the game before playing." 🔍 Real-Life Examples That Explain Computability 1. 🧠 The Halting Problem – Can You Predict the Future of Code? Scenario: You write a program and wonder: Will it finish running or get stuck in an infinite loop? Wish: A super tool that tells you: "This code will stop after 10 steps." "This code will run forever." Reality: Computability theory proves this is impossible in general. No tool can perfectly do this for all programs. 📌 Moral: Some problems look simple but are unsolvable by any computer . 2. 🎮 Game Solver – Will Mario Always Win? Scenario: Can you write a program that decides if Mario can always finish any level of a game? For very complex games, this problem becomes equivalent to the Halting Problem. ✅ For small levels: Yes. ❌ For complex levels with infinite combinations:...
Read more

Theory of Computation PCCST302 Syllabus

  SEMESTER 3 THEORY OF COMPUTATION (CommontoCS/CA/CM/CD/CN/CC)   Course  Code PCCST302 CIE Marks 40 Teaching Hours/Week (L: T:P: R) 3:1:0:0 ESE Marks 60 Credits 4 Exam  Hours 2Hrs 30 Mins Prerequisites(if  any) PCCST205 Course  Type Theory   Course Objectives: 1. To introduce the concept of formal languages. 2. To discuss the Chomsky classification  of formal languages with a discussion on grammar and automata for regular, context-free, context-sensitive, and unrestricted languages. 3. To discuss the notions of decidability and the halting problem.  SYLLABUS   Module No. Syllabus  Description Contact Hours       1 Foundations(Linz,Hopcroft) Motivation for studying c...
Read more