Atal Bihari Vajpayee Vishwavidyalaya M.Sc. I semester Syllabus
THEORY OF COMPUTATION
ADVANCED DATABASE MANAGEMENT SYSTEM
PROGRAMMING IN PYTHON
AI & MI
PROGRAMMING IN PYTHON LAB
THEORY OF COMPUTATION
UNIT I:
Sets, Relations and Functions, Fundamental Proof Techniques, Introduction of alphabets, Strings and Languages; Automata, Finite automata (FA), Transition System & Function and their properties; Deterministic Finite Automata (DFA) -Formal definition, simplified notations (state transition diagram, transition table), Non-deterministic Finite Automata (NFA -Formal Definition, Acceptability of a String by a DFA & NFA,), Minimizing number of state of a DFA, Finite Automata with output (Moore and Mealy Machine, Procedure for Transforming a Mealy Machine into a Moore Machine and vice versa
UNIT-2
FORMAL LANGUAGES:
Definition of a Grammar, Derivations and the Language Generated by a Grammar, Chomsky Classification of Languages, Languages and Their Relation, Recursive and Recursively Enumerable Sets, Operations on Languages, Languages and Automata
UNIT 3:
Regular expressions (RE)-
Definition, FA and RE, Transition System Containing A-moves, NFAs with A-moves and Regular Expressions, NFA to DFA conversion, Algebraic Method Using Arden's Theorem, Construction of Finite Automata Equivalent to a Regular Expression and vice versa, Equivalence of two FA, Equivalence of two RE, Pumping Lemma for Regular Sets, Application of Pumping Lemma, Closure Properties of Regular Sets, Regular Sets and Regular Grammars, Closure Properties of Regular languages, emptiness, finiteness, membership.
UNIT 4: Context-free Grammars (CFGs)-
Formal definition, sentential forms, leftmost and rightmost derivations, The language of CFG, Derivation tree, Ambiguity in grammars and Languages, Ambiguity in CFG, Simplification of CFG, Normal Forms for CFG (Chomsky Normal Form, Greibach Normal Form), Pumping Lemma for Context-free Languages, Closure Properties of CFG’s
UNIT 5:
Pushdown Automata (PDA):
Formal definition, acceptance by PDA, PDAs and CFGs, CFG to PDA, PDA to CFG, DPDAs -Definition, DPDAs and Regular Languages, DPDAs, and CFLs, Languages of DPDAs, DPDAs. Context Sensitive Grammar, Linear Bounded Automata, Turing Machines -Formal definition and behaviour, Transition diagrams, acceptance by TM, Multi tape Turing Machine, Universal Turing Machine, Halting Problem of Turing Machine
TEXT/REFERENCE BOOKS:
1. “Elements of The Theory of Computation”, H.R.Lewis & C.H. Papadimitriou, P.H.I.
2. “Introduction To Automata Theory, Language and Computation” J.E.Hopcroft, R.Motwani J.D.Ullman, Pearson Education
3. “Theory of Computer Science(Automata, Languages And Computation)”, K.L.P.Mishra, N.Chandrasekaran:,PHI
4. “Introduction to languages and Theory of Computation”, John Martin, McGraw Hill
5. “Introduction To Computer Theory”, D.A.Cohen (J.Wiley)
Lab-1: Programming in Python
1. Python program to find the union of two lists.
2. Python program to find the intersection of two lists,
3. Using for loop, print a table of Celsius/Fahrenheit equivalences. Let ¢ be
the Celsius temperatures ranging from 0 to 100, for each value of ¢, print
the corresponding Fahrenheit temperature.
4. Using while loop, produce a table of sins, cosines and tangents. Make a variable
X in range from 0 to 10 in steps of 0.2. For each value of X, print the value of
sin(x), cos(x) and tan(x).
5. Write a program that reads an integer value and prints —leap yearl or —not a
leap yearl. ’
6. Write a program that takes a positive integer n and then produces n lines of
output shown as follows.
For example, enter a size: 5
*
**
***
****
*****
7. Write a function that takes an integer _n*as input and calculates
the value of 1 + 1/114 1/214 1/31 +... + I/n
8. Write a function that takes an integer input and calculates the factorial of that
number.
9.Write a function that takes a string input and checks if it's a palindrome or not,
10. Write a list function to convert a string into a list, as in list (_abe*) gives [a, b, cl.
11. Write a program to generate Fibonacci series.
12. Write a program to check whether the input number is even or odd.
13. Write a program to compare three numbers and print the largest one.
14. Write a program to print factors of a given number.
15. Write a method to calculate GED of two numbers.
16. Write a program to create Stack Class and implement all its methods. (Use
Lists).
17. Write a program to create Queue Class and implement all its methods. (Use Lists)
18. Write a program to implement linear and binary search on lists.
19. Write a program to sort a list using insertion sort and bubble sort.
20. Python program to remove the “i” th occurrence of the given word in a list where
words repeat.
21. Python program to count the occurrences of each word in a given string sentence.
22. Python program to check if a substring is present in a given string.
23. Python program to map two lists into a dictionary.
24. Python program to count the frequency of words appearing in a string using a
dictionary.
25. Python program to create a dictionary with key as first character and value as
words starting with that character.
26. Python program to find the length of a list using recursion.
27. Python program to read a file“and capitalize the first letter of every word in the
file.
28. Python program to read the contents of a file in reverse order.
29. Python program to create a class in which one method accepts a string from the
user and another prints it.
30. Study and Implementation of Database, Structured Query Language and database
connectivity.