Теория автоматов
Поделись знанием:
<math>L= \{ w \in \Sigma^{\star}|\hat\delta(S_0,w)\in F\}</math>
Страшное известие о Бородинском сражении, о наших потерях убитыми и ранеными, а еще более страшное известие о потере Москвы были получены в Воронеже в половине сентября. Княжна Марья, узнав только из газет о ране брата и не имея о нем никаких определенных сведений, собралась ехать отыскивать князя Андрея, как слышал Николай (сам же он не видал ее).
Получив известие о Бородинском сражении и об оставлении Москвы, Ростов не то чтобы испытывал отчаяние, злобу или месть и тому подобные чувства, но ему вдруг все стало скучно, досадно в Воронеже, все как то совестно и неловко. Ему казались притворными все разговоры, которые он слышал; он не знал, как судить про все это, и чувствовал, что только в полку все ему опять станет ясно. Он торопился окончанием покупки лошадей и часто несправедливо приходил в горячность с своим слугой и вахмистром.
Несколько дней перед отъездом Ростова в соборе было назначено молебствие по случаю победы, одержанной русскими войсками, и Николай поехал к обедне. Он стал несколько позади губернатора и с служебной степенностью, размышляя о самых разнообразных предметах, выстоял службу. Когда молебствие кончилось, губернаторша подозвала его к себе.
– Ты видел княжну? – сказала она, головой указывая на даму в черном, стоявшую за клиросом.
Николай тотчас же узнал княжну Марью не столько по профилю ее, который виднелся из под шляпы, сколько по тому чувству осторожности, страха и жалости, которое тотчас же охватило его. Княжна Марья, очевидно погруженная в свои мысли, делала последние кресты перед выходом из церкви.
Николай с удивлением смотрел на ее лицо. Это было то же лицо, которое он видел прежде, то же было в нем общее выражение тонкой, внутренней, духовной работы; но теперь оно было совершенно иначе освещено. Трогательное выражение печали, мольбы и надежды было на нем. Как и прежде бывало с Николаем в ее присутствии, он, не дожидаясь совета губернаторши подойти к ней, не спрашивая себя, хорошо ли, прилично ли или нет будет его обращение к ней здесь, в церкви, подошел к ней и сказал, что он слышал о ее горе и всей душой соболезнует ему. Едва только она услыхала его голос, как вдруг яркий свет загорелся в ее лице, освещая в одно и то же время и печаль ее, и радость.
– Я одно хотел вам сказать, княжна, – сказал Ростов, – это то, что ежели бы князь Андрей Николаевич не был бы жив, то, как полковой командир, в газетах это сейчас было бы объявлено.
Княжна смотрела на него, не понимая его слов, но радуясь выражению сочувствующего страдания, которое было в его лице.
– И я столько примеров знаю, что рана осколком (в газетах сказано гранатой) бывает или смертельна сейчас же, или, напротив, очень легкая, – говорил Николай. – Надо надеяться на лучшее, и я уверен…
Княжна Марья перебила его.
– О, это было бы так ужа… – начала она и, не договорив от волнения, грациозным движением (как и все, что она делала при нем) наклонив голову и благодарно взглянув на него, пошла за теткой.
Вечером этого дня Николай никуда не поехал в гости и остался дома, с тем чтобы покончить некоторые счеты с продавцами лошадей. Когда он покончил дела, было уже поздно, чтобы ехать куда нибудь, но было еще рано, чтобы ложиться спать, и Николай долго один ходил взад и вперед по комнате, обдумывая свою жизнь, что с ним редко случалось.
Княжна Марья произвела на него приятное впечатление под Смоленском. То, что он встретил ее тогда в таких особенных условиях, и то, что именно на нее одно время его мать указывала ему как на богатую партию, сделали то, что он обратил на нее особенное внимание. В Воронеже, во время его посещения, впечатление это было не только приятное, но сильное. Николай был поражен той особенной, нравственной красотой, которую он в этот раз заметил в ней. Однако он собирался уезжать, и ему в голову не приходило пожалеть о том, что уезжая из Воронежа, он лишается случая видеть княжну. Но нынешняя встреча с княжной Марьей в церкви (Николай чувствовал это) засела ему глубже в сердце, чем он это предвидел, и глубже, чем он желал для своего спокойствия. Это бледное, тонкое, печальное лицо, этот лучистый взгляд, эти тихие, грациозные движения и главное – эта глубокая и нежная печаль, выражавшаяся во всех чертах ее, тревожили его и требовали его участия. В мужчинах Ростов терпеть не мог видеть выражение высшей, духовной жизни (оттого он не любил князя Андрея), он презрительно называл это философией, мечтательностью; но в княжне Марье, именно в этой печали, выказывавшей всю глубину этого чуждого для Николая духовного мира, он чувствовал неотразимую привлекательность.
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.
Терминология
Символ — любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ — это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.
- Слово — строка символов, создаваемая через конкатенацию (соединение).
- Алфавит — конечный набор различных символов (множество символов)
- Язык — множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.
- Автоматы
Автоматы могут быть детерминированные и недетерминированные.
- Детерминированный конечный автомат (ДКА) — последовательность (кортеж) из пяти элементов <math>(Q, \Sigma, \delta, S_0, F)</math>, где:
- <math>Q</math> — множество состояний автомата
- <math>\Sigma</math> — алфавит языка, который понимает автомат
- <math>\delta</math> — функция перехода, такая что <math>\delta : Q \times \Sigma \rightarrow Q</math>
- <math>S_0 \in Q </math> — начальное состояние
- <math>F \subseteq Q </math> — множество конечных состояний.
- Недетерминированный конечный автомат (НКА) — последовательность (кортеж) из пяти элементов <math>(Q, \Sigma, \Delta, S, F)</math>, где:
- <math>Q</math> — множество состояний автомата
- <math>\Sigma</math> — алфавит языка, который понимает автомат
- <math>\Delta</math> — отношение перехода, <math>\Delta=\{<q,a,p>: q,p \in Q, a \in \Sigma \cup \{e\}\}</math>, где <math>\{e\}</math> - пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)
- <math>S \subseteq Q </math> — множество начальных состояний
- <math>F \subseteq Q </math> — множество конечных состояний.
- Слово
- Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом.Набор всех слов записывается как Σ*.
- Принимаемое слово
- Слово w ∈ Σ* принимается автоматом, если qn ∈ F.
Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита <math>\Sigma</math> таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:
Обычно автомат переходит из состояния в состояние с помощью функции перехода <math>\delta</math>, читая при этом один символ из ввода. Есть автоматы, которые могут перейти в новое состояние без чтения символа. Функция перехода без чтения символа называется <math>\epsilon</math>-переход (эпсилон-переход).
Применение
Теория автоматов лежит в основе всех цифровых технологий и программного обеспечения, так например компьютер является частным случаем практической реализации конечного автомата.
Часть математического аппарата теории автоматов напрямую применяется при разработке лексеров и парсеров для формальных языков, в том числе языков программирования, а также при построении компиляторов и разработке самих языков программирования.
Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.
Типовые задачи
- Построение и минимизация автоматов — построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
- Синтез автоматов — построение системы из заданных «элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется структурным. Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.
См. также
- Лемма о накачке
- Абстрактный автомат
- Игра «Жизнь»
- Минимальная форма автомата
- Теорема Шеннона — Лупанова
- Муравей Лэнгтона
Напишите отзыв о статье "Теория автоматов"
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: Вильямс, 2002. — С. 528. — ISBN 0-201-44124-1.
- Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. — C. 112.
Ссылки
- [teorya.hut.ru/ Применение теории автоматов]
Отрывок, характеризующий Теория автоматов
Страшное известие о Бородинском сражении, о наших потерях убитыми и ранеными, а еще более страшное известие о потере Москвы были получены в Воронеже в половине сентября. Княжна Марья, узнав только из газет о ране брата и не имея о нем никаких определенных сведений, собралась ехать отыскивать князя Андрея, как слышал Николай (сам же он не видал ее).
Получив известие о Бородинском сражении и об оставлении Москвы, Ростов не то чтобы испытывал отчаяние, злобу или месть и тому подобные чувства, но ему вдруг все стало скучно, досадно в Воронеже, все как то совестно и неловко. Ему казались притворными все разговоры, которые он слышал; он не знал, как судить про все это, и чувствовал, что только в полку все ему опять станет ясно. Он торопился окончанием покупки лошадей и часто несправедливо приходил в горячность с своим слугой и вахмистром.
Несколько дней перед отъездом Ростова в соборе было назначено молебствие по случаю победы, одержанной русскими войсками, и Николай поехал к обедне. Он стал несколько позади губернатора и с служебной степенностью, размышляя о самых разнообразных предметах, выстоял службу. Когда молебствие кончилось, губернаторша подозвала его к себе.
– Ты видел княжну? – сказала она, головой указывая на даму в черном, стоявшую за клиросом.
Николай тотчас же узнал княжну Марью не столько по профилю ее, который виднелся из под шляпы, сколько по тому чувству осторожности, страха и жалости, которое тотчас же охватило его. Княжна Марья, очевидно погруженная в свои мысли, делала последние кресты перед выходом из церкви.
Николай с удивлением смотрел на ее лицо. Это было то же лицо, которое он видел прежде, то же было в нем общее выражение тонкой, внутренней, духовной работы; но теперь оно было совершенно иначе освещено. Трогательное выражение печали, мольбы и надежды было на нем. Как и прежде бывало с Николаем в ее присутствии, он, не дожидаясь совета губернаторши подойти к ней, не спрашивая себя, хорошо ли, прилично ли или нет будет его обращение к ней здесь, в церкви, подошел к ней и сказал, что он слышал о ее горе и всей душой соболезнует ему. Едва только она услыхала его голос, как вдруг яркий свет загорелся в ее лице, освещая в одно и то же время и печаль ее, и радость.
– Я одно хотел вам сказать, княжна, – сказал Ростов, – это то, что ежели бы князь Андрей Николаевич не был бы жив, то, как полковой командир, в газетах это сейчас было бы объявлено.
Княжна смотрела на него, не понимая его слов, но радуясь выражению сочувствующего страдания, которое было в его лице.
– И я столько примеров знаю, что рана осколком (в газетах сказано гранатой) бывает или смертельна сейчас же, или, напротив, очень легкая, – говорил Николай. – Надо надеяться на лучшее, и я уверен…
Княжна Марья перебила его.
– О, это было бы так ужа… – начала она и, не договорив от волнения, грациозным движением (как и все, что она делала при нем) наклонив голову и благодарно взглянув на него, пошла за теткой.
Вечером этого дня Николай никуда не поехал в гости и остался дома, с тем чтобы покончить некоторые счеты с продавцами лошадей. Когда он покончил дела, было уже поздно, чтобы ехать куда нибудь, но было еще рано, чтобы ложиться спать, и Николай долго один ходил взад и вперед по комнате, обдумывая свою жизнь, что с ним редко случалось.
Княжна Марья произвела на него приятное впечатление под Смоленском. То, что он встретил ее тогда в таких особенных условиях, и то, что именно на нее одно время его мать указывала ему как на богатую партию, сделали то, что он обратил на нее особенное внимание. В Воронеже, во время его посещения, впечатление это было не только приятное, но сильное. Николай был поражен той особенной, нравственной красотой, которую он в этот раз заметил в ней. Однако он собирался уезжать, и ему в голову не приходило пожалеть о том, что уезжая из Воронежа, он лишается случая видеть княжну. Но нынешняя встреча с княжной Марьей в церкви (Николай чувствовал это) засела ему глубже в сердце, чем он это предвидел, и глубже, чем он желал для своего спокойствия. Это бледное, тонкое, печальное лицо, этот лучистый взгляд, эти тихие, грациозные движения и главное – эта глубокая и нежная печаль, выражавшаяся во всех чертах ее, тревожили его и требовали его участия. В мужчинах Ростов терпеть не мог видеть выражение высшей, духовной жизни (оттого он не любил князя Андрея), он презрительно называл это философией, мечтательностью; но в княжне Марье, именно в этой печали, выказывавшей всю глубину этого чуждого для Николая духовного мира, он чувствовал неотразимую привлекательность.
