ගණනය කිරීම් න්‍යාය

කාලය: ආසන්න වශයෙන් දේශන පැය 30 ක්

පූර්ව අවශ්‍යතා: කිසිවක් නැත

ඉගෙනීමේ අරමුණු

1. To introduce the mathematical formalisms of formal languages, finite automata, push downautomata and Turing machines.
2. To explain their applications to computer languages and compilers.
3. To provide exposure to the theory of complexity and intractable problems

පාඨමාලා අන්තර්ගතය

1. Mathematical Preliminaries
2. Alphabets and Languages
3. Finite automata
4. Context free languages
5. Turing Machines
6. Computational Complexity

ඉගෙනීමේ ප්‍රතිඵල

මෙම පාඨමාලාව අවසානයේදී, සිසුන්ට පහත සඳහන් දෑ කළ හැකි වනු ඇත.

1. Define and manipulate strings.
2. Define languages; and perform language operations.
3. Define and identify regular languages; and represent them finitely.
4. Define a deterministic finite automaton; and describe its operation.
5. Define a nondeterministic finite automaton; and describe its operation.
6. Explain the relationship between regular languages and finite automata.
7. Construct finite automata accepting regular languages.
8. Define and identify context free grammars and languages.
9. Define a pushdown automaton; and describe its operation.
10. Relate context free languages with pushdown automata.
11. Construct pushdown automata accepting context free languages.
12. Explain and apply Pumping lemma.
13. Define a Turing machine; and describe its operation.
14. Describe the computation with Turing machine

ආශ්‍රයන්

1. H.R. Lewis, C.H. Papadimitrio. Elements of the Theory of Computation. Prentice Hall. 2nd Edition,1998
2. D.C. Kozen. Automata and Computability, Springer-Verlang, New York, 1997