Skip to content
0091-484-2540360
[email protected]
Kalamassery, Kochi, Ernakulam
Search for:
TOP MENU
Primary Menu
HOME
ABOUT US
Albertian Institute of Science & Technology
Instructors
Annual Appraisal
Research & Consultancy @ AISAT
ALL COURSES
Departments
AI & ML Courses
ASH Courses
CE Courses
CSE Courses
ECE Courses
EEE Courses
ME Courses
First Year Courses
Applied Science & Humanities Courses
Engineering Chemistry Courses
Engineering Mathematics Courses
Engineering Physics Courses
English Courses
General Courses
General Courses
IIC Orientations
Physical Education Training
Placement Training
Research Orientation
Soft Skill Development
CONTACT US
PROFILE
LOGIN
Main Site
Search for:
Main Site
0091-484-2540360
[email protected]
Kalamassery, Kochi, Ernakulam
Home
All Courses
PCCST302 THEORY OF COMPUTATION
Curriculum
4 Sections
55 Lessons
10 Weeks
Expand all sections
Collapse all sections
MODULE 1
12
1.1
MOTIVATION FOR STUDYING COMPUTABILITY
1.2
NEED FOR MATHEMATICAL MODELING
1.3
AUTOMATA: INTRODUCING AUTOMATA THROUGH SIMPLE MODELS
1.4
THREE BASIC CONCEPTS: ALPHABET, STRINGS, AND LANGUAGES
1.5
FORMAL DEFINITION OF A FINITE AUTOMATA
1.6
DETERMINISTIC FINITE AUTOMATA(DFA)
1.7
NON DETERMINISTIC FINITE AUTOMATA
1.8
NFA WITH EPSILON TRANSITIONS
1.9
EQUIVALENCE OF NFAs AND DFAs
1.10
THE SUBSET CONSTRUCTION
1.11
DFA STATE MINIMIZATION
1.12
APPLICATIONS OF FINITE AUTOMATA: TEXT SEARCH, KEYWORD RECOGNITION
MODULE 2
17
2.1
REGULAR EXPRESSIONS: THE FORMAL DEFINITION OF A REGULAR EXPRESSION
2.2
BUILDING REGULAR EXPRESSIONS
2.3
CONVERTING FA TO REGULAR EXPRESSIONS
2.4
CONVERTING REGULAR EXPRESSIONS TO FA
2.5
PATTERN MATCHING AND REGULAR EXPRESSION
2.6
REGULAR GRAMMAR: CONVERTING RG TO FA
2.7
CONVERTING FA TO RG
2.8
CLOSURE AND DECISION PROPERTIES OF REGULAR LANGUAGES
2.9
THE PUMPING LEMMA FOR REGULAR LANGUAGES
2.10
PUMPING LEMMA AS A TOOL TO PROVE NON REGULARITY OF LANGUAGES
2.11
FORMAL DEFINITION OF A CONTEXT FREE GRAMMAR
2.12
DESIGNING CONTEXT FREE GRAMMARS
2.13
LEFTMOST AND RIGHTMOST DERIVATIONS USING A GRAMMAR
2.14
PARSE TREES
2.15
AMBIGUOUS GRAMMARS
2.16
RESOLVING AMBIGUITY
2.17
INHERENT AMBIGUITY
MODULE 3
12
3.1
FORMAL DEFINITION OF A PUSHDOWN AUTOMATA
3.2
DPDA AND NPDA
3.3
EXAMPLES OF PUSHDOWN AUTOMATA
3.4
CONVERTING PDA TO CFG
3.5
CONVERTING CFG TO PDA
3.6
ELIMINATION OF USELESS SYMBOLS AND PRODUCTIONS
3.7
ELIMINATING EPSILON PRODUCTIONS
3.8
ELIMINATING UNIT PRODUCTIONS
3.9
CHOMSKY NORMAL FORM
3.10
GREIBACH NORMAL FORM
3.11
THE PUMPING LEMMA FOR CONTEXT FREE LANGUAGES
3.12
CLOSURE AND DECISION PROPERTIES OF CONTEXT FREE LANGUAGES
MODULE 4
14
4.1
THE FORMAL DEFINITION OF A TURING MACHINE
4.2
EXAMPLES OF TURING MACHINES
4.3
TURING MACHINE AS LANGUAGE ACCEPTORS
4.4
TURING MACHINES AS COMPUTERS OF FUNCTIONS
4.5
VARIANTS OF TURING MACHINES
4.6
RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES
4.7
CHOMSKIAN HIERARCHY
4.8
LINEAR BOUNDED AUTOMATON AS A RESTRICTED TM
4.9
CHURCH TURING THESIS
4.10
ENCODING OF TMs
4.11
UNIVERSAL MACHINE AND DIAGONALIZATION
4.12
DECIDABLE AND UNDECIDABLE PROBLEMS
4.13
HALTING PROBLEMS
4.14
POST CORRESPONDENCE PROBLEM
This content is protected, please
login
and
enroll
in the course to view this content!
Modal title
Main Content
