• Student home
• Things to know this week
• Student news
• Student events
• New students' welcome
• Studying at York
  • Semesters
  • Teaching hours
  • Enrolment
  • Manage your studies
    • Enrol or re-enrol
    • e:Vision and your student record
    • Your timetable
    • Change your plan
    • Programmes and modules
      • Programme specifications
      • Studying beyond your department
      • Module catalogue
    • University study spaces
  • Student Visa holders
  • Study skills
  • Assessment and examination
  • Academic progress issues
  • Graduation
• York Online students
• Support and advice
• Health and wellbeing
• Work, volunteering and career planning
• Study Abroad
• Accommodation
• IT and online services
• Finance
• Student life in York
• If things go wrong

Theory 2: Formal Languages & Automata - COM00014C

« Back to module search

• Department: Computer Science
• Credit value: 20 credits
• Credit level: C
• Academic year of delivery: 2024-25
  • See module specification for other years: 2022-23 2023-24

Module summary

Formal Languages and Automata

Module will run

Occurrence	Teaching period
A	Semester 2 2024-25

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

• Describe and illustrate the concepts of formal languages, automata and grammars, and the relations between them;
• Construct a variety of abstract machines including: deterministic and non-deterministic finite automata, deterministic and non-deterministic pushdown automata and Turing machines;
• Distinguish different classes of automata, and the languages they accept;
• Apply a variety of operations to transform and convert between automata;
• Convert between grammars and automata for regular and context-free languages;
• Demonstrate that a grammar is ambiguous;
• Apply the pumping lemma for regular and context-free languages to show a language is not regular or context-free respectively;
• Describe the Chomsky hierarchy;
• Identify key applications in computing where regular and context-free languages are used in practice; and
• Use automata theory as the basis for building lexers and parsers.

Indicative assessment

Task	% of module mark
Open Examination	100

Special assessment rules

None

Indicative reassessment

Task	% of module mark
Open Examination	100

Module feedback

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

Indicative reading

• *** Peter Linz, An introduction to formal languages and automata. Sixth Edition. Jones and Bartlett Computer Science. 2017
• ** D.I. Cohen, Introduction to Computer Theory. 2nd Edition. Wiley. 1997
• ** Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D., Introduction to Automata Theory, Languages and Computation (3rd ed.), Pearson Education, 2013
• ** S.H. Rodger and T.W. Finley, JFLAP: An interactive formal language and automata package. Jones and Bartlett Computer Science. 2006. Available online
• * 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