## ECE 6514 Applications of Automata Theory to Digital Design

#### Fall 2014 textbook list

The Fall 2014 ECE textbook list is available online for students.

#### Current Prerequisites & Course Offering

For current prerequisites for a particular course, and to view course offerings for a particular semester, see the Virginia Tech Course Timetables.

### ECE 6514 Applications of Automata Theory to Digital Design (3C)

Applications of theory of finite automata, pushdown automata, and Turing machines to the design of digital machines. Emphasis will be on the computational capabilities of classes of finite and infinite automata and on the consequences for digital design. Theory of NP-completeness, description of NP complete problems in digital design, and the consequences for design processes.

What is the reason for this course?

This course covers fundamental mathematical models for digital components, which can be used in the design process. By understanding the computational limits of various computing structures, our students will be able to make informed decisions about the type of computing structure needed for a given application. Also, by understanding the fundamental nature of classes of computations, our students will be able to identify intrinsically difficult problems and know how to deal with them. Engineers will be prevented from pursuing lines of attack that are guaranteed to fail, and will instead direct attention toward more productive techniques.

Typically offered: Spring. Program Area: Computers.

Prerequisites: 3504; MATH 5454.

Why are these prerequisites or corequisites required?

Basic concepts of digital design, such as combinational logic design, Karnaugh maps, state tables, state assignment, state diagrams, asynchronous design, races, and hazards, as taught in 3504. Fundamentals of graph theory as taught in MATH 5454. This material provides examples of NP-complete problems.

### Department Syllabus Information:

Major Measurable Learning Objectives:
• Select an appropriate computing structure that will be able to solve a given problem.
• Identify problems that are inherently very difficult, thereby eliminating inappropriate solution methods.
• Analyze problems and select an appropriate computing structure for their solution.

Course Topics
Topic Percentage
1. Deterministic Finite Automata 10%
2. Nondeterministic Finite Automata 10%
3. Use of Regular Expressions in Machine Design 20%
4. Use of Mathematical Models in Machine Design 10%
5. Pushdown Automata 10%
6. Turing Machines 10%
7. Theory of NP Completeness 15%
8. Consequences of NP Completeness to Digital Design 15%