Конечный автомат

Коне́чный автома́т — абстрактный автомат, число возможных внутренних состояний которого конечно.

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

<math>M = (V, Q, q_0, F, \delta) </math>,

где

• <math>V</math> — входной алфавит (конечное множество входных символов), из которого формируются входные слова, воспринимаемые конечным автоматом;
• <math>Q</math> — множество внутренних состояний;
• <math>q_0</math> — начальное состояние <math>(q_0 \in Q)</math>;
• <math>F</math> — множество заключительных, или конечных состояний <math>(F \subset Q)</math>;
• <math>\delta</math> — функция переходов, определенная как отображение <math>\delta\colon Q \times ( V \cup \{ \lambda \} ) \rightarrow Q</math>, такое, что <math>\delta(q,a) = \{ r\colon q \rightarrow_a r \}</math>, то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).

Принято полагать, что конечный автомат начинает работу в состоянии <math>q_0</math>, последовательно считывая по одному символу входного слова (цепочки входных символов). Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов.

Читая входную цепочку символов <math>x</math> и делая переходы из состояния в состояние, автомат после прочтения последнего символа входного слова окажется в некотором состоянии <math>q'</math>.

Если это состояние является заключительным, то говорят, что автомат допустил слово <math>x</math>.

Конечные автоматы широко используются на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспечения на основе моделей.

Другие способы описания

1. Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой размеченный ориентированный граф, вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а метки дуг — символы, по которым осуществляется переход из одного состояния в другое. Если переход из состояния q₁ в q₂ может быть осуществлен по одному из нескольких символов, то все они должны быть надписаны над дугой диаграммы.
2. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается состояние, в которое должен перейти автомат, если в данном состоянии он считал данный входной символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

• Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором нет дуг с меткой ε (предложение, не содержащее ни одного символа), и из любого состояния по любому символу возможен переход в точности в одно состояние.
• Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов может достигаться двумя способами: либо могут существовать переходы, помеченные пустой цепочкой ε, либо из одного состояния могут выходить несколько переходов, помеченных одним и тем же символом.

• 

  Детерминированный конечный автомат

• 

  Недетерминированный автомат с пустыми переходами

• Ошибка создания миниатюры: Файл не найден

  Недетерминированный автомат с переходами из одного состояния помеченными одним и тем же символом

Если рассмотреть случай, когда автомат задан следующим образом: <math>M = (V, Q, S, F, \delta)</math>, где <math>S</math> — множество начальных состояний автомата, такое, что <math>S \subseteq V</math>, то появляется третий признак недетерминированности — наличие нескольких начальных (стартовых) состояний у автомата <math>M</math>.

Теорема о детерминизации утверждает, что для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их языки совпадают). Однако поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

Автоматы и регулярные языки

Для конечного автомата можно определить язык (множество слов) в алфавите V, который он допускает — так называются слова, чтение которых переводит автомат из начального состояния в одно из заключительных состояний.

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

Специализированные языки программирования

• Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования, широко используется для программирования промышленных логических контроллеров (ПЛК).

В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.

Разработка моделей с использованием конечных автоматов

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

Что может «делать» конечный автомат и последовательностная машина?

Ответ дается в различных терминах в зависимости от того, является ли автомат (соответственно П-машина) автономным или нет. Автономный конечный автомат, начиная с некоторого такта, может лишь генерировать периодическую последовательность состояний х (соответственно П-машина — последовательность выходных символов y). Если эта последовательность состоит лишь из одного символа, то это означает, что за конечное число тактов автомат достигает равновесного состояния. Если же эта последовательность содержит несколько символов, это означает, что автомат последовательно проходит состояния, соответствующие этим символам, а затем работа автомата неограниченно долго периодически повторяется. Более того, какова бы ни была периодическая последовательность состояний конечной длины, всегда может быть построен автономный конечный автомат, который, начиная уже со второго такта, генерирует эту последовательность. Ничего иного, кроме периодического повторения одного и того же состояния или конечной последовательности состояний, автономный автомат «делать» не может. Однако в связи с тем, что последовательное выполнение заданного цикла операций типично для многих областей современной техники, динамические системы, которые в приемлемой идеализации можно рассматривать как автономный автомат, имеют широкое применение.

