Course Name:Formal Language and Automata

Course Code: S2293123

Semester: 3

Credit: 3

Program: Computer science

Course Module: Specialized Compulsory

Responsible:Marc Gaetano

E-mail: gaetano@polytech.unice.fr

Department:Polytech Nice-Sophia,France

Time Allocation(1 credit hour = 45 minutes)

Course Description

The course is a required course designed for Engineering Master of Computer Science in TIEI. Formal language and automaton reveals the essence of computing from the perspective of language processing. The main contents of this course include formal language, computational model and the relationship between them. The course aims to develop students’ knowledge of computer theory literacy, improve their ability of logical thinking and problem solving.

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.

Course Syllabus

• 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