Automata Theory

Jeffrey D. Ullman, StanfordOnline

This course covers the theory of automata and languages. We begin with a study of finite automata and the languages they can define (the so-called "regular languages." Topics include deterministic and nondeterministic automata, regular expressions, and the equivalence of these language-defining mechanisms.

We begin with a study of finite automata and the languages they can define (the so-called "regular languages." Topics include deterministic and nondeterministic automata, regular expressions, and the equivalence of these language-defining mechanisms. We also look at closure properties of the regular languages, e.g., the fact that the union of two regular languages is also a regular language. We consider decision properties of regular languages, e.g., the fact that there is an algorithm to tell whether or not the language defined by two finite automata are the same language. Finally, we see the pumping lemma for regular languages -- a way of proving that certain languages are not regular languages.

Our second topic is context-free grammars and their languages. We learn about parse trees and follow a pattern similar to that for finite automata: closure properties, decision properties, and a pumping lemma for context-free languages. We also introduce the pushdown automaton, whose nondeterministic version is equivalent in language-defining power to context-free grammars.

Next, we introduce the Turing machine, a kind of automaton that can define all the languages that can reasonably be said to be definable by any sort of computing device (the so-called "recursively enumerable languages"). We shall learn how "problems" (mathematical questions) can be expressed as languages. That lets us define problems to be "decidable" if their language can be defined by a Turing machine and "undecidable" if not. We shall see some basic undecidable problems, for example, it is undecidable whether the intersection of two context-free languages is empty.

Last, we look at the theory of intractable problems. These are problems that, while they are decidable, have almost certainly no algorithm that runs in time less than some exponential function of the size of their input. We meet the NP-complete problems, a large class of intractable problems. This class includes many of the hard combinatorial problems that have been assumed for decades or even centuries to require exponential time, and we learn that either none or all of these problems have polynomial-time algorithms. A common example of an NP-complete problem is SAT, the question of whether a Boolean expression has a truth-assignment to its variables that makes the expression itself true.

What will you learn

  • Finite automata and regular expressions
  • Context-free grammars
  • Turing machines and decidability
  • The theory of intractability, or NP-complete problems

Сессии:
  • 30 марта 2020
Характеристики онлайн курса:
  • Бесплатный:
  • Платный:
  • Сертификат:
  • MOOC:
  • Видеолекции:
  • Аудиолекции:
  • Email-курс:
  • Язык: Английский Gb

Отзывы

Пока никто не написал отзыв по этому курсу. Хотите быть первым?

Зарегистрируйтесь, чтобы оставить отзыв

Show?id=n3eliycplgk&bids=695438
NVIDIA
Ещё курсы на эту тему:
Small-icon.hover Automata
This course covers finite automata, context-free grammars, Turing machines,...
Extensionflag Introduction to the Theory of Computation
This course is an introduction to the theory of computation, teaching...
18-404jf06 Theory of Computation
This graduate level course is more extensive and theoretical treatment of the...
6-045js11 Automata, Computability, and Complexity
This course provides a challenging introduction to some of the central ideas...
6-080s08 Great Ideas in Theoretical Computer Science
This course provides a challenging introduction to some of the central ideas...
Ещё из рубрики «Компьютерные науки»:
Mooc%20icon Investigative Journalism for the Digital Age
Learn from some of the best investigative journalism instructors in the United...
073d6494-9e83-4ffd-8f36-6e1d95ac4366-374f4f2f4a7c.small Statistical Thinking for Data Science and Analytics
Learn how statistics plays a central role in the data science approach. This...
B93c9fea-3df3-4180-984c-55310821cbb5-f8050e6a1cca.small Machine Learning for Data Science and Analytics
Learn the principles of machine learning and the importance of algorithms. Machine...
A58d02d2-ee6b-4903-8075-15d516b28254-a14c08150405.small Enabling Technologies for Data Science and Analytics: The Internet of Things
Discover the relationship between Big Data and the Internet of Things (IoT)...
Ef4d812a-d160-4f21-bf8d-48bbb8deadfa-d369cbea0566.small Introduction to Java Programming – Part 1
Learn the fundamental elements of Java programming and data abstraction. Do...
Ещё от edX:
20574fb6-99b9-44cf-afa5-473d8337c7a8-c1588ba86fbd.small AnatomyX: Musculoskeletal Cases
Learn the anatomy basic to understanding five musculoskeletal injuries commonly...
Ed8158ec-92c6-4483-8618-68e1518cf413-036c24d90c72.small Marketing Innovative Products and Services
Learn essential marketing concepts and practical commercialization strategies...
1f714d8d-83f0-47ef-841c-168e95f2c81a-9392c93e5e09.small Finance for Everyone: Smart Tools for Decision-Making
In this introduction to finance course from Michigan learn to apply frameworks...
073d6494-9e83-4ffd-8f36-6e1d95ac4366-374f4f2f4a7c.small Statistical Thinking for Data Science and Analytics
Learn how statistics plays a central role in the data science approach. This...
B93c9fea-3df3-4180-984c-55310821cbb5-f8050e6a1cca.small Machine Learning for Data Science and Analytics
Learn the principles of machine learning and the importance of algorithms. Machine...

© 2013-2019