Аноним

Категория:Теория автоматов: различия между версиями

Материал из WikiGrapp

Категория:Теория автоматов (посмотреть исходный код)

Версия от 13:44, 13 апреля 2009

602 байта убрано ,  13 апреля 2009
нет описания правки
Нет описания правки
 
Нет описания правки
Строка 5: Строка 5:
При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют  число состояний автомата для работы по заданному [[алгоритм | алгоритму]]. Такой автомат называют [[абстрактный автомат|абстрактным]].  
При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют  число состояний автомата для работы по заданному [[алгоритм | алгоритму]]. Такой автомат называют [[абстрактный автомат|абстрактным]].  
При синтезе  автоматов формируют систему из элементарных автоматов, эквивалентную заданному  [[абстрактный автомат|абстрактному автомату]]. Такой автомат называется [[структурный автомат|структурным]].
При синтезе  автоматов формируют систему из элементарных автоматов, эквивалентную заданному  [[абстрактный автомат|абстрактному автомату]]. Такой автомат называется [[структурный автомат|структурным]].
Слова входного языка можно представить символами множества <math>X={x_1,x_2,...x_n}</math>, который называют входным алфавитом, а слова выходного языка - символами множества <math>Y={y_1,y_2,...y_p}</math>, который называют выходным алфавитом.
Множество [[состояние|состояний]] автомата <math>\boldsymbol{S={s_1,s_2,...s_m}}</math> называют алфавитом [[состояние|состояний]].


Автоматы часто классифицируются через [[Формальный язык|формальные языки]], которые они могут распознавать.
Автоматы часто классифицируются через [[Формальный язык|формальные языки]], которые они могут распознавать.
Строка 14: Строка 10:
Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем.
Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем.


Есть несколько классов автоматов, например [[Конечный автомат|конечные автоматы]] (различают детерминированные и недетерминированные конечные автоматы), [[МП-автомат|МП-автоматы]], [[ЛО-автомат|ЛО-автоматы]], [[Клеточный автомат|клеточные автоматы]] (игра «жизнь»), [[Машина Тьюринга|машины Тьюринга]].
Есть несколько классов автоматов, например [[Конечный автомат|конечные автоматы]] (различают детерминированные и недетерминированные конечные автоматы), [[МП-автомат|МП-автоматы]], [[ЛО-автомат|ЛО-автоматы]], [[Клеточный автомат|клеточные автоматы]](игра «жизнь»), [[Машина Тьюринга|машины Тьюринга]].
Источник — http://pco.iis.nsk.su/grapp/index.php/Служебная:Сравнение_версий/1421