Skip to main content Skip to navigation

Module Catalogue

CS143-10 Logic and Automata

Department
Computer Science
Level
Undergraduate Level 1
Module leader
Ramanujan Maadapuzhi Sridharan
Credit value
10
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry

Download as PDF

Introductory description

This module introduces students to formal methods for describing and analysing the behaviour of computational systems.

Module aims

To introduce students to basic connections between mathematical logic, formal languages, automata theory and verification by model checking. Students will also learn and practise proof techniques for reasoning about the limits of various computational models, including concepts such as the pumping lemma and diagonalisation.

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Propositional logic and predicate logic, proofs, semantics, regular languages, finite automata, non-determinism, regular expressions, pumping lemma, closure properties, Turing-recognisable languages, Turing machines, decidability, reducibility.

Learning outcomes

By the end of the module, students should be able to:

  • Construct and reason about proofs in a variety of logics.
  • Apply logic to specify and verify computing systems.
  • Specify formal languages and translate between various forms of formal language descriptions.
  • Argue that given formal languages are (or are not) regular.
  • Understand basic connections between expressive power of some logics and computational models.
Indicative reading list

(a) W. Thomas. Languages, Automata and Logic, Handbook of Formal Languages, volume 3, Springer-Verlag, 1997.
(b) M. Sipser, Introduction to the theory of computation, Cengage Learning, 2013.
(c) J. E. Hopcroft; R. Motwani; J. D. Ullman, Introduction to automata theory, languages, and computation, Pearson, 2014.
(d) B. Khoussainov and A. Nerode, Automata Theory and its Applications. Progress in Computer Science and Applied Logic, Volume 21. Birkhauser, 2001.
(e) M. Fitting, First-order logic and automated theorem proving, Springer-Verlag, 1996.

Subject specific skills
  1. Formal reasoning about computer systems, languages and proofs. Theory and practice relating to reliability of systems form a vital part of computer science.
  2. Formally describing, reasoning about and comparing various computational models. Applied in the study of complexity of computational problems.
Transferable skills

Critical Thinking, problem-solving, ability to define problems, design solutions and conduct mathematically rigorous analysis of possible solutions .

Study time

Type Required
Lectures 30 sessions of 1 hour (30%)
Seminars 9 sessions of 1 hour (9%)
Private study 59 hours (59%)
Assessment 2 hours (2%)
Total 100 hours
Private study description

Inclusive of preparation for seminars, background reading, problem set assignments and revision.

Costs

No further costs have been identified for this module.

You do not need to pass all assessment components to pass the module.

Assessment group D
Weighting Study time
Problem Set 1 10%

Written homework assignment

This assessment is eligible for self-certification (extension).
Problem Set 2 10%

Written homework assignment

This assessment is eligible for self-certification (extension).
In-person Examination 80% 2 hours

Final Examination (written)

  • Answerbook Pink (12 page)
Assessment group R
Weighting Study time
In-person Examination - Resit 100%

Resit Examination

  • Answerbook Pink (12 page)
Feedback on assessment

Marks, feedback on Tabula.

Past exam papers for CS143

Courses

This module is Core for:

  • UCSA-G4G1 Undergraduate Discrete Mathematics
    • Year 1 of G4G1 Discrete Mathematics
    • Year 1 of G4G1 Discrete Mathematics
  • Year 1 of UCSA-G4G3 Undergraduate Discrete Mathematics