Классическим примером могут служить автоматы-куклы, выполнявшие сложные последовательности действий, например: пишущие на бумаге определенный текст, играющие На рояле заранее установленные пьесы т. д.

Современным примером служат многие станки-автоматы, автоматические линии и системы автоматического управления циклическими производствами. Если автомат не автономен, то есть состояние входа изменяется от такта к такту, то ответ на вопрос, что может «делать» и что не может «делать» конечный автомат, можно дать в разных терминах. Например, ответ можно сформулировать на языке представления событий. Действительно, неавтономный конечный автомат или последовательностная машина лишь преобразуют входные последовательности символов в последовательности состояний или выходных символов, и сказать, что может и что не может «делать» конечный автомат, значит выяснить, какие преобразования последовательностей возможны в конечном автомате, а какие невозможны. Но так как количество состояний (соответственно выходных символов) конечно, этот вопрос эквивалентен такому вопросу: при каких входных последовательностях возникает каждое из возможных состояний (или каждый из выходных символов). Этот последний вопрос в терминах, принятых в теории конечных автоматов, формулируется так: какие события могут и какие не могут быть представлены в конечном автомате каждым из возможных состояний (или каждым из выходных символов).

Ответ дается теоремами Клини. Этот ответ точный, так как теоремы Клини устанавливают необходимые и достаточные условия представимости последовательности событий в автомате, а именно: выделяются особые множества последовательностей входных символов — регулярные множества. Факт появления входной последовательности из такого множества называется соответствующим регулярным событием. Теоремы Клини устанавливают, что в конечном автомате могут быть представлены регулярные события и только они. Таким образом, на языке представления событий ответ на вопрос, что может «делать» конечный автомат, дается однозначно: конечный автомат может представлять только регулярные события. Ряд важных множеств входных последовательностей, с которыми часто приходится иметь дело на практике, заведомо регулярны. Так, например, заведомо регулярно множество, состоящее из любого конечного числа входных последовательностей конечной длины; множество любых периодических входных последовательностей; множество бесконечных последовательностей, которое содержит заданные конечные последовательности на протяжении нескольких последних тактов, и т. д.

В общем случае, если каким-либо произвольным способом задано бесконечное множество входных последовательностей, то остается открытым вопрос о том, регулярно ли это множество. Дело в том, что понятие регулярного множества вводится индуктивно, то есть устанавливается алгоритм построения любых регулярных множеств. Однако, не существует достаточно эффективного способа решения обратной задачи, то есть установления того, является ли каждое заданное множество регулярным.

Хотя теоремы Клини и отвечают на вопрос о том, что может делать конечный автомат, но отвечают они на этот вопрос неэффективно. Сделаны первые попытки построения иных языков, на которых ответ может быть дан эффективно. Эта проблема языка, играющая кардинальную роль в получении эффективного ответа на вопрос, что может и что не может «делать» конечный автомат, имеет решающее значение и для первых этапов синтеза автомата, то есть для ответа на второй из сформулированных выше вопросов. Если расширить класс динамических систем, которые мы определили терминами «конечный автомат» и «последовательностная машина», включением бесконечной памяти (моделью бесконечной памяти может быть, например, бесконечная лента для хранения символов или бесконечное число состояний), то для динамических систем этого более широкого класса (абстрактные системы этого класса называют машинами Тьюринга) ответ на вопрос «что они могут делать?» значительно проще — они могут реализовать любой наперед заданный алгоритм. При этом само понятие алгоритма трактуется в современной математике как реализация вычисления значений какой-либо рекурсивной функции. Столь однозначный и четкий ответ на вопрос «что может делать машина Тьюринга?» дает возможность положить понятие о машине Тьюринга в основу определения понятия алгоритма: алгоритмом называется любой процесс, который может быть осуществлен на конечном автомате, дополненном бесконечной памятью, то есть алгоритмически полных машинах, на машине Тьюринга, на машине Поста и др.

См. также

• Автомат Мили
• Автомат Мура
• JFLAP — кроссплатформенная программа симулятор (автоматов, машины Тьюринга, грамматик)
• Автоматное программирование
• Sequential Function Chart
• Компилятор
• Транслятор
• Сети Петри
• Секвенциальная логика (Последовательностная логика)
• Таблица принятия решений

Литература

• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — С. 460-587. — ISBN 5-7038-2886-4.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Дискретная математика. — 2-е изд. — Вильямс, 2002. — 528 с. — (Алгоритмы и методы. Искусство программирования).
• Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. [trpl7.ru/t-books/TRYAP_BOOK_Details.htm Теория и реализация языков программирования] — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
• Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109—188. — URL www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
• [robot-develop.org/archives/1440#more-1440 Применение конечных автоматов для решения задач автоматизации]

Ссылки

• Дехтярь М. И. [www.intuit.ru/department/ds/introsaa/ Введение в схемы, автоматы и алгоритмы]
• [sourceforge.net/projects/genfsm/ Open source генератор конечных автоматов на языках C++ и Java по XML файлам описания]
• [www.rsdn.ru/article/alg/nka.xml Недетерминированные конечные автоматы]
• Подзоров С. Ю. [www.nsu.ru/education/podzorov/Alg/Course.pdf Курс лекции по теории алгоритмов]

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Конечный автомат

Окончив свой второй стакан пунша, Наполеон пошел отдохнуть пред серьезным делом, которое, как ему казалось, предстояло ему назавтра.
Он так интересовался этим предстоящим ему делом, что не мог спать и, несмотря на усилившийся от вечерней сырости насморк, в три часа ночи, громко сморкаясь, вышел в большое отделение палатки. Он спросил о том, не ушли ли русские? Ему отвечали, что неприятельские огни всё на тех же местах. Он одобрительно кивнул головой.
Дежурный адъютант вошел в палатку.
– Eh bien, Rapp, croyez vous, que nous ferons do bonnes affaires aujourd'hui? [Ну, Рапп, как вы думаете: хороши ли будут нынче наши дела?] – обратился он к нему.
– Sans aucun doute, Sire, [Без всякого сомнения, государь,] – отвечал Рапп.
Наполеон посмотрел на него.
– Vous rappelez vous, Sire, ce que vous m'avez fait l'honneur de dire a Smolensk, – сказал Рапп, – le vin est tire, il faut le boire. [Вы помните ли, сударь, те слова, которые вы изволили сказать мне в Смоленске, вино откупорено, надо его пить.]
Наполеон нахмурился и долго молча сидел, опустив голову на руку.
– Cette pauvre armee, – сказал он вдруг, – elle a bien diminue depuis Smolensk. La fortune est une franche courtisane, Rapp; je le disais toujours, et je commence a l'eprouver. Mais la garde, Rapp, la garde est intacte? [Бедная армия! она очень уменьшилась от Смоленска. Фортуна настоящая распутница, Рапп. Я всегда это говорил и начинаю испытывать. Но гвардия, Рапп, гвардия цела?] – вопросительно сказал он.
– Oui, Sire, [Да, государь.] – отвечал Рапп.
Наполеон взял пастильку, положил ее в рот и посмотрел на часы. Спать ему не хотелось, до утра было еще далеко; а чтобы убить время, распоряжений никаких нельзя уже было делать, потому что все были сделаны и приводились теперь в исполнение.
– A t on distribue les biscuits et le riz aux regiments de la garde? [Роздали ли сухари и рис гвардейцам?] – строго спросил Наполеон.
– Oui, Sire. [Да, государь.]
– Mais le riz? [Но рис?]
Рапп отвечал, что он передал приказанья государя о рисе, но Наполеон недовольно покачал головой, как будто он не верил, чтобы приказание его было исполнено. Слуга вошел с пуншем. Наполеон велел подать другой стакан Раппу и молча отпивал глотки из своего.
– У меня нет ни вкуса, ни обоняния, – сказал он, принюхиваясь к стакану. – Этот насморк надоел мне. Они толкуют про медицину. Какая медицина, когда они не могут вылечить насморка? Корвизар дал мне эти пастильки, но они ничего не помогают. Что они могут лечить? Лечить нельзя. Notre corps est une machine a vivre. Il est organise pour cela, c'est sa nature; laissez y la vie a son aise, qu'elle s'y defende elle meme: elle fera plus que si vous la paralysiez en l'encombrant de remedes. Notre corps est comme une montre parfaite qui doit aller un certain temps; l'horloger n'a pas la faculte de l'ouvrir, il ne peut la manier qu'a tatons et les yeux bandes. Notre corps est une machine a vivre, voila tout. [Наше тело есть машина для жизни. Оно для этого устроено. Оставьте в нем жизнь в покое, пускай она сама защищается, она больше сделает одна, чем когда вы ей будете мешать лекарствами. Наше тело подобно часам, которые должны идти известное время; часовщик не может открыть их и только ощупью и с завязанными глазами может управлять ими. Наше тело есть машина для жизни. Вот и все.] – И как будто вступив на путь определений, definitions, которые любил Наполеон, он неожиданно сделал новое определение. – Вы знаете ли, Рапп, что такое военное искусство? – спросил он. – Искусство быть сильнее неприятеля в известный момент. Voila tout. [Вот и все.]
Рапп ничего не ответил.
– Demainnous allons avoir affaire a Koutouzoff! [Завтра мы будем иметь дело с Кутузовым!] – сказал Наполеон. – Посмотрим! Помните, в Браунау он командовал армией и ни разу в три недели не сел на лошадь, чтобы осмотреть укрепления. Посмотрим!
Он поглядел на часы. Было еще только четыре часа. Спать не хотелось, пунш был допит, и делать все таки было нечего. Он встал, прошелся взад и вперед, надел теплый сюртук и шляпу и вышел из палатки. Ночь была темная и сырая; чуть слышная сырость падала сверху. Костры не ярко горели вблизи, во французской гвардии, и далеко сквозь дым блестели по русской линии. Везде было тихо, и ясно слышались шорох и топот начавшегося уже движения французских войск для занятия позиции.
Наполеон прошелся перед палаткой, посмотрел на огни, прислушался к топоту и, проходя мимо высокого гвардейца в мохнатой шапке, стоявшего часовым у его палатки и, как черный столб, вытянувшегося при появлении императора, остановился против него.
– С которого года в службе? – спросил он с той привычной аффектацией грубой и ласковой воинственности, с которой он всегда обращался с солдатами. Солдат отвечал ему.
– Ah! un des vieux! [А! из стариков!] Получили рис в полк?
– Получили, ваше величество.
Наполеон кивнул головой и отошел от него.

В половине шестого Наполеон верхом ехал к деревне Шевардину.
Начинало светать, небо расчистило, только одна туча лежала на востоке. Покинутые костры догорали в слабом свете утра.
Вправо раздался густой одинокий пушечный выстрел, пронесся и замер среди общей тишины. Прошло несколько минут. Раздался второй, третий выстрел, заколебался воздух; четвертый, пятый раздались близко и торжественно где то справа.
Еще не отзвучали первые выстрелы, как раздались еще другие, еще и еще, сливаясь и перебивая один другой.
Наполеон подъехал со свитой к Шевардинскому редуту и слез с лошади. Игра началась.


Вернувшись от князя Андрея в Горки, Пьер, приказав берейтору приготовить лошадей и рано утром разбудить его, тотчас же заснул за перегородкой, в уголке, который Борис уступил ему.
Когда Пьер совсем очнулся на другое утро, в избе уже никого не было. Стекла дребезжали в маленьких окнах. Берейтор стоял, расталкивая его.
– Ваше сиятельство, ваше сиятельство, ваше сиятельство… – упорно, не глядя на Пьера и, видимо, потеряв надежду разбудить его, раскачивая его за плечо, приговаривал берейтор.
– Что? Началось? Пора? – заговорил Пьер, проснувшись.
– Изволите слышать пальбу, – сказал берейтор, отставной солдат, – уже все господа повышли, сами светлейшие давно проехали.
Пьер поспешно оделся и выбежал на крыльцо. На дворе было ясно, свежо, росисто и весело. Солнце, только что вырвавшись из за тучи, заслонявшей его, брызнуло до половины переломленными тучей лучами через крыши противоположной улицы, на покрытую росой пыль дороги, на стены домов, на окна забора и на лошадей Пьера, стоявших у избы. Гул пушек яснее слышался на дворе. По улице прорысил адъютант с казаком.
– Пора, граф, пора! – прокричал адъютант.
Приказав вести за собой лошадь, Пьер пошел по улице к кургану, с которого он вчера смотрел на поле сражения. На кургане этом была толпа военных, и слышался французский говор штабных, и виднелась седая голова Кутузова с его белой с красным околышем фуражкой и седым затылком, утонувшим в плечи. Кутузов смотрел в трубу вперед по большой дороге.
Войдя по ступенькам входа на курган, Пьер взглянул впереди себя и замер от восхищенья перед красотою зрелища. Это была та же панорама, которою он любовался вчера с этого кургана; но теперь вся эта местность была покрыта войсками и дымами выстрелов, и косые лучи яркого солнца, поднимавшегося сзади, левее Пьера, кидали на нее в чистом утреннем воздухе пронизывающий с золотым и розовым оттенком свет и темные, длинные тени. Дальние леса, заканчивающие панораму, точно высеченные из какого то драгоценного желто зеленого камня, виднелись своей изогнутой чертой вершин на горизонте, и между ними за Валуевым прорезывалась большая Смоленская дорога, вся покрытая войсками. Ближе блестели золотые поля и перелески. Везде – спереди, справа и слева – виднелись войска. Все это было оживленно, величественно и неожиданно; но то, что более всего поразило Пьера, – это был вид самого поля сражения, Бородина и лощины над Колочею по обеим сторонам ее.
Над Колочею, в Бородине и по обеим сторонам его, особенно влево, там, где в болотистых берегах Во йна впадает в Колочу, стоял тот туман, который тает, расплывается и просвечивает при выходе яркого солнца и волшебно окрашивает и очерчивает все виднеющееся сквозь него. К этому туману присоединялся дым выстрелов, и по этому туману и дыму везде блестели молнии утреннего света – то по воде, то по росе, то по штыкам войск, толпившихся по берегам и в Бородине. Сквозь туман этот виднелась белая церковь, кое где крыши изб Бородина, кое где сплошные массы солдат, кое где зеленые ящики, пушки. И все это двигалось или казалось движущимся, потому что туман и дым тянулись по всему этому пространству. Как в этой местности низов около Бородина, покрытых туманом, так и вне его, выше и особенно левее по всей линии, по лесам, по полям, в низах, на вершинах возвышений, зарождались беспрестанно сами собой, из ничего, пушечные, то одинокие, то гуртовые, то редкие, то частые клубы дымов, которые, распухая, разрастаясь, клубясь, сливаясь, виднелись по всему этому пространству.
Эти дымы выстрелов и, странно сказать, звуки их производили главную красоту зрелища.
Пуфф! – вдруг виднелся круглый, плотный, играющий лиловым, серым и молочно белым цветами дым, и бумм! – раздавался через секунду звук этого дыма.
«Пуф пуф» – поднимались два дыма, толкаясь и сливаясь; и «бум бум» – подтверждали звуки то, что видел глаз.
Пьер оглядывался на первый дым, который он оставил округлым плотным мячиком, и уже на месте его были шары дыма, тянущегося в сторону, и пуф… (с остановкой) пуф пуф – зарождались еще три, еще четыре, и на каждый, с теми же расстановками, бум… бум бум бум – отвечали красивые, твердые, верные звуки. Казалось то, что дымы эти бежали, то, что они стояли, и мимо них бежали леса, поля и блестящие штыки. С левой стороны, по полям и кустам, беспрестанно зарождались эти большие дымы с своими торжественными отголосками, и ближе еще, по низам и лесам, вспыхивали маленькие, не успевавшие округляться дымки ружей и точно так же давали свои маленькие отголоски. Трах та та тах – трещали ружья хотя и часто, но неправильно и бедно в сравнении с орудийными выстрелами.
Пьеру захотелось быть там, где были эти дымы, эти блестящие штыки и пушки, это движение, эти звуки. Он оглянулся на Кутузова и на его свиту, чтобы сверить свое впечатление с другими. Все точно так же, как и он, и, как ему казалось, с тем же чувством смотрели вперед, на поле сражения. На всех лицах светилась теперь та скрытая теплота (chaleur latente) чувства, которое Пьер замечал вчера и которое он понял совершенно после своего разговора с князем Андреем.
– Поезжай, голубчик, поезжай, Христос с тобой, – говорил Кутузов, не спуская глаз с поля сражения, генералу, стоявшему подле него.
Выслушав приказание, генерал этот прошел мимо Пьера, к сходу с кургана.
– К переправе! – холодно и строго сказал генерал в ответ на вопрос одного из штабных, куда он едет. «И я, и я», – подумал Пьер и пошел по направлению за генералом.
Генерал садился на лошадь, которую подал ему казак. Пьер подошел к своему берейтору, державшему лошадей. Спросив, которая посмирнее, Пьер взлез на лошадь, схватился за гриву, прижал каблуки вывернутых ног к животу лошади и, чувствуя, что очки его спадают и что он не в силах отвести рук от гривы и поводьев, поскакал за генералом, возбуждая улыбки штабных, с кургана смотревших на него.


Генерал, за которым скакал Пьер, спустившись под гору, круто повернул влево, и Пьер, потеряв его из вида, вскакал в ряды пехотных солдат, шедших впереди его. Он пытался выехать из них то вправо, то влево; но везде были солдаты, с одинаково озабоченными лицами, занятыми каким то невидным, но, очевидно, важным делом. Все с одинаково недовольно вопросительным взглядом смотрели на этого толстого человека в белой шляпе, неизвестно для чего топчущего их своею лошадью.
– Чего ездит посерёд батальона! – крикнул на него один. Другой толконул прикладом его лошадь, и Пьер, прижавшись к луке и едва удерживая шарахнувшуюся лошадь, выскакал вперед солдат, где было просторнее.
Впереди его был мост, а у моста, стреляя, стояли другие солдаты. Пьер подъехал к ним. Сам того не зная, Пьер заехал к мосту через Колочу, который был между Горками и Бородиным и который в первом действии сражения (заняв Бородино) атаковали французы. Пьер видел, что впереди его был мост и что с обеих сторон моста и на лугу, в тех рядах лежащего сена, которые он заметил вчера, в дыму что то делали солдаты; но, несмотря на неумолкающую стрельбу, происходившую в этом месте, он никак не думал, что тут то и было поле сражения. Он не слыхал звуков пуль, визжавших со всех сторон, и снарядов, перелетавших через него, не видал неприятеля, бывшего на той стороне реки, и долго не видал убитых и раненых, хотя многие падали недалеко от него. С улыбкой, не сходившей с его лица, он оглядывался вокруг себя.
– Что ездит этот перед линией? – опять крикнул на него кто то.
– Влево, вправо возьми, – кричали ему. Пьер взял вправо и неожиданно съехался с знакомым ему адъютантом генерала Раевского. Адъютант этот сердито взглянул на Пьера, очевидно, сбираясь тоже крикнуть на него, но, узнав его, кивнул ему головой.