automaton

If we go back to the method by which we solved the domino problems in Chapter 7, we can obtain a formula for S by considering it as a "finite state language" defined by the following "automaton":

Вспоминая, как мы решали в гл. 7 задачи про домино, мы можем получить формулу для S, рассматривая множество слагаемых как „автоматный язык", определяемый следующим „конечным автоматом":

Graham, Ronald L.,Knuth, Donald E.,Patashnik, Oren / Concrete Mathematics: A Foundation for Computer ScienceГрэхем, Р.,Кнут, Д.,Паташник, О. / Конкретная математика. Основание информатики

Конкретная математика. Основание информатики

Грэхем, Р.,Кнут, Д.,Паташник, О.

© 1994, 1989 by Addison-Wesley Publishing Company, Inc.

© перевод, В. В. Походзей, А.В. Ходулёв, 1998

Concrete Mathematics: A Foundation for Computer Science

Graham, Ronald L.,Knuth, Donald E.,Patashnik, Oren

© 1989 by Addison-Wesley Publishing Company

The automaton is in state off after 0 pushes, so we must show that 0 is even.

После 0 нажатий автомат находится в состоянии "выкл", поэтому нам нужно показать, что 0 — четное число.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

She waited on him in the sharp, mechanical manner of an automaton, all but breaking the plates with the violence with which she set them down.

Тэза подавала ему, двигаясь точно автомат, и так стучала тарелками, что угрожала их все перебить.

Zola, Emile / Abbe Mouret's TransgressionЗоля, Эмиль / Проступок аббата Муре

Проступок аббата Муре

Золя, Эмиль

Abbe Mouret's Transgression

Zola, Emile

© BiblioBazaar, LLC

In fact, as you may have noticed, it doesn't really depend on the automaton being deterministic, and could just as well have been applied to an NFA or even an e-NFA.

Как вы, возможно, заметили, он на самом деле не зависит от того, детерминирован ли этот автомат, и точно так же применим и к НКА, и даже к е-НКА.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

A smart automaton would blend in .

Интеллектуальный автомат сольется с фоном.

Watts, Peter / BlindsightУоттс, Питер / Ложная слепота

Ложная слепота

Уоттс, Питер

© 2006 by Peter Watts

© Д.М.Смушкович, перевод, 2009

© ООО "Астрель-СПб", 2010

Blindsight

Watts, Peter

© 2006 by Peter Watts

In effect, it stays in its one state on any sequence of inputs, so the customer automaton has no effect on the operation of the overall system.

В итоге, какая бы последовательность действий ни была подана на вход, он остается в своем единственном состоянии. Поэтому на операции, совершаемые системой в целом, автомат клиента не влияет.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

We shall discover that adding nondeterminism does not let us define any language that cannot be defined by a deterministic finite automaton, but there can be substantial efficiency in describing an application using a nondeterministic automaton.

Мы выясним, что добавление недетерминизма не позволяет определять языки, которые нельзя было бы определить с помощью детерминированных конечных автоматов. Тем не менее, недетерминированные автоматы оказываются весьма эффективными в приложениях.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Perhaps the simplest nontrivial finite automaton is an on/off switch.

Простейшим нетривиальным конечным автоматом является переключатель "включено-выключено".

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

We can view the pushdown automaton informally as the device suggested in Fig. 6.1.

Магазинный автомат можно рассматривать неформально как устройство, представленное на рис. 6.1.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

A two-state automaton with states A and D

Автомат с двумя состояниями А и D

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

But her head still twitched like an automaton and with a face contorted with bitter grief she began, without a word, beating her breast with her fist.

Но та как автомат все дергалась своею головой и безмолвно, с искривленным от жгучего горя лицом, вдруг стала бить себя кулаком в грудь.

Dostoevsky, Fyodor / The brothers KaramazovДостоевский, Фёдор / Братья Карамазовы

Братья Карамазовы

Достоевский, Фёдор

© Издательство "Художественная литература", 1988

The brothers Karamazov

Dostoevsky, Fyodor

A finite automaton can be deterministic or nondeterministic, where "nondeterministic" means that more than one transition out of a state may be possible on the same input symbol.

Такой автомат может быть детерминированным или недетерминированным (недетерминированный автомат может иметь более одного перехода из состояния при одном и том же входном символе).

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey / Compilers: Principles, Techniques, and ToolsАхо, Альфред В.,Ульман, Джеффри,Сети, Рави / Компиляторы: принципы, технологии, инструменты

Компиляторы: принципы, технологии, инструменты

Ахо, Альфред В.,Ульман, Джеффри,Сети, Рави

© Addison-Wesley Publishing Company, Inc., 1985

© 2001

© Издательский дом "Вильямс", 2001

Compilers: Principles, Techniques, and Tools

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey

© 2001 by PEARSON EDUCATION NORTH ASIA LIMITED and PEOPLE'S POSTS & TELECOMMUNICATIONS PUBLISHING HOUSE

© 1986

Beneath the black clock on the wall his sunburned face turned from side to side like an automaton.

Поджарая фигура поворачивается под черными часами, как автомат.

Bulgakov, Michail / The White GuardБулгаков, Михаил / Белая гвардия

Белая гвардия

Булгаков, Михаил

© Мурманское книжное издательство, 1990

The White Guard

Bulgakov, Michail

© 1971 by McGraw-Hill Book Company

The term "deterministic" refers to the fact that on each input there is one and only one state to which the automaton can transition from its current state.

Термин "детерминированный" говорит о том, что для всякой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Our first step is to convert it to an automaton with regular expression labels.

Вначале преобразуем этот автомат в автомат с регулярными выражениями в качестве меток.

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computationХопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычислений

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley