- Department: Computer Science
- Module co-ordinator: Dr. Steve King
- Credit value: 20 credits
- Credit level: C
- Academic year of delivery: 2020-21
- See module specification for other years: 2019-20
Formal Languages and Automata
Occurrence | Teaching cycle |
---|---|
A | Spring Term 2020-21 to Summer Term 2020-21 |
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.
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. |
Task | Length | % of module mark |
---|---|---|
Online Exam Theory 2 (THE2) |
N/A | 100 |
None
Task | Length | % of module mark |
---|---|---|
Online Exam Theory 2 (THE2) |
N/A | 100 |
Feedback is provided through work in practical sessions, and after the final assessment as per normal University guidelines.
**** 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
Coronavirus (COVID-19): changes to courses
The 2020/21 academic year will start in September. We aim to deliver as much face-to-face teaching as we can, supported by high quality online alternatives where we must.
Find details of the measures we're planning to protect our community.