Accessibility statement

Theory 2: Formal Languages & Automata - COM00014C

« Back to module search

  • Department: Computer Science
  • Module co-ordinator: Prof. Steve King
  • Credit value: 20 credits
  • Credit level: C
  • Academic year of delivery: 2021-22

Module summary

Formal Languages and Automata

Module will run

Occurrence Teaching period
A Spring Term 2021-22 to Summer Term 2021-22

Module aims

Students taking this module will be introduced to the concepts of formal languages and the abstract machines that accept them as a way of describing computation. Students will have a deep understanding of finite automata and pushdown automata, with their associated languages and related proof techniques, and will be introduced to more complex machines accepting context sensitive and recursively enumerable languages for purposes of being able to identify and describe them.

Module learning outcomes

 

T201

Describe and illustrate the concepts of formal languages, automata and grammars, and the relations between them;

T202

Construct a variety of abstract machines including: deterministic and non-deterministic finite automata, deterministic and non-deterministic pushdown automata and Turing machines.

T203

Differentiate between deterministic and non-deterministic finite automata and convert between them

T204

Distinguish the differences between different classes of automata, and the languages they accept

T205

Apply the pumping lemma for regular languages to show a language is not regular

T206

Apply a variety of operations to transform automata.

T207

Generate regular expressions from finite automata

T208

Convert between grammars and push-down automata for context-free languages

T209

Demonstrate that a grammar is ambiguous

T210

Identify if a language is not context-free

T211

Produce simple examples for a Turing Machine and the languages it accepts

T212

Describe the Chomsky hierarchy

T213

Identify key applications in computing where regular and context-free languages are used in practice.

Assessment

Task Length % of module mark
Online Exam -less than 24hrs (Centrally scheduled)
Theory 2: Formal Languages & Automata (THE2)		 3 hours 100

Special assessment rules

None

Reassessment

Task Length % of module mark
Online Exam -less than 24hrs (Centrally scheduled)
Theory 2: Formal Languages & Automata (THE2)		 3 hours 100

Module feedback

Feedback is provided through work in practical sessions, and after the final assessment as per normal University guidelines.

Indicative reading

**** Martin, John C., Introduction to Languages and the Theory of Computation (4th ed.), McGraw Hill, 2010

** Rich, Elaine, Automata, Computability and Complexity, Pearson Education, 2008

** Sipser, Michael, Introduction to the Theory of Computation (3rd ed.), South-Western College Publishing, 2012

* Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D., Introduction to Automata Theory, Languages and Computation (3rd ed.), Pearson Education, 2013

* Arora, Sanjeev and Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, 2009

++ Garey, Michael R. and Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979


The information on this page is indicative of the module that is currently on offer. The University is constantly exploring ways to enhance and improve its degree programmes and therefore reserves the right to make variations to the content and method of delivery of modules, and to discontinue modules, if such action is reasonably considered to be necessary by the University. Where appropriate, the University will notify and consult with affected students in advance about any changes that are required in line with the University's policy on the Approval of Modifications to Existing Taught Programmes of Study.