Semester: 1

Credit:3

Program: Computer Science

Course Module: Specialized Compulsory

Responsible: Marc Gaetano

E-mail: marc.gaetano@gmail.com

Department: School of Computer Science & Technology, Tianjin University

Time Allocation (1 credit hour = 45 minutes)

32

16

Prerequisite

Ÿ Theory of computation basic: basic knowledge of the algorithm, computational complexity, automaton theory, computability theory, the form language theory.

Ÿ Discrete Mathematics:basic knowledge of logic, abstract algebra, computing model.

Ÿ Data structure : have a basic knowledge of the logical structure and physical structure of the data.

Ÿ program design: the ability to write programs independently.

Course Objectives

The course introduces four language forms (phrase language structure, context related to language, context free language, regular language) and four kinds of automata (finite automata, pushdown automata, Turing machine, linear have bounded automata), discusses the formal language and automata main theoretical results and application examples. After this course, students should:

Ÿ Master regular language,

Ÿ Master context free language,

Ÿ Master identification model,and to

Ÿ Grasp the basic knowledge of the Turing machine.

CourseSyllabus

Ÿ Preparatory knowledge: theorem proving methods, collection and basic operations, graphs and tree profiles, alphabet, strings and languages,

Ÿ General theory of grammar: formal grammar and formal language,

Ÿ Finite automaton: Basic definition, non-formalization description, application, non-deterministic finite automata,

Ÿ Regular expression:the definition of regular expressions, equivalent transformation, application, relationship with the finite automaton,

Ÿ The nature of a formal language:the pumping lemma, the decision algorithm, the relationship with the finite automaton, minimization of finite automaton,

Ÿ Context free grammars: grammar analysis, simplification, model, application,

Ÿ Pushdown automata,

Ÿ Turing machine guide, and to

Ÿ Linear bounded automaton and context related grammars.

Textbooks & References

Ÿ John E. Hopcroft, Rajeev Motwani.Introduction to automata theory, languages, and computation(3rd ed). Pearson, 2006.

Ÿ Michael Sipser.Introduction to the Theory of Computation (3rd ed). Cengage Learning, 2012.

Ÿ Jürgen Dassow, Gheorghe Paun.Regulated rewriting in formal language theory (1st ed). Springer Publishing Company, 2012.

Ÿ Peter Linz.An Introduction to Formal Languages and Automata (5th ed). Jones & Bartlett Learning, 2011.

Capability Tasks

CT1: To understand basic concepts of formal language and computational model, and clear the connection between them.

CT2: To master regular language, context-free languages and calculation model, which be used in professional knowledge learning.

CS1: To master the basic theoretical knowledge, to understand the professional status and trends.

CS2:To master the core of formal language and related technical knowledge; and to get the initial capacity of using core knowledge and engineering technical knowledge for professional learning.

Achievements

Ÿ To understand concepts of formal language and automaton. - Level: N

Ÿ To master the method to solve computer problem. - Level: M

Ÿ To master the ability to understand and deal with the formal model. - Level: M

Students:Computer Science, Year 1

Assessment：

Exam

Assignment

Report

Term Paper

Presentation

Others

√

√

Language of assessment：English

Attendance： 0 % Homework: 20 %

Mid-term report/test： 40 % Final report/test： 40 %