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

Formal Definition - Turing Machine

Image
  📘 Formal Definition - Turing Machine A Turing Machine is a nine-tuple M = ( Q , Σ , Γ , δ , B , ⊢ , s,t, r) M = (Q, \Sigma, \Gamma, \delta, s_0, B, ⊢, s_{acc}, s_{rej}) where: Q – a finite set of states (typically denoted r , s , t , ... ). Σ – the input alphabet , which does not contain the blank symbol B or the left-end marker ⊢ . Γ – the tape alphabet , satisfying Σ ⊆ Γ , B ∈ Γ , ⊢ ∈ Γ Σ ⊆ Γ, \quad B ∈ Γ, \quad ⊢ ∈ Γ Every cell of the tape contains one symbol from Γ. δ – the transition function δ : ( Q − { t,r } ) × Î“ → Q × Î“ × { L , R } δ : (Q - \{s_{acc}, s_{rej}\}) \times Γ \to Q \times Γ \times \{L, R\} Given the current state and the symbol under the tape head, the machine writes a symbol, moves Left (L) or Right (R), and enters a new state. s ∈ Q – the initial (start) state . B ∈ Γ – the blank symbol , representing the empty tape cell. ⊢ ∈ Γ – the left-end marker , which appears at the extreme left of the tape and is never overwritte...
Read more

Introduction to Turing Machine

Image
  🌟 Introduction to Turing Machines A Turing Machine (TM) is a theoretical model of computation introduced by Alan Turing in 1936 . It is one of the most fundamental concepts in computer science because it precisely captures what it means for a function or a problem to be computable . 🧠 Why Turing Machines? Before Turing’s time, mathematicians wondered: “Is there a clear, mechanical procedure to determine whether a mathematical statement is true or false?” To answer this, Turing proposed a simple abstract machine that could simulate the logic of any computer algorithm. His goal was to define computation itself in a mathematical way. The beauty of the Turing Machine lies in its simplicity — despite being an abstract model, it can simulate any computer program that could ever be written. ⚙️ Structure of a Turing Machine A Turing Machine consists of: A tape – an infinite strip divided into cells, each containing one symbol (like a very long memory). A tape hea...
Read more