meta data for this page
  •  

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
public:dugc:cs208-toc [2015/07/08 15:46] – anupreetpublic:dugc:cs208-toc [2020/06/05 02:36] (current) – external edit 127.0.0.1
Line 26: Line 26:
  
 I  Title of the Course  Logic for Computer Science I  Title of the Course  Logic for Computer Science
-i   Credit Structure     L   T   P  C +i   Credit Structure\\ 
-____________________     3   0   0  6+ L   T   P  C\\ 
 + 3   0   0  6\\
 ii  Prerequisite, if any - None ii  Prerequisite, if any - None
  
Line 82: Line 83:
 Press, 2004. Press, 2004.
  
----------------+---- 
 Once this course is introduced, CS 208 - Automata Theory and Logic can be Once this course is introduced, CS 208 - Automata Theory and Logic can be
 renamed "Theory of Computation" and the following can be dropped from CS renamed "Theory of Computation" and the following can be dropped from CS
Line 98: Line 100:
 Current curriculum:    Current curriculum:   
  
-I  Title of the Course  Theory of Computation +I  Title of the Course  Theory of Computation\\ 
- i   Credit Structure + i   Credit Structure\\ 
- L  T  P  C + L  T  P  C\\ 
- 3  0  0  6 + 3  0  0  6\\ 
- ii  Prerequisite, if any Discrete Structures (CS 207) + ii  Prerequisite, if any Discrete Structures (CS 207)(for the student)
-        (for the student)+
  
-v   Course content+v   Course content\\
 Rudiments of formal languages. Finite state machines(DFA/NFA/epsilon NFAs), regular expressions. Properties of regular languages. My hill-Nerode Theorem. Non-regularity. Push down automata. Properties of context-free languages. Turing machines:Turing hypothesis, Turing computability, Nondeterministic, multi tape and other versions of Turing machines. Church's thesis, recursively enumerable sets and Turing computability. Universal Turing machines. Unsolvability, The halting problem, partial solvability, Turing Rudiments of formal languages. Finite state machines(DFA/NFA/epsilon NFAs), regular expressions. Properties of regular languages. My hill-Nerode Theorem. Non-regularity. Push down automata. Properties of context-free languages. Turing machines:Turing hypothesis, Turing computability, Nondeterministic, multi tape and other versions of Turing machines. Church's thesis, recursively enumerable sets and Turing computability. Universal Turing machines. Unsolvability, The halting problem, partial solvability, Turing
 enumerability, acceptability and decidability, unsolvable problems about Turing Machines. Post`s correspondence problem. enumerability, acceptability and decidability, unsolvable problems about Turing Machines. Post`s correspondence problem.
  
-Texts/References: +Texts/References:\\ 
-1. Introduction to Automata Theory, Languages and Computation, +1. Introduction to Automata Theory, Languages and Computation,\\ 
-by John. E. Hopcroft, Rajeev Motwani, J. D. Ullman,+by John. E. Hopcroft, Rajeev Motwani, J. D. Ullman,\\
 published by Pearson Education Asia, 2006.\\ published by Pearson Education Asia, 2006.\\
-2. Elements of the Theory of Computation, by H.R. Lewis and C.H.Papadimitrou,+2. Elements of the Theory of Computation, by H.R. Lewis and C.H.Papadimitrou,\\
 published by Prentice Hall Inc, 1981. published by Prentice Hall Inc, 1981.