Theory of Computation PCCST302 Syllabus

 

SEMESTER 3 THEORY OF COMPUTATION

(CommontoCS/CA/CM/CD/CN/CC)

 

Course Code

PCCST302

CIEMarks

40

Teaching Hours/Week (L: T:P: R)

3:1:0:0

ESEMarks

60

Credits

4

Exam Hours

2Hrs 30Mins

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 computability, need for mathematical modeling - automata, Introducing automata through simple models - On/Off switch, coffee vending machine. Three basic concepts: Alphabet, Strings, and Languages

FiniteAutomata(Linz,Hopcroft)

Formal definition of a finite automaton, Deterministic Finite Automata (DFA), Regular languages,Nondeterminism (guess and verify paradigm), Formal definition of a nondeterministic finite automaton, NFA with epsilon transitions, Eliminating epsilon transitions (Proof not expected), Equivalence of NFAs and DFAs (Proof not expected) - The Subset Construction. DFA State Minimization, Applications of finite automata - text search, keyword recognition

 

 

 

11



2
Regular Expressions(Linz)

The formal definition of a regular expression,Building Regular Expressions,Equivalence with finite automata(Proof not expected)-
Converting FA to Regular Expressions, Converting Regular Expressions to FA, Pattern Matching and Regular Expressions, Regular grammar, Equivalence with FA - Conversion in both directions

Properties of Regular Languages(Linz)

Closure and Decision Properties of Regular Languages(with proofs),The Pumping Lemma for Regular Languages (with formal proof), Pumping lemma as a tool to prove non regularity of languages

Context-Free Grammars and Applications(Linz)

Formal definition of a context-free grammar, Designing context-free grammars,Leftmost and Rightmost Derivations Using a Grammar,Parse Trees, Ambiguous Grammars, Resolving ambiguity, Inherent ambiguity, CFGs, and programming languages









    11









     3
Pushdown Automata(Linz)

Formal definition of a pushdown automaton,DPDA and NPDA,Examples of pushdown automata

Equivalence NPDAs and CFGs(Proof not expected)-conversions in both directions

Simplification of Context-Free Languages(Linz)

Elimination of useless symbols and productions, Eliminating epsilon productions, Eliminating unit productions, Chomsky normal form, Greibach normal form,

Properties of Context-Free Languages(Linz)

The Pumping Lemma for Context-Free Languages (with formal proof), Closure and Decision Properties of Context-Free Languages (with formal proofs)

 

 

 

 11

 

 

 

 

 

 

 

 

 

 4

 

 

Turing Machines(Kozen)

The formal definition of a Turing machine,Examples of Turing machines- Turing machines as language acceptors,Turing machines as computers of functions, Variants of Turing Machines(Proofs for equivalence with basic model not expected), Recursive and recursively enumerable languages
Chomskian hierarchy,Linear bounded automaton as a restricted TM.
Computability(Kozen)

Church Turing thesis, Encoding of TMs, Universal Machine and Diagonalization,Reductions,Decidable and Undecidable Problems,Halting problem, Post Correspondence Problem and the proofs for their undecidability.

 

 

 

 

 11

 

 

Course Assessment Method(CIE: 40 marks, ESE: 60 marks)

Continuous Internal Evaluation Marks(CIE):

 

 

Attendance

 

Assignment/ Microproject

Internal Examination-1 (Written)

Internal Examination-2 (Written )

 

Total

5

15

10

10

40

 

End Semester Examination Marks(ESE)

In PartA,all questions need to be answered and in PartB,each student can choose anyone full 
question out of two questions

 

PartA

PartB

Total

●     2 Questions from each module. 

●     Total of 8 Questions,each carrying 3 marks

 

(8x3=24marks)

●     Each question carries 9marks.

●     Two questions will be given from each module,out of which 1 question should be answered.

●     Each question can have a maximum of 3 subdivisions.

(4x9=36marks)

 

 

 

60

CourseOutcomes(COs)

At the end of the course students should be able to:

 

 

Course Outcome

Bloom’s Knowledge Level(KL)

 

CO1

Classify formal languages into regular,context-free,context-sensitive,

and unrestricted languages.

 

K2

 

CO2

Develop finite state automata,regular grammar,and regular

expression.

 

K3

 

CO3

Model push-down automata and context-free grammar representations

for context-free languages.

 

K3

 

CO4

Construct uring Machines to accept recursive and recursively

enumerable languages. 

 

K3

 

CO5

Describe the notions of decidability and undecidability of problems,

the Halting problem.

 

K2

Note:K1-Remember,K2-Understand,K3-Apply,K4-Analyse,K5-Evaluate,K6-Create

CO-POMappingTable(MappingofCourseOutcomestoProgramOutcomes)

 

 

PO1

PO2

PO3

PO4

PO5

PO6

PO7

PO8

PO9

PO10

PO11

PO12

CO1

3

3

3

3

 

 

 

 

 

 

 

3

CO2

3

3

3

3

 

 

 

 

 

 

 

3

CO3

3

3

3

3

 

 

 

 

 

 

 

3

CO4

3

3

3

3

 

 

 

 

 

 

 

3

CO5

3

3

3

3

 

 

 

 

 

 

 

3

Note:1:Slight(Low),2:Moderate(Medium),3:Substantial(High),-:NoCorrelation

 

TextBooks

Sl.No

TitleoftheBook

NameoftheAuthor/s

Nameofthe Publisher

Edition andYear

1

An     Introduction     to     Formal Languages and Automata

Peter Linzand Susan H. Rodger

Jones     and     Bartlett Publishers, Inc

7/e,2022

 

2

Introduction to Automata Theory LanguagesAnd Computation

John   .Hopcroft, Jeffrey D.Ullman

Rainbow                               Book Distributiors

3/e,2015

3

Automata and Computability

Dexter C.Kozen

Springer

1/e,2007

 

 

Reference Books

Sl.No

Title of the Book

Name of the Author/s

Name of the Publisher

Edition andYear

 

1

Introduction to the Theory  of Computation

Michael Sipser

Cengage India Private Limited 

3/e,2014

 

2

Introduction to Languages and the Theory of Computation

John C Martin

McGraw-Hill Education

4/e,2010

 

3

Theory     of    Computation:A Problem-Solving Approach

KaviMahesh

Wiley

1/e,2012

4

ElementsoftheTheoryof Computation

HarryR.Lewis,Christos Papadimitriou

PearsonEducation

2/e,2015

VideoLinks(NPTEL,SWAYAM…)

Module No.

LinkID

1

https://archive.nptel.ac.in/courses/106/104/106104148/

https://nptel.ac.in/courses/106106049

 

2

https://archive.nptel.ac.in/courses/106/104/106104148/

https://nptel.ac.in/courses/106106049

 

3

https://archive.nptel.ac.in/courses/106/104/106104148/

https://nptel.ac.in/courses/106106049

 

4

https://archive.nptel.ac.in/courses/106/104/106104148/

https://nptel.ac.in/courses/106106049

 

Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion - Examples DFA state minimization DFA vs NFA Applications of Fini...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more

Example DFAs University Questions

Image
 Even number of a's ab as a substring empty set All strings except the empty set over the alphabet {0.1} Accept empty string and 0 every odd position of the string w is 1 begins with 1 ends with 0 {w| w contains at least 3 ones }  {w|w contains the substring 0101 ie; w=x0101y for some x and y} {w|w has length at least 3 and its third symbol is a zero} {w|w starts with 0 and has odd length , or starts with 1 and has even length } construct a DFA which accepts the language L = {a^N | N ≥ 1} String in {a,b} with odd number of a's starting with 01 over the alphabet [1,0} Strings ending with abc Program to build a DFA that checks if a string ends with "01" or "10" build a DFA to accept strings that start and end with same character build DFA that starts and end with 'a' from input (a, b) build a DFA that accepts strings starting and ending with different character DFA of a string starting with 0 and ends with 10? DFA of a string of a's and b's  st...
Read more