Категория:Теория автоматов: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 5: | Строка 5: | ||
При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному [[алгоритм | алгоритму]]. Такой автомат называют [[абстрактный автомат|абстрактным]]. | При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному [[алгоритм | алгоритму]]. Такой автомат называют [[абстрактный автомат|абстрактным]]. | ||
При синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному [[абстрактный автомат|абстрактному автомату]]. Такой автомат называется [[структурный автомат|структурным]]. | При синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному [[абстрактный автомат|абстрактному автомату]]. Такой автомат называется [[структурный автомат|структурным]]. | ||
Автоматы часто классифицируются через [[Формальный язык|формальные языки]], которые они могут распознавать. | Автоматы часто классифицируются через [[Формальный язык|формальные языки]], которые они могут распознавать. | ||
| Строка 14: | Строка 10: | ||
Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем. | Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем. | ||
Есть несколько классов автоматов, например [[Конечный автомат|конечные автоматы]] (различают детерминированные и недетерминированные конечные автоматы), [[МП-автомат|МП-автоматы]], [[ЛО-автомат|ЛО-автоматы]], [[Клеточный автомат|клеточные автоматы]] (игра «жизнь»), [[Машина Тьюринга|машины Тьюринга]]. | Есть несколько классов автоматов, например [[Конечный автомат|конечные автоматы]] (различают детерминированные и недетерминированные конечные автоматы), [[МП-автомат|МП-автоматы]], [[ЛО-автомат|ЛО-автоматы]], [[Клеточный автомат|клеточные автоматы]](игра «жизнь»), [[Машина Тьюринга|машины Тьюринга]]. | ||
Версия от 20:44, 13 апреля 2009
В дискретной математике, разделе информатики, теория автоматов изучает абстрактные машины в виде математических моделей, и проблемы, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов. Это объясняется тем, что автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результирующую информацию по шагам заданного алгоритма. Эти преобразования возможны с помощью технических и/или программных средств. Автомат можно представить как некоторое устройство (чёрный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния.
При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному алгоритму. Такой автомат называют абстрактным. При синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному абстрактному автомату. Такой автомат называется структурным.
Автоматы часто классифицируются через формальные языки, которые они могут распознавать.
Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем.
Есть несколько классов автоматов, например конечные автоматы (различают детерминированные и недетерминированные конечные автоматы), МП-автоматы, ЛО-автоматы, клеточные автоматы(игра «жизнь»), машины Тьюринга.
Страницы в категории «Теория автоматов»
Показано 29 страниц из 29, находящихся в данной категории.