2025 (Current Year) Faculty Courses School of Computing Undergraduate major in Computer Science
Automata and Formal Languages
- Academic unit or major
- Undergraduate major in Computer Science
- Instructor(s)
- Koichi Shinoda
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 5-6 Tue / 5-6 Fri
- Class
- -
- Course Code
- CSC.T251
- Number of credits
- 200
- Course offered
- 2025
- Offered quarter
- 2Q
- Syllabus updated
- Mar 19, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course covers fundamentals of programming/natural language processings, and focuses on phrase structure grammar, regular expression, finite automaton, pushdown automaton, and properties of formal languages.
The aim of this course is to understand fundamental theories of language processing by learning formal languages from the viewpoints of language generation and analysis methods.
Course description and aims
At the end of this course, students will be able to:
1) Have an understanding of definitions and properties of regular and context-free languages.
2) Have an understanding of regular and context-free grammars, and solve related problems such as conversion to normal form.
3) Have an understanding of deterministic/non-deterministic finite automata, and solve related problems such as generating an automaton for a given grammar.
4) Have an understanding of definition of pushdown automaton, and solve problems of related algorithms.
Keywords
phrase structure grammar, regular language, context-free language, regular grammar, context-free grammar, regular expression, finite automaton, pushdown automaton, pumping lemma
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
1) At the beginning of each class, the previous class is reviewed, and solutions to exercise problems are given.
2) Exercise problems of the day are given towards the end of class (around 30 min).
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | introduction, phrase structure grammar | formal language, phrase structure grammar, derivation of sentence |
| Class 2 | regular grammar | regular grammar, regular language, union/concatenation/Kleene-closure of regular languages, elimination of ε-production |
| Class 3 | finite automaton | formal definition of automaton, state transition diagram, deterministic finite automaton (DFA), nondeterministic finite automaton (NFA) |
| Class 4 | regular grammar and finite automaton | conversion from NFA to DFA, derivation of regular grammar from NFA |
| Class 5 | automaton with ε-transition | automaton with ε-transition, elimination of ε-transitions, NFA for union, complement, intersection, concatenation, and Kleene-closure |
| Class 6 | minimization of deterministic finite automaton | minimization algorithm of the number of DFA states, proof of minimality, proof of uniqueness |
| Class 7 | pumping lemma of regular language | pumping lemma of regular language, method to prove that a language is not regular |
| Class 8 | conversion from regular expression to automaton, conversion from automaton to regular expression | bottom-up method, top-down method, Kleene's method, method by solving recurrence equations |
| Class 9 | review of regular language and finite automaton | review of regular language and finite automaton |
| Class 10 | context-free grammar (CFG) | context-free grammar, context-free language, derivation tree, ambiguity, elimination of ε-productions |
| Class 11 | Chomsky normal form | Chomsky normal form (CNF), elimination of unit productions |
| Class 12 | pumping lemma of context-free language (CFL), Ogden's lemma | derivation tree for CNF, pumping lemma of context-free language, Ogden's lemma, method to prove that a given language is not CFL (by the pumping lemma and Ogden's lemma) |
| Class 13 | nondeterministic pushdown automaton (NPDA), deterministic pushdown automaton (DPDA) | nondeterministic pushdown automaton (formal definition, state-transition diagram, languages accepted), instantaneous description, deterministic pushdown automaton, deterministic context-free language (DCFL) |
| Class 14 | equivalency of context-free language and pushdown automaton | NPDA construction for given context-free grammar, languages accepted by empty stack, generation of context-free grammar for given NPDA |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
V. J. Rayward-Smith, A First Course in Formal Language Theory. Norwich UK: Blackwell Scientific Publishers. ISBN: 978-0077092450
Reference books, course materials, etc.
J. Hopcroft, R. Motowani, J. Ullman . Introduction to Automata Theory, Languages, and Computation. London: Pearson. ISBN: 978-1292039053
Evaluation methods and criteria
Students will be assessed on their understanding of this course, such as properties of formal languages, phrase structure grammar, and automata, and their ability to apply them to solve problems.
Students' course scores are based on exercise problems (40%), midterm exam (30%), and final exam (30%).
Related courses
- GRE.C101 ： Foundations of Computer Science I
- GRE.C102 ： Foundations of Computer Science II
- CSC.T241 ： Fundamentals of Computing
- CSC.T372 ： Compiler Construction
- ART.T459 ： Natural Language Processing
Prerequisites
No prerequisites.
Other
Course handouts will be uploaded to T2SCHOLA.