Course Name: Finite State Machines

Course Code:S2293229

Semester: 5

Credit: 2

Program: Computer science

Course Module: Optional

Responsible: Jianrong Wang

E-mail: wjr@tju.edu.cn

Department: Tianjin International Engineering Institute

Time Allocation (1 credit hour = 45 minutes)

Course Description

The course is optional designed for Engineering Master of Computer Science in TIEI. The course covers the basic knowledge and operation principles of the finite state machine. Through equipment by which continuous sequence could be observed, students can better master the finite state machine’s operation principle, and solve problems encountered in electronic design automation, communication protocol design, language parsing and other engineering application. Students will have a preliminary and extensive understanding about Finite State Machines, which enables students to realize language parsing.

Prerequisite

• Use PLC independently

• Master basic knowledge of Formal Language and Automaton

Course Objectives

This course discusses basic concepts of Finite State Machines to help students deal with semantic problems. After this course, students should be able to:

• Master the basic knowledge of Finite State Machines, and to

• Master the operation principle of finite state machine, and could analyze language.

Course Syllabus

• Finite state machine overview: basic concepts

• Regular expressions: structure, features of regular language

• Context Free Grammars: structure, language, and properties

• Turing machine: form, undecidability

• State Machine Optimization: methods and techniques

Textbooks & References

• AlfredV.Aho, JeffreyD.Ullman, RaviSethi, MonicaS.Lam.Compilers: Principle, Techniques and Tools. China Machine Press, 2009.

• Tiziano Villa, Timothy Kam, Robert K. Brayton, Alberto Sangiovanni-Vincentelli.Synthesis of Finite State Machines: Logic Optimization. Springer, 1997.

• Frederic P Miller, Agnes F Vandome, John McBrewster.Finite-State Machine. Alphascript Publishing, 2010.

• Volnei A. Pedroni.Finite State Machines in Hardware: Theory and Design (with VHDL and SystemVerilog). MIT Press, 2014.

Capability Tasks

CT2: To master basic knowledge of finite state machine.

CT3: To grasp how to use finite state machine.

CT4: To design corresponding case according to different actual environment.

CS1: To master the basic theories of finite state machine, and understand the development status and trends of finite state machine.

CS2: To have great ability of analysis, and design corresponding case according to different actual environment.

Achievements

• To understand the development process of a state machine, and the basic concept of a finite state machine. - Level: A

• To design finite state machine. - Level: M

• To design corresponding case according to different requirement. - Level: M

Students: Computer science,Year 3