CS259 Formal Languages Skip to main content Skip to navigation Sign in Study Research Business Alumni News Engagement Search Warwick Search Department of Computer Science Admissions Undergraduate Postgraduate Taught Degree Apprenticeships Teaching Coronavirus(Restricted permissions) DCS Self Isolation Notification Student Support Appointment Booking Form Course Structures Student Handbook(Restricted permissions) Modules Taught Research Doctoral Studies Interdisciplinary Research Centres Impact and Innovation Applied Computing Artificial Intelligence and Human-Centred Computing Data Science, Systems and Security Theory and Foundations People News Events Computer Science Colloquium Outreach News Upcoming Events Past Events Projects Report(Restricted permissions) Vacancies Intranet(Restricted permissions) Teaching Modules Taught CS259 CS259 Formal Languages CS259-15 Formal Languages Academic year 20/21 Department Computer Science Level Undergraduate Level 2 Module leader Ramanujan Maadapuzhi Sridharan Credit value 15 Module duration 10 weeks Assessment Multiple Study location University of Warwick main campus, Coventry Download as PDF Description Study Assessment Availability Introductory description The module introduces methods used to describe and reason about formal languages (such as programming languages). This module is only available to students in the second year of their degree and is not available as an unusual option to students in other years of study. Module aims The module presents a classification of formal languages (Chomsky hierarchy) and techniques for locating languages within it (closure properties, pumping lemmas). Automata models corresponding to various levels of the Chomsky hierarchy are discussed along with the fundamental notion of computability. These concepts are central to computer science. 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. Regular languages: finite automata, non-determinism, regular expressions, pumping lemma, non-regular languages, minimisation, translations between automata and regular expressions, closure properties Context-free languages: context-free grammars, ambiguity, Chomsky normal form, pushdown automata, pumping lemma, translations between automata and grammars, closure properties Introduction to lexical analysis and parsing Turing-recognisable languages: Turing machines, Church-Turing thesis, decidability, reducibility, the halting problem Learning outcomes By the end of the module, students should be able to: Specify formal languages. Translate between various forms of formal language descriptions. Argue that given formal languages are (or are not) regular or context-free. Understand the operation of tools for lexical analysis and parsing. Understand ideas of decidability and the Church-Turing thesis. Indicative reading list Please see Talis Aspire link for most up to date list. View reading list on Talis Aspire Subject specific skills Formally describing, reasoning about and comparing various computational models. Applied in the study of complexity of computational problems. Designing basic tools for lexing and parsing. Applied in the design of compilers. Transferable skills Critical Thinking - Problem-solving, rigorous analysis of possible solutions. Study time Type Required Lectures 30 sessions of 1 hour (20%) Seminars 9 sessions of 1 hour (6%) Private study 111 hours (74%) Total 150 hours Private study description Working on weekly exercise sheets. Background reading between lectures. Exam revision and solving old/sample exam papers. Costs No further costs have been identified for this module. You do not need to pass all assessment components to pass the module. Students can register for this module without taking any assessment. Assessment group D2 Weighting Study time Programming assignment 20% CS259 10% 50 Minute class test 2 hour online examination (Summer) 70% Examination ~Platforms - AEP Online examination: No Answerbook required Assessment group R Weighting Study time Online Resit Examination (September) 100% Resit examination ~Platforms - AEP Online examination: No Answerbook required Feedback on assessment Individual written feedback on each assignment. Past exam papers for CS259 Courses This module is Core for: Year 2 of UCSA-G500 Undergraduate Computer Science Year 2 of UCSA-G503 Undergraduate Computer Science MEng Year 2 of UCSA-I1N1 Undergraduate Computer Science with Business Studies Year 2 of UCSA-G5N1 Undergraduate Computer and Management Sciences Year 2 of UCSA-G4G1 Undergraduate Discrete Mathematics Year 2 of UCSA-G4G3 Undergraduate Discrete Mathematics This module is Optional for: Year 2 of USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat) Year 2 of USTA-GG14 Undergraduate Mathematics and Statistics (BSc) This module is Core option list A for: Year 2 of UCSA-G5N1 Undergraduate Computer and Management Sciences This module is Option list B for: Year 2 of USTA-G300 Undergraduate Master of Mathematics,Operational Research,Statistics and Economics Year 2 of USTA-Y602 Undergraduate Mathematics,Operational Research,Statistics and Economics Further Information Term 2 15 CATS (7.5 ECTS) Online Material Additional Information Note: This module is only available to students in the second year of their degree and is not available as an unusual option to students in other years of study. Department of Computer Science, University of Warwick, CV4 7AL E-mail: comp-sci at dcs dot warwick dot ac dot uk, Telephone: +44 (0)24 7652 3193 DCS Intranet FacebookTwitterLinkedIn Page contact: Jackie Pinks Last revised: Wed 11 Aug 2021 Powered by Sitebuilder © MMXXI Terms Privacy Cookies Accessibility Coronavirus (Covid-19): Latest updates and information Let us know you agree to cookies We use cookies to give you the best online experience. Please let us know if you agree to functional, advertising and performance cookies. You can update your cookie preferences at any time. Cookie policy Essential cookies Functional cookies Advertising cookies Performance cookies Accept all Remember my preference More information
