A, B, C и D

Автоматическими выключателями называются приборы, отвечающие за защиту электроцепи от повреждений, связанных с воздействием на нее тока большой величины. Слишком сильный поток электронов способен вывести из строя бытовую технику, а также вызвать перегрев кабеля с последующим оплавлением и возгоранием изоляции. Если вовремя не обесточить линию, это может привести к пожару, Поэтому, в соответствии с требованиями ПУЭ (Правила устройства электроустановок), эксплуатация сети, в которой не установлены электрические автоматы защиты, запрещена. АВ обладают несколькими параметрами, один из которых – время токовая характеристика автоматического защитного выключателя. В этой статье мы расскажем, чем различаются автоматические выключатели категории A, B, C, D и для защиты каких сетей они используются.

Особенности работы автоматов защиты сети

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

Токи, которые могут представлять опасность для сети, подразделяются на два вида:

• Токи перегрузки. Их появление чаще всего происходит из-за включения в сеть приборов, суммарная мощность которых превышает ту, что линия способна выдержать. Другая причина перегрузки – неисправность одного или нескольких устройств.
• Сверхтоки, вызванные КЗ. Короткое замыкание происходит при соединении между собой фазного и нейтрального проводников. В нормальном состоянии они подключены к нагрузке по отдельности.

Устройство и принцип работы автоматического выключателя – на видео:

Токи перегрузки

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

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

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

Этот элемент нагревается под воздействием мощного тока, становится пластичным, изгибается и вызывает срабатывание автомата.

Токи короткого замыкания

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

Однако существует один нюанс. Иногда ток перегрузки может также быть очень большим, но при этом не вызванным КЗ. Как же аппарат должен определить различие между ними?

На видео про селективность автоматических выключателей:

Здесь мы плавно переходим к основному вопросу, которому посвящен наш материал. Существует, как мы уже говорили, несколько классов АВ, различающихся по времятоковой характеристике. Наиболее распространенными из них, которые применяются в бытовых электросетях, являются устройства классов B, C и D. Автоматические выключатели, относящиеся к категории A, встречаются значительно реже. Они наиболее чувствительны и используются для защиты высокоточных аппаратов.

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

Характеристики срабатывания защитных автоматических выключателей

Класс АВ, определяющийся этим параметром, обозначается латинским литером и проставляется на корпусной части автомата перед цифрой, соответствующей номинальному току.

В соответствии с классификацией, установленной ПУЭ, защитные автоматы подразделяются на несколько категорий.

Автоматы типа МА

Отличительная черта таких устройств – отсутствие в них теплового расцепителя. Аппараты этого класса устанавливают в цепях подключения электрических моторов и других мощных агрегатов.

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

Приборы класса А

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

Катушка электромагнитного расцепления обесточивает сеть в течение примерно 0,05 сек, если электроток в цепи превышает номинальный на 100%. Если по какой-либо причине после увеличения силы потока электронов в два раза электромагнитный соленоид не сработал, биметаллический расцепитель отключает питание в течение 20 – 30 сек.

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

Защитные устройства класса B

Аппараты категории B обладают меньшей чувствительностью, чем относящиеся к типу A. Электромагнитный расцепитель в них срабатывает при превышении номинального тока на 200%, а время на срабатывание составляет 0,015 сек. Срабатывание биметаллической пластины в размыкателе с характеристикой B при аналогичном превышении номинала АВ занимает 4-5 сек.

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

Автоматы категории C

Устройства типа C наиболее распространены в бытовых сетях. Их перегрузочная способность еще выше, чем у ранее описанных. Для того, чтобы произошло срабатывание соленоида электромагнитного расцепления, установленного в таком приборе, нужно, чтобы проходящий через него поток электронов превысил номинальную величину в 5 раз. Срабатывание теплового расцепителя при пятикратном превышении номинала аппарата защиты происходит через 1,5 сек.

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

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

Автоматические выключатели категории Д

Эти устройства имеют наиболее высокую перегрузочную способность. Для срабатывания электромагнитной катушки, установленной в аппарате такого типа, нужно, чтобы номинал по электротоку защитного автомата был превышен как минимум в 10 раз.

Срабатывание теплового расцепителя в этом случае происходит через 0,4 сек.

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

Защитные устройства категории K и Z

Автоматы этих типов распространены гораздо меньше, чем те, о которых было рассказано выше. Приборы типа K имеют большой разброс в величинах тока, необходимых для электромагнитного расцепления. Так, для цепи переменного тока этот показатель должен превышать номинальный в 12 раз, а для постоянного – в 18. Срабатывание электромагнитного соленоида происходит не более чем через 0,02 сек. Срабатывание теплового расцепителя в таком оборудовании может произойти при превышении величины номинального тока всего на 5%.

Этими особенностями обусловлено применение устройств типа K в цепях с исключительно индуктивной нагрузкой.

Приборы типа Z тоже имеют разные токи срабатывания соленоида электромагнитного расцепления, но разброс при этом не столь велик, как в АВ категории K. В цепях переменного тока для их отключения превышение токового номинала должно быть трехкратным, а в сетях постоянного – величина электротока должна быть в 4,5 раза больше номинальной.

Аппараты с характеристикой Z используются только в линиях, к которым подключены электронные устройства.

Наглядно про категории автоматов на видео:

Заключение

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

Автоматические выключатели и их характеристики B, C, D

Основными характеристиками автоматических выключателей являются

Номинальный ток (In):

ток, который может протекать через автомат, без его срабатывания. 

Номинальное рабочее напряжение (Ue)

номинальное, на которое рассчитана изоляция автомата 

Номинальное напряжение изоляции (Ui)

Это величина напряжения, относительно которого выбирается напряжение при испытании электрической прочности изоляции, которое обычно превышает 2 Ui, и определяется длина пути тока утечки через изолятор.

Номинальное выдерживаемое импульсное напряжение (Uimp)

Параметр представляет собой величину импульса напряжения (определенной формы и полярности) в кВ, который рассматриваемое оборудование может выдержать в условиях испытаний без повреждения.

Обычно для промышленных автоматических выключателей Uimp = 8 кВ, для бытовых автоматических выключателей Uimp = 6 кВ.

Отключающая способность:

ток (в кА), срабатывания автомата при коротком замыкании, после которого он еще будет работоспособен. 

Характеристика автоматов В, С, D:

зависимость времени отключения от тока. 

Буквы B, C и D обозначают характеристику автоматов, которая называется «тип мгновенного расцепления» и установлена в ГОСТ Р 50345-99] (МЭК 60898-95) «Аппаратура малогабаритная электрическая. автоматические выключатели для защиты от сверхтоков бытового и аналогичного назначения».

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

В ГОСТ Р 50345 для каждого типа мгновенного расцепления установлены следующие стандартные диапазоны токов:

тип В: 3In — 5In;

тип С: 5 In -10 In

тип D:10 In — 20 In

Стандартная времятоковая зона предписывает следующее поведение автоматического выключателя:

В случае если в главной цепи выключателя протекает электрический ток, величина которого соответствует нижней границе диапазона токов мгновенного расцепления 3In, 5In и 10 In, то он должен расцепиться за промежуток времени:

тип мгновенного расцепления B — более 0,1 с, но менее 45 или 90 с,

тип C — 15 или 30с

тип D — 4 или 8с.

При протекании в главной цепи электрического тока, равного верхней границе диапазона токов мгновенного расцепления (5In, 10In и 50In), автоматический выключатель должен расцепиться за промежуток времени менее 0,1 с.

В том случае, если значение электрического тока, протекающего в главной цепи, находится между нижней и верхней границами диапазона токов мгновенного расцепления, автоматический выключатель может расцепиться либо с незначительной выдержкой времени (несколько секунд), либо без выдержки времени (менее 0,1 с).

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

Исходя из вышенаписанного автоматы предназначены:

типа В — для защиты потребителей с преимущественно активной нагрузкой (печь, обогреватель, ЛН),

типа С — двигателей,

типа D — двигателей в повторно-кратковременном (частые пуски) режиме работы. 

A, B, C, D, K и Z

На сегодняшний день автоматические выключатели стали незаменимым частью электрической цепи как на производстве, так и в быту. Все автоматические выключатели обладают множеством параметров, один из которых – время токовая характеристика. В данной статьи мы рассмотрим, чем отличаются автоматы с время токовой характеристиками категории A, B, C, D и где данные выключатели применяются.

Работа автоматического выключателя

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

 В сети бывают 2 вида опасных для сети токов:

Сверхтоки вызванный КЗ. Причиной возникновения короткого замыкания является замыкание нейтрального и фазного проводника между собой. В обычном состоянии фазный и нейтральный провод подключены к нагрузке отдельно друг от друга.

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

 Токи перегрузки

Токи перегрузки зачастую бывают немного больше номинального значения тока автомата, поэтому токи перегрузки как правило не вызывают повреждение цепи в случае недолговременной продолжительности действия. Следовательно, нам не нужно мгновенно отключать сеть в данном случае (зачастую величина тока быстро приходит в норму). В каждом автоматическом выключателе предусмотрено определенное превышение силы тока, которое приводит к срабатыванию автомата.

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

Токи КЗ

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

Здесь мы плавно переходим к основному вопросу, которому посвящен наш материал. Существует, как мы уже говорили, несколько классов АВ, различающихся по времятоковой характеристике. Наиболее распространенными из них, которые применяются в бытовых электросетях, являются устройства классов B, C и D. Автоматические выключатели, относящиеся к категории A, встречаются значительно реже. Они наиболее чувствительны и используются для защиты высокоточных аппаратов.

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

 Автоматы типа МА

Главная особенность подобных устройств – отсутствие в них теплового расцепителя. Обычно подобные устройства ставят для защиты электрических моторов и прочих мощных устройств.

Устройства класса А

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

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

Защитные устройства класса B

Все устройства категории В имеют меньшую чувствительность, в сравнении с устройствами категории А. Срабатывание электромагнитного расцепителя в них происходит при превышении номинала автомата на 200%. При этом время срабатывания данных устройств составляет 0,015 сек.

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

Устройства категории С

Устройства типа С весьма распространены в бытовых сетях. Устойчивость к перегрузкам у данных устройств выше, нежели у всех вышеперечисленных. Чтобы произошло срабатывание соленоида электромагнитного расцепителя, требуется превышение проходящего через расцепитель тока в 5 раз выше номинального значения. Тепловой расцепитель срабатывает в случае превышения номинала в 5 раз через 1,5 сек.

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

Вы можете купить автоматические выключатели категории С от лучших производителей:

Автоматы CHINT

Автоматы IEK

Автоматические выключатели категории D

Выключатели категории D имеют наиболее высокую перегрузочную способность. Электромагнитная катушка в устройстве срабатывает при превышении номинала автомата, как минимум в 10 раз.

Тепловой расцепитель срабатывает через 0,4 сек.

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

Вы можете купить автоматические выключатели категории D здесь:

Автоматы CHINT

Автоматы IEK

 Защитные устройства категории K и Z

Автоматы категории K и Z встречаются довольно редко. Устройства категории К имеют большой разброс в значениях тока, требуемых для электромагнитного расцепителя. К примеру, для цепи переменного тока данный показатель должен превышать номинал в 12 раз, а в случае применения в цепи постоянного тока, в 18 раз. Электромагнитный соленоид срабатывает через 0,02 сек. Тепловой расцепитель может сработать при превышении номинала всего на 5%.

Из-за своих свойств устройства категории К применяются в цепях с исключительно индуктивной нагрузкой.

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

Характеристики срабатывания автоматов. Принцип выбора

Автоматические выключатели: характеристики срабатывания и ситуации применения

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

Для размыкания электрической цепи автоматические выключатели оборудованы специальными устройствами – расцепителями. 

В современных модульных автоматах используется два типа расцепителей: 

1) Тепловой – служит для защиты от перегрузки

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

Нормируемые параметры – следующие:

• 1,13 (In) –  тепловой расцепитель не срабатывает в течение 1 ч.
• 1,45 (In) – расцепитель срабатывает в течение < 1 ч.

2) Электромагнитный (отсечка) – предназначен для защиты от короткого замыкания

Соленоид с подвижным сердечником, который втягивается при превышении заданного порога тока, мгновенно размыкая электрическую цепь. Отсечка срабатывает при существенном превышении номинального тока (2÷10 In) в зависимости от характеристики срабатывания. Рассмотрим наиболее распространенные автоматы с характеристиками: (B, C, D, K, Z).

1) Характеристика В (3-5 In)

Электромагнитный расцепитель срабатывает при токе, превышающем номинальный в 5 раз. Время отключения <1с. При токе, превышающим номинальный в 3 раза, в течение 4-5 с. сработает тепловой расцепитель. (Обращаем ваше внимание, что для постоянного тока (DC) граница срабатывания будет немного сдвинута (х1,5). 

Автоматические выключатели «В» применяются в осветительных сетях с небольшими пусковыми токами (или полным их отсутствием). 

2) Характеристика С (5-10 In)

Наиболее распространённые автоматические выключатели. Минимальный ток срабатывания составляет 5 In. При этом значении через 1,5 с сработает тепловой расцепитель, а при 10 кратном превышении номинала, электромагнитный разомкнет цепь меньше, чем за 0,1 с.

Автоматические выключатели «С» подходят для сетей со смешанной нагрузкой (освещение, бытовые электроприборы)

3) Характеристика D (10-20 In)

Характеризуются большой устойчивостью к перегрузке. Тепловой расцепитель разомкнет цепь за 0,4 при превышении порога в 10 In. Срабатывание соленоида произойдет при двадцатикратном превышении номинального тока.

Автоматические выключатели «D» используются для подключения электродвигателей с кратковременными большими токами (пусковые токи)

4) Характеристика K (8-15 In)

Для автоматов этой категории характерна большая разница в показателях для постоянного и переменного токов. Например, электромагнитный расцепитель гарантировано разомкнет цепь за 0,02 с. при достижении значения в 12 In в цепи переменного тока, а для постоянного это значения увеличивается до 18 In. При превышении номинального тока в 1,5 раза в течение 2 мин. сработает тепловой расцепитель.

Автоматы с характеристикой «K» применяются для подключения преимущественно индуктивной нагрузки.

5) Характеристика Z (2-3 In)

Автоматы этой категории также имеют различия в параметрах срабатывания для переменного и постоянного токов.

Электромагнитный расцепитель разомкнет цепь при трёхкратном превышении номинальных параметров в цепи переменного тока и 4,5 In в цепях постоянного тока. Тепловой расцепитель сработает при токе в 1,2 от номинального в течение часа.

Вследствие небольших значений по превышению номинальных параметров, Автоматы «Z» применяются только для защиты высокочувствительной электронной аппаратуры.

Подытоживая вышесказанное отметим, что для бытового использования подходят автоматы с характеристиками: «В» и «С», при возможном подключении электродвигателей с высокими пусковыми токами имеет смысл использовать автоматы категории «Е» (во избежание ложного срабатывания). Категория «К» подходит при работе с индуктивными нагрузками, а «Z» для электронного оборудования, чувствительного к небольшим перегрузкам. 

И последнее: если вы сомневаетесь в правильности выбора — обратитесь к профессиональному электрику, не гадайте!

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

Чтобы узнать подробности и заказать электротехническую продукцию звоните по телефону 

(495) 777-05-30 

Или оставьте сообщение через форму обратной связи в разделе «Контакты». 

Технические характеристики автоматических выключателей типа B, C, D, выбор в зависимости от вида нагрузки

электрика, сигнализация, видеонаблюдение, контроль доступа (СКУД) и другие инженерно технические системы (ИТС)

Автоматический защитный выключатель (АВ) относится к наиболее часто используемым аппаратам коммутации и защиты в сетях 0,4 кВ. Защитные функции автоматов построены на срабатывании расцепителей двух видов:

• электромагнитного;
• теплового.

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

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

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

Основные принципы автоматической защиты электрических цепей и электрооборудования заключаются в следующем.

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

Элементы автоматической защиты АВ не обладают возможностью гибкой настройки параметров срабатывания, как УРЗА. Поэтому для обеспечения защиты нагрузки различного свойства применяют автоматические выключатели, имеющие разную зависимость времени срабатывания от токовой величины. Эта зависимость называется время – токовой характеристикой (ВТХ) автоматического выключателя.

В соответствии с ГОСТ Р 50345 – 2010 время – токовые характеристики автоматов делятся на три типа – B, C, D. Наиболее наглядно сравнительные характеристики автоматов защиты демонстрируют графики ВТХ. По горизонтальной оси графиков отложены значения кратности тока, то есть, отношение фактического тока к номиналу автомата, по вертикальной – время отключения.

ГОСТ регламентирует порядок проведения испытаний по проверке время – токовых характеристик защитного автомата. Проверка отключающей характеристики осуществляется на пяти значениях испытательного тока.

Первые три применяемые в ходе испытаний токовые значения предназначены для проверки срабатывания тепловых расцепителей. Одно из них является величиной нерасцепления, два других – токами расцепления. Два последних испытания проводятся для проверки отключающей способности мгновенного электромагнитного расцепителя.

ИСПЫТАНИЯ ТЕПЛОВЫХ РАСЦЕПИТЕЛЕЙ

Автоматические выключатели с характеристикой типа B, C, D.

I = 1,13*In.

При такой кратности испытываются технические характеристики срабатывания автоматических выключателей всех трёх типов – B, C и D. Токовая нагрузка одновременно пропускается через все полюса выключателя. Критерии отсутствия расцепления одинаковы для всех типов характеристик.

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

Для защитных автоматов номиналом более 63 ампер, срабатывания расцепителя не должно быть в течение двух часов. Начинается испытание при холодном состоянии автомата. Холодным принято считать температуру автомата 30°С.

I = 1,45*In.

В таком режиме также испытываются автоматические выключатели всех трёх видов. К этому испытанию переходят непосредственно после технической проверки током нерасцепления. Ток повышают плавно в течение 5 секунд до величины 1,45*In. Критерии срабатывания расцепителя также одинаковы для защитных коммутационных аппаратов всех технических характеристик.

Автоматические выключатели с номинальными значениями до 63 ампер включительно должны отключиться в течение времени менее одного часа, аппараты номиналом более 63 А – менее чем за 2 часа.

I = 2,55*In.

Данное испытание характеристики расцепителя воздушного выключателя начинают с холодного состояния. Нагрузка должна проходить по всем трём полюсам АВ. Технические критерии расцепления следующие. Отключение защитного коммутационного аппарата с номиналом до 32 ампер включительно происходит более чем за секунду и менее чем за 60 секунд.

Время срабатывания защиты АВ номиналом более 32 ампер лежит в диапазоне от 1 секунды до 120 секунд.

ИСПЫТАНИЯ ЭЛЕКТРОМАГНИТНЫХ РАСЦЕПИТЕЛЕЙ

Автоматические выключатели с технической характеристикой типа B.

I = 3*In.

Целью данной токовой прогрузки является проверка мгновенного электромагнитного расцепителя. Время срабатывания автоматических выключателей любых номиналов, имеющих ВТХ типа B не должно превышать 0,1 секунды.

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

I = 5*In.

Токовая проверка пятикратным номиналом также рассчитана на мгновенный расцепитель. Технические условия проведения этого вида испытания такие же, как у предыдущего. АВ холодный, ток подаётся сторонним коммутатором. Автоматическое срабатывание расцепителя должно занимать не более 0,1 секунды.

Автоматические выключатели с технической характеристикой типа C и D.

АВ имеющие ВТХ вида C испытываются 5 – кратным и 10 – кратным током, автоматы с ВТХ D – 10 – кратным и 20 – кратным токами. Время отключения во всех случаях не должно быть более 0,1 секунды. В отдельных случаях АВ типа D могут быть подвергнуты техническим испытаниям 50 – кратным током.

КРИТЕРИИ ВЫБОРА ХАРАКТЕРИСТИКИ

Как видно из описания время – токовых характеристических параметров, к наиболее чувствительным аппаратам относятся АВ, обладающие ВТХ класса B, далее в порядке снижения чувствительности следуют типы C и D.

При выборе автоматических выключателей ВТХ исходят из технического характера защищаемой нагрузки. Процедура выбора выполняется при проектировании электрической части объекта. Выбираемый автомат всегда должен быть чувствительным настолько, насколько это возможно по условиям отстройки от максимальных токовых значений рабочего режима.

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

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

Это:

• осветительная, электронагревательная аппаратура;
• электродвигатели небольшой мощности с лёгким пуском, например воздушные маломощные вентиляторы.

Характеристика C применяется, когда требуется защитить нагрузку с двигателями средней мощности, имеющими заметные пусковые токи.

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

Часто встречаются технические рекомендации по выбору автоматических коммутационных аппаратов, в которых указывается, что тип B применяется в быту, тип C – в быту и на производстве, тип D – только на производстве. На самом деле защитный коммутационный аппарат выбирается не по назначению нагрузки, а по наличию и величине пусковых токов.

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

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

© 2012-2021 г. Все права защищены.

Представленные на сайте материалы имеют информационный характер и не могут быть использованы в качестве руководящих и нормативных документов

Типы характеристика классификация виды автоматических выключателей. Устройство автоматического выключателя: маркировка, токи, обозначение

Что такое время токовые характеристики автоматических выключателей

При нормальной работе электросети и всех приборов через автоматический выключатель протекает электрический ток. Однако если сила тока по каким-либо причинам превысила номинальные значения, происходит размыкание цепи из-за срабатывания расцепителей автоматического выключателя.

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

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

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

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

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

По логике работы, автомат, конечно же, должен отключиться. К примеру, мотор потребляет в пусковом режиме 12 А, а в рабочем – 5. Автомат стоит на 10 А, и от 12 его вырубит. Что в таком случае делать? Если например поставить на 16 А, тогда непонятно отключится он или нет если заклинит мотор или замкнет кабель.

Можно было бы решить эту проблему, если его поставить на меньший ток, но тогда он будет срабатывать от любого движения. Вот для этого и было придумано такое понятие для автомата, как его «время токовая характеристика».

Какие существуют время токовые характеристики автоматических выключателей и их отличие между собой

Как известно основными органами срабатывания автоматического выключателя являются тепловой и электромагнитный расцепитель.

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

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

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

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

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

Автоматы имеют несколько характеристик, самыми распространенными из которых являются:

• — B — от 3 до 5 ×In;
• — C — от 5 до 10 ×In;
• — D — от 10 до 20 ×In.

Что означают цифры указанные выше?

Приведу небольшой пример. Допустим, есть два автомата одинаковой мощности (равные по номинальному току) но характеристики срабатывания (латинские буквы на автомате) разные: автоматы В16 и С16.

Диапазоны срабатывания электромагнитного расцепителя для В16 составляет 16*(3…5)=48…80А. Для С16 диапазон токов мгновенного срабатывания 16*(5…10)=80…160А.

При токе 100 А автомат В16 отключится практически мгновенно, в то время как С16 отключится не сразу а через несколько секунд от тепловой защиты (после того как нагреется его биметаллическая пластина).

В жилых зданиях и квартирах, где нагрузки чисто активные (без больших пусковых токов), а какие-нибудь мощные моторы включаются нечасто, самыми чувствительными и предпочтительными к применению являются автоматы с характеристикой B. На сегодняшний день очень распространена характеристика С, которую также можно использовать для жилых и административных зданий.

Что касается характеристики D, то она как раз годится для питания каких-либо электромоторов, больших двигателей и других устройств, где могут быть при их включении большие пусковые токи. Также через пониженную чувствительность при КЗ автоматы с характеристикой D могут быть рекомендованы для использования как вводные для повышения шансов селективности со стоящими ниже групповыми АВ при КЗ.

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

Поэтому на графике верхняя кривая характеризует холодное состояние автомата, нижняя кривая характеризует горячее состояние автомата.

Пунктирной линией обозначен предельный ток срабатывания для автоматов до 32 А.

Что показано на графике время токовой характеристики

На примере 16-Амперного автомата, имеющего время токовую характеристику C, попробуем рассмотреть характеристики срабатывания автоматических выключателей.

На графике можно увидеть, как протекающий через автоматический выключатель ток влияет на зависимость времени его отключения. Кратность тока протекающего в цепи к номинальному току автомата (I/In) изображает ось Х, а время срабатывания, в секундах – ось У.

Выше говорилось, что в состав автомата входит электромагнитный и тепловой расцепитель. Поэтому график можно разделить на два участка. Крутая часть графика показывает защиту от перегрузки (работа теплового расцепителя), а более пологая часть защиту от КЗ (работа электромагнитного расцепителя).

Как видно на графике если к автомату С16 подключить нагрузку 23 А то он должен отключится за 40 сек. То есть при возникновении перегрузки на 45 % автомат отключится через 40 сек.

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

При прохождении через автомат С16 тока 5×In (80 А) он должен сработать через 0.02 сек (это если автомат горячий). В холодном состоянии, при такой нагрузке, он отключится в пределах 11 сек. и 25 сек. (для автоматов до 32 А и выше 32 А соответственно).

Если через автомат будет протекать ток равный 10×In, то он отключается за 0,03 секунды в холодном состоянии или меньше чем за 0,01 секунду в горячем.

К примеру, при коротком замыкании в цепи, которая защищена автоматом С16, и возникновении тока в 320 Ампер, диапазон времени отключения автомата будет составлять от 0,008 до 0,015 секунды. Это позволит снять питание с аварийной цепи и защитить от возгорания и полного разрушения сам автомат, закоротивший электроприбор и электропроводку.

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

В квартирах по возможности необходимо обязательно применять автоматы категории B, которые являются более чувствительными. Данный автомат отработает от перегрузки так же, как и автомат категории С. А вот о случае короткого замыкания?.

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

Ток может оказаться малым при коротком замыкании, если дом является старым, а к нему идут плохие провода с огромным сопротивлением линии (особенно в сельских сетях, где большое сопротивление петли фаза-нуль) – в таком случае автомат категории C может не сработать вообще. Поэтому единственным выходом из этой ситуации является установка автоматов с характеристикой типа В.

Следовательно, время токовая характеристика типа В является определенно более предпочтительной, в особенности в дачной или сельской местности или в старом фонде.

В быту на вводной автомат вполне целесообразно ставить именно тип С, а на автоматы групповых линий для розеток и освещения – тип В. Таким образом будет соблюдена селективность, и где-нибудь в линии при коротком замыкании вводной автомат не будет отключаться и «гасить» всю квартиру.

Похожие материалы на сайте:

Понравилась статья — поделись с друзьями!

Основы теории автоматов

Введение

Теория автоматов — увлекательная теоретическая область информатики. Он заложил свои корни в 20 веке, когда математики начали разрабатывать — как теоретически, так и буквально — машины, которые имитировали определенные черты человека, выполняя вычисления более быстро и надежно. Само слово automaton , тесно связанное со словом «автоматизация», обозначает автоматические процессы, осуществляющие производство определенных процессов.Проще говоря, теория автоматов имеет дело с логикой вычислений относительно простых машин, называемых автоматами . С помощью автоматов компьютерные ученые могут понять, как машины вычисляют функции и решают проблемы, и, что более важно, что означает определение функции как вычислимой или описание вопроса как разрешимой .

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

Основная цель теории автоматов — разработать методы, с помощью которых компьютерные специалисты могут описывать и анализировать динамическое поведение дискретных систем, в которых периодически производится выборка сигналов.Поведение этих дискретных систем определяется тем, как система построена из запоминающих и комбинационных элементов. Характеристики таких машин включают:

• Входы: предполагается, что представляют собой последовательности символов, выбранных из конечного набора I входных сигналов. А именно, набор I — это набор {x ₁ , x, ₂ , x ₃ … x _k }, где k — количество входов.
• Выходы: последовательностей символов, выбранных из конечного набора Z.А именно, набор Z — это набор {y ₁ , y ₂ , y ₃ … y _m }, где m — количество выходов.
• Состояния: конечное множество Q , определение которого зависит от типа автомата.

Существует четырех основных семейств автоматов :

• Конечный автомат
• Выталкивающие автоматы
• Линейно-ограниченные автоматы
• Машина Тьюринга

Приведенные выше семейства автоматов можно интерпретировать в иерархической форме, где конечный автомат — это простейший автомат, а машина Тьюринга — самый сложный.Основное внимание в этом проекте уделяется конечному автомату и машине Тьюринга. Машина Тьюринга — это машина с конечным числом состояний, но обратное неверно.

[вверху]

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

Увлекательная история того, как конечные автоматы стали отраслью информатики, иллюстрирует широкий спектр их приложений. Первыми, кто рассмотрел концепцию конечного автомата, была группа биологов, психологов, математиков, инженеров и некоторых из первых ученых-информатиков.Все они были объединены общим интересом: моделировать мыслительный процесс человека, будь то мозг или компьютер. Уоррен МакКаллох и Уолтер Питтс, два нейрофизиолога, были первыми, кто представил описание конечных автоматов в 1943 году. Их статья, озаглавленная «Логическое исчисление, имманентное нервной деятельности», внесла значительный вклад в изучение теории нейронных сетей, теории автоматы, теория вычислений и кибернетика. Позже двое ученых-информатиков Г. Мили и Э.Ф. Мур обобщили теорию на гораздо более мощные машины в отдельных статьях, опубликованных в 1955-56 гг.Конечные автоматы, машина Мили и машина Мура, названы в честь их работы. В то время как машина Мили определяет свои выходные данные через текущее состояние и входные данные, выходные данные машины Мура основываются только на текущем состоянии.

Автомат, в котором множество состояний Q содержит только конечных элементов, называется конечным автоматом (FSM).Конечные автоматы — это абстрактные машины, состоящие из набора состояний (набор Q), набора входных событий (набор I), набора выходных событий (набор Z) и функции перехода между состояниями. Функция перехода между состояниями принимает текущее состояние и входное событие и возвращает новый набор выходных событий и следующее состояние. Следовательно, его можно рассматривать как функцию, которая отображает упорядоченную последовательность входных событий в соответствующую последовательность или набор выходных событий.

Функция перехода между состояниями: I → Z

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

Чтобы полностью понять концептуально конечный автомат, рассмотрим аналогию с лифтом:

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

• Состояния: конечный набор состояний для отражения прошлой истории запросов клиентов.
• Входы: конечный набор входов, в зависимости от количества этажей, на которые может подняться лифт. Мы можем использовать набор I, размер которого равен количеству этажей в здании.
• Выходы: конечных наборов выходных данных, в зависимости от необходимости подъема или опускания лифта в соответствии с потребностями клиентов.

Конечный автомат формально определяется как кортеж из 5 (Q, I, Z, ∂, W), такой что:

• Q = конечный набор состояний
• I = конечный набор входных символов
• Z = конечный набор выходных символов
• ∂ = отображение I x Q в Q, называемое функцией перехода состояний, то есть I x Q → Q
• W = отображение W I x Q на Z, называемое функцией вывода
• A = набор состояний принятия, где F — подмножество Q

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

При рассмотрении конечных автоматов важно иметь в виду, что механический процесс внутри автоматов, который приводит к вычислению выходных данных и изменению состояний, не акцентируется и не углубляется в детали; вместо этого он считается «черным ящиком», как показано ниже:

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

Диаграмма состояний иллюстрирует работу автомата. Состояния представлены узлами графов, переходами стрелками или ветвями , а соответствующие входы и выходы обозначены символами. Стрелка, входящая слева в q ₀ , показывает, что q ₀ является начальным состоянием станка. Движения, не связанные с изменением состояний, обозначены стрелками по сторонам отдельных узлов.Эти стрелки известны как петли .

Существует нескольких типов конечных автоматов , которые можно разделить на три основные категории:

• акцепторы : либо принимать ввод, либо не
• распознаватели : либо распознают ввод, либо нет
• преобразователи : генерировать выходной сигнал по заданному входу

Приложения конечных автоматов можно найти в самых разных областях.Они могут работать с языками с конечным числом слов (стандартный случай), бесконечным числом слов (автоматами Рабина, автоматами Бирша), различными типами деревьев и в аппаратных схемах, где вход, состояние и выход являются битовыми. векторы фиксированного размера.

[вверху]

Конечное состояние против машин Тьюринга

Простейший автомат, используемый для вычислений, — это конечный автомат. Он может вычислять только очень примитивные функции; следовательно, это не адекватная модель вычислений.Кроме того, неспособность конечного автомата обобщать вычисления снижает его мощность.

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

Представьте себе современный процессор. Каждый бит в машине может находиться только в двух состояниях (0 или 1). Следовательно, существует конечное число возможных состояний. Кроме того, при рассмотрении частей компьютера, с которыми взаимодействует ЦП, существует ограниченное количество возможных входов от компьютерной мыши, клавиатуры, жесткого диска, различных слотовых карт и т. Д.В результате можно сделать вывод, что ЦП можно смоделировать как конечный автомат.

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

Всемирно известный ученый-компьютерщик Алан Тьюринг разработал первую «бесконечную» (или неограниченную) модель вычислений: машину Тьюринга в 1936 году для решения задачи Entscheindungs ​​. Машину Тьюринга можно рассматривать как конечный автомат или блок управления, снабженный бесконечным хранилищем (памятью). Его «память» состоит из бесконечного числа одномерных массивов ячеек. Машина Тьюринга — это, по сути, абстрактная модель современного компьютерного исполнения и хранения, разработанная для того, чтобы дать точное математическое определение алгоритма или механической процедуры.

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

Машина Тьюринга формально определяется набором [Q, Σ, Γ, δ, q ₀ , B, F], где

• Q = конечный набор состояний, из которых одно состояние q ₀ является начальным состоянием
• Σ = подмножество Γ, не включая B, это набор входных символов
• Γ = конечный набор допустимых обозначений ленты
• δ = функция следующего перемещения , функция отображения из Q x Γ в Q x Γ x {L, R}, где L и R обозначают направления влево и вправо соответственно
• q ₀ = в наборе Q в качестве начала состояние
• B = символ Γ, как пробел
• F ⊆ Q набор из конечных состояний

Таким образом, основное различие между машиной Тьюринга и двусторонним конечным автоматом (FSM) заключается в том, что машина Тьюринга способна изменять символы на своей ленте и моделировать выполнение и хранение на компьютере.По этой причине можно сказать, что машина Тьюринга способна моделировать все вычисления, которые сегодня можно вычислить с помощью современных компьютеров.

[вверху]

Введение в конечные автоматы — GeeksforGeeks

Конечные автоматы (FA) — это простейшая машина для распознавания шаблонов. Конечный автомат или конечный автомат — это абстрактная машина, которая имеет пять элементов или кортеж. У него есть набор состояний и правил для перехода из одного состояния в другое, но это зависит от применяемого входного символа.По сути, это абстрактная модель цифрового компьютера. На следующем рисунке показаны некоторые важные особенности общей автоматизации.

Рисунок: Характеристики конечных автоматов

На приведенном выше рисунке показаны следующие особенности автоматов:

1. Вход
2. Выход
3. Состояния автоматов
4. Отношение состояний
5. Выходное отношение

   Конечный автомат состоит из следующего:

 Q: Конечный набор состояний.Σ: набор входных символов.
q: Исходное состояние.
F: набор конечных состояний.
δ: функция перехода.
 

Формальная спецификация машины:
{Q, Σ, q, F, δ}.

FA характеризуется двумя типами:

1) Детерминированные конечные автоматы (DFA)

 DFA состоит из 5 кортежей {Q, Σ, q, F, δ}.
Q: набор всех состояний.
Σ: набор входных символов. (Символы, которые машина принимает в качестве входных данных)
q: Исходное состояние. (Стартовое состояние машины)
F: набор конечного состояния.δ: функция перехода, определяемая как δ: Q X Σ -> Q.
 

В DFA для определенного входного символа машина переходит только в одно состояние. Функция перехода определяется в каждом состоянии для каждого входного символа. Также в DFA нулевое (или ε) перемещение не допускается, т. Е. DFA не может изменить состояние без какого-либо входного символа.

Например, нижеприведенный DFA с Σ = {0, 1} принимает все строки, заканчивающиеся на 0.

Рисунок: DFA с Σ = {0, 1}

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

2) Недетерминированные конечные автоматы (NFA)
NFA похожи на DFA, за исключением следующих дополнительных функций:
1. Разрешено нулевое (или ε) перемещение, т.е. он может двигаться вперед без чтения символов.
2. Возможность передачи в любое количество состояний для конкретного входа.
Однако эти вышеупомянутые функции не добавляют мощности NFA. Если мы сравним оба по мощности, оба равноценны.

Из-за вышеупомянутых дополнительных функций NFA имеет другую функцию перехода, остальные такие же, как DFA.В.

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

NFA

Следует отметить одну важную вещь: в NFA, если какой-либо путь для входной строки приводит к конечному состоянию, то входная строка принимается . Например, в приведенной выше NFA есть несколько путей для входной строки «00». Поскольку один из путей ведет к конечному состоянию, «00» принимается вышеуказанным NFA.

Некоторые важные моменты:

Поскольку все кортежи в DFA и NFA одинаковы, за исключением одного из кортежей, который является функцией перехода (δ)

 В случае DFA
δ: Q X Σ -> Q
В случае NFA
δ: Q X Σ -> 2  Q  

Теперь, если вы понаблюдаете, вы обнаружите, что Q X Σ -> Q является частью Q X Σ -> 2 ^Q .

На правой стороне Q является подмножеством 2 ^Q , что указывает на то, что Q содержится в 2 ^Q или Q является частью 2 ^Q , однако обратное неверно.Таким образом, математически мы можем заключить, что каждый DFA является NFA, но не наоборот . Тем не менее, есть способ преобразовать NFA в DFA, поэтому существует эквивалентный DFA для каждого NFA .

1. И NFA, и DFA имеют одинаковую мощность, и каждый NFA может быть преобразован в DFA.
2. Как в DFA, так и в NFA может быть несколько конечных состояний.
3. NFA — это скорее теоретическая концепция.
4. DFA используется в лексическом анализе в компиляторе.

См. Тест по регулярным выражениям и конечным автоматам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований SDE с помощью курса CS Theory Course по доступной для студентов цене и станьте готовым для отрасли.

Теория автоматов

Автомат , во множественном числе Автоматы или Автоматы — это самоуправляемое устройство.Теория автоматов лежит в области компьютерных наук и дискретной математики. Это исследование абстрактной машины. Он предназначен для автоматического выполнения заранее определенной последовательности операций. Термин «автоматы» произошел от греческого слова αὐτόματα , что означает « самовоспроизводящийся ». Это означает, что он автоматически обрабатывает производство конкретной работы.

Изобретатель автоматов

Жак де Вокансон был ответственным за изобретение инновационных и впечатляющих автоматов.

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

Характеристики автоматов

К основным характеристикам автоматов относятся:

• Входы — это конечный набор входных символов или последовательностей символов, {x ₁ , x ₂ , x ₃ ,…x _k }, где k — количество входов.
• Выходы — это конечный набор выходных символов, {y ₁ , y ₂ , y ₃ , … y _m }, где m — количество выходов.
• Состояния — Это конечный набор, обозначаемый Q.

Примеры автоматов

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

Торговый автомат

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

Здесь пользователи вводят деньги, счетчики денег отправляют в блок управления. Пользователь выбирает продукт через блок управления. Внутренняя программа торгового автомата выдаст продукт, когда будет введено правильное количество.Это зависит от конструкции метода конечных автоматов (FSM) и Visual Automata Simulator (VAS) .

Светофор

Сегодня в системе управления дорожным движением также реализовано интеллектуальное интеллектуальное устройство. За этим стоит и теория автоматов. Он интеллектуально контролирует транспортные средства и пешеходный переход.

Видеоигры

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

Компилятор

Теория автоматов используется на этапе компиляции. В компиляторе исходный код преобразуется в целевой код в шесть этапов. На первом этапе используется лексический анализ. Он читает введенный символ за символом, пока не найдет лексему. После этого он анализирует код в DFA (детерминированные конечные автоматы).

Основная математическая терминология, используемая в автоматах

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

Набор

Набор — это группа объектов, содержащая символы, числа, объекты и даже сам набор.

Пример

  {2,32,17,49}  

Установить членство ∈

Обозначает, что элемент принадлежит набору.

Пример

  2 ∈ {2,32,17,49}  

Установить Нечленство ∉

Обозначает, что элемент не принадлежит набору.

Пример

  5 ∉ {2,32,17,49}  

Подмножество ⊆

Если A и B — два множества, мы говорим, что A является подмножеством B, A⊆B, если каждый элемент A также является элементом B.

Пример

  {3,9,12} ⊆ {3,9,12}  

Собственное подмножество ⊂

Если A и B — два множества, мы говорим, что A — собственное подмножество B, A ⊂ B, если A — подмножество B и не равно B.

Пример

  {5,24} ⊂ {5,24,43}  

Пустой набор Ø

Набор из 0 элементов называется пустым набором и обозначается Ø.

Это некоторые основные термины, используемые в автоматах.

Алфавиты

Конечный непустой набор символов. Обозначается греческой буквой ∑. Это набор, в котором определены строки. Это несколько примеров алфавитов.

Примеры алфавитов

  ∑ = {a, b, c, d}
∑ = {A, B, C} // Это алфавит
∑ = {0,1,2,3} // Это алфавит из цифр
∑ = {0,1, a, b, c, d} // Это алфавит из цифр  

Струны

Строка в алфавите — это конечная последовательность любого символа, выбранного из набора символов алфавита.Обычно обозначается w .

Примеры строк

  ∑  1  = {0,1}
w = 100111 // Это строка в алфавите ∑  1 
∑  2  = {a, b, c}
w2 = abaccab // Это строка в алфавите ∑  2   

Пустая строка обозначается как є или λ .
Длина строки — Длина строки обозначается как | w | .

Языки

Набор допустимых строк в конечном алфавите.Обозначается он L .
Пустой язык — Пустая строка не содержит строки, обозначается {} или ∅.

Пример языка

  ∑ = {a, b}
L = {aa, ab, ba, bb}
  

Клиновая застежка

Набор ∑ + — это бесконечное множество всех возможных строк любой возможной длины по all. Он создается путем объединения произвольных элементов набора строк. Его также называют Positive Closure или Kleene Star .

Примеры закрытия клини

  ∑ = {a, b}
∑  *  = {a, b aa, ab, ba, bb, ..}

∑  1  = {ab, c}
∑  1   *  = {ab, c, abc, abab, cc, abababc, ..}  

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

III. Детерминированный конечный автомат (dfas)

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

Например, на рис. 2 состояния представлены кружками. Одна часть конечного управления, соответствующая рис.2, — это переход δ ( q ₀ , 0) = q ₁ .То есть, когда в состоянии q ₀ и считывая 0, автомат переходит в состояние q ₁ . Затем головка ввода автоматически перемещается на один квадрат вправо (перемещение вправо от маркера правого конца приводит к отказу машины). Переход δ ( q ₀ , 1) = q ₂ указывает, что в состоянии q ₀ и при чтении 1 переход в состояние q ₂ . Опять же, головка ввода автоматически перемещается на один квадрат вправо.Остаток конечного управления для диаграммы переходов, показанной на рис. 2, задается аналогично. Конечное управление полностью показано в табличной форме в таблице I. Каждая строка в такой таблице представляет один возможный переход M . Эта таблица называется таблицей перехода для M . Обратите внимание, что в таблице нет записей, указывающих, каким должно быть следующее состояние, когда заголовок ввода находится над маркером конца. В таком случае, когда нет следующего состояния, машина просто останавливается.

Таблица I. Удобный метод представления функции перехода DFA

Примечание: Таблица переходов для DFA, представленная на Рис.2 показан здесь. Для удобства переходы пронумерованы, но эта нумерация не является частью конечного управления.

Теперь мы готовы представить формальное определение DFA. Описание DFA представлено в виде набора из пяти элементов, поэтому порядок компонентов фиксирован.

Определение 2

Детерминированный конечный автомат ( DFA ) представляет собой набор из пяти элементов M = ( Q , Σ, δ, q ₀ , F ) с указанными компонентами следующим образом:

1.

Q : Конечный непустой набор состояний .

2.

Σ: Алфавит данных и его индуцированный ленточный алфавит Σ _T = Σ ∪ {<,>}.

3.

δ: функция перехода или конечное управление — это функция

δ: Q × ΣT↦Q.

4.

q ₀ : Начальное состояние или начальное состояние , q ₀ ∈ Q .

5.

F : Набор принимающих состояний , F ⊆ Q

Набор состояний обозначен как Q Обратите внимание, что Q является конечным и непустым.

Алфавит данных обозначен Σ. Это символы, которые могут встречаться на входной ленте между <и>. Маркеры конца не могут использоваться в качестве символов данных. Алфавит ленты Σ _T — это набор всех возможных символов, которые появляются на ленте, и поэтому он представляет собой Σ объединение набора {<,>}.

Мы пока откладываем описание 3δ.

Начальное состояние обозначено q ₀ . Это особое состояние в Q и состояние, с которого начинается выполнение M . Обратите внимание, что начальное состояние — это , а не , выраженное как набор, как другие компоненты в определении.

F — непустой набор принимающих состояний. Эти особые состояния используются DFA, чтобы сигнализировать, когда он принимает свой ввод, если это действительно так.Когда машина останавливается в не принимающем состоянии, это означает, что ввод отклонен. Понятие принятия формально описано в определении 6.

Где в определении появляется входная лента? Лента используется в переходной функции δ. Область δ составляет Q × Σ _T элементов в области 8 упорядоченных пар. То есть δ берет состояние и символ с входной ленты (возможно, конечный маркер). Обратите внимание, что более сложные модели, которые мы представим позже, имеют полезные переходы на концевых маркерах.Ограничения, наложенные на DFA, не позволяют использовать маркеры конца. Поэтому в наших примерах мы показываем только δ, определяемую на Q × Σ. Типичным аргументом для δ будет (0,1). Используя стандартные обозначения функций, мы бы написали δ ((0,1)), чтобы обозначить, что δ применяется к ее аргументам. Чтобы упростить обозначения, мы опускаем «лишний» набор круглых скобок, имея в виду, что аргументы δ действительно являются упорядоченными парами. Так, например, мы пишем δ (0,1). Диапазон δ составляет Q .

Предположим, что q ∈ Q a ∈ Σ _T , и δ ( q, a ) = q ′, где q ′ ∈ Q . Это называется переходом на M . Этот переход перемещает M из состояния q в состояние q ‘при чтении a , а затем головка ввода перемещается на один квадрат вправо. На рис. 2 переходы были представлены краями между состояниями и помечены входными символами ленты.Поскольку δ — функция, DFA ведут себя детерминированно. Другими словами, у машины есть только один «выбор» для следующего перехода, точно так же, как типичная программа на C должна выполнить уникальную следующую инструкцию. Полная спецификация DFA, показанная на рис. 2, приведена ниже.

Пример 1

Формальная спецификация DFA.

Пятикратный набор для DFA M , показанный на рис. 2, выглядит следующим образом: M = ({ q ₀ , q ₁ , q ₂ }, { 0,1}, δ, q ₀ , { q ₀ }), где δ определяется, как в таблице переходов, показанной в таблице I, или эквивалентно выражается как

q0,0, q1, q0 , 1, q2, q1,0, q0, q1,1, q2, q2,0, q2, q2,1, q2.

Здесь мы записали функцию δ: Q × Σ _T ↦ Q в виде троек в Q × Σ _T × Q

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

Определение 3

Конфигурация DFA M = ( Q , Σ δ, q ₀ , F ) на входе x ∈ Σ является двухкортежным ( q , [ p , x ]), где q ∈ Q и [ p , x ] — это конфигурация входной ленты. Исходная конфигурация из M на входе x — это конфигурация ( q ₀ , [1, x ])> или эквивалентная ( q ₀ , τ ^I ( x )).Мы используем C ₀ для обозначения начальной конфигурации, когда понимаются M и x . Для станка M набор всех возможных конфигураций для всех возможных входов x обозначен C ( M ).

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

Определение 4

Пусть M = ( Q , Σ δ, q ₀ , F ) будет DFA.Пусть C ( M ) будет набором всех конфигураций M . Пусть C ₁ = ( q ₁ , [ p ₁ , x ]) и C ₂ = ( q ₂ , [ p ₂ , x ]) быть двумя элементами C ( M ). C ₁ ⊢ _M C ₂ тогда и только тогда, когда p ₂ = p ₁ + 1 и есть переход δ ( q ₁ σ [ p ₁ , x ]) = q ₂ Отношение ⊢ _M называется следующим ходом , шаг или дает отношение .

Уведомление ⊢ _M — это отношение, определяемое в конфигурациях. Это означает ⊢ _M ⊆C ( M ) × C ( M ). Поскольку δ является функцией, ⊢ _M также является функцией. Определение 4 говорит, что конфигурация C ₁ дает конфигурацию C ₂ , если есть переход от C ₁ , который при выполнении переводит M в новую конфигурацию C ₂ .

В качестве примера рассмотрим DFA, назовите его M , функция перехода которого была изображена в таблице I. Начальная конфигурация входа Mon x = 0011: ( q ₀ , [1, 0011]) . Применяя переход 1 из таблицы I, мы получаем

(q0, [1,0011]) ⊢M (q1, [2,0011]).

Машина прочитала 0 и перешла в состояние q ₁ . Продолжая эту трассу (формально определенную в определении 5), мы получаем следующую серию конфигураций:

(q1, [1,0011]) ⊢M (qo, [2,0011} (by transition3) ⊢M (q2 , [3,0011]) (по переходу2) ⊢M (q2, [4,0011]) (по переходу6)

Мы говорим, что DFA останавливает , когда нет следующего состояния или когда машина движется от конца кассета.Это может произойти, когда функция перехода между состояниями не определена. Конфигурация остановки DFA — это конфигурация C _h = ( q , [ p, x ]) ∈ C ( M ) со свойством, что δ ( q , σ [ p, x ]) не определено. Если DFA останавливается, когда больше не осталось входных данных для обработки, то есть он находится в конфигурации C = ( q, τ ^F ( x )), тогда мы говорим, что DFA в финальной конфигурации .То есть DFA находится в конфигурации C _h = ( q , [ p, x ]) ∈ C ( M ) со свойством, что p = | x | + 1.

Отношение ⊢ _M было определено для помощи в описании вычислений. Но ⊢ _M означает только одну ступеньку. Мы хотели бы обсудить вычисления различной длины, включая нулевую.

Определение 5

Пусть M будет DFA с отношением следующего хода ⊢ _M .Пусть C _i ∈ C ( M ), для 0 ≤ i ≤ n . Определим ⊢M * как рефлексивное транзитивное замыкание отношения ⊢ _M . C ₀ дает или ведет к C _n , если C ₀ ⊢ _M * C _n . Вычисление или трассировка для M представляет собой последовательность конфигураций, связанных между собой ⊢ _M следующим образом: C ₀ ⊢ _M C ₁ ⊢ _M · · · ⊢ _M C _n .Это вычисление имеет длину n , или мы говорим, что оно имеет n шагов . Иногда мы пишем C ₀ ⊢ _M ⁿ C _n , чтобы указать вычисление от C ₀ до C _n длиной n .

Обратите внимание, что на входе x длиной n DFA будет выполняться не более чем n + 1 шагов. Если функция перехода между состояниями определена для каждого состояния и символа данных, то DFA обработает все входные данные.Для четырехэтапного вычисления, описанного выше, мы можем записать

(q0, [1,0011]) ⊢M * (q2, [5,0011]) или (q0, [1,0011] ⊢M4 (q2, [5 , 0011])

с ( q ₂ , [5, 0011]) окончательной конфигурацией.

Мы хотели бы описать вычислительные возможности DFA в терминах языков, которые они принимают. Во-первых, нам нужно определить, что означает для DFA принятие входных данных . Идея состоит в том, что машина просто считывает все свои входные данные и оказывается в состоянии приема.

Определение 6

Пусть M = ( Q , Σ, δ, q ₀ , F ) будет DFA и q ∈ Q. M принимает вход x ∈ Σ *, если

(q0, τI (x)) ⊢M * (f, τF (x)),

, где f ∈ F . Это вычисление называется вычислением , принимающим . Конфигурация остановки ( q , τ ^F ( x )) называется принимающей конфигурацией из M , если q ∈ F .Если M не принимает ввод x , то говорят, что M отклоняет x . Вычисление M на входе x в этом случае называется вычислением отклонения , а M было оставлено в конфигурации отклонения .

M начинает вычисление в своем начальном состоянии, при этом головка входной ленты сканирует первый символ x и x , записанный на входной ленте. Если M считывает все x и заканчивается в состоянии принятия, он принимает.Важно отметить, что M считывает свой ввод только один раз и в режиме on-line . Это означает, что M считывает ввод слева направо и затем должен решить, что с ним делать. M не может вернуться и снова посмотреть ввод. Кроме того, даже если M может определить конец ввода, обнаружив маркер>, это полезно только в том случае, если M может изменить направление на входной ленте. Таким образом, M должен быть готов принять решение о принятии или отклонении, предполагая, что ввод может быть исчерпан после того, как только что прочитанный символ.

В качестве примера DFA с функцией перехода, показанной на рис. 2, принимает входные данные x = 0011, поскольку q ₀ ∈ F и ( q ₀ , [1, 0011 ]) ⊢ * ( q ₀ [5, 0011]). Теперь мы можем определить язык , принятый , с помощью DFA M . Неформально это просто набор всех струн, принимаемых M .

Определение 7

Пусть M = ( Q , Σ, δ, q ₀ , F ) будет DFA.Допустимый язык : , M, , обозначенный L ( M ), это { x | M принимает x }. Объединение всех языков, принятых DFA, обозначается L _DFA . То есть

LDFA = L | есть DFAMwithL = LM.

DFA, показанный на рис. 2, принимает язык {Λ, 00, 0000, 000000,…}. Отсюда следует, что этот язык находится в L _DFA . Давайте теперь посмотрим на типичное применение DFA.

Пример 2

Применение DFA, включающее поиск текста по заданному шаблону.

DFA используются для сопоставления с образцом. Здесь мы рассматриваем задачу поиска заданного шаблона x в текстовом файле. Предположим, наш алфавит — { a , b , c }. Этот пример можно легко обобщить на более крупные алфавиты. Чтобы еще больше упростить обсуждение, пусть x будет строкой abac. Используемые здесь методы можно применить к любой другой струне размером x .Формально мы хотим построить DFA, который принимает язык

s | s∈a, b, c * и содержит шаблонabac.

Идея состоит в том, чтобы начать с жесткого кодирования шаблона x в состояниях машины. Это проиллюстрировано на фиг. 5A. Поскольку шаблон abac имеет длину четыре, для запоминания шаблона необходимы четыре состояния в дополнение к начальному состоянию, q ₀ . Думайте о каждом состоянии как о значении определенного прогресса в поиске паттерна.Так, например, при достижении состояния q ₂ машина запоминает, что было прочитано ab .

Рис. 5. Этапы построения DFA для распознавания шаблона x в текстовом файле. В этом случае, соответствующем Примеру 2, x равно abac . Часть (A) показывает, как начать с жесткого кодирования шаблона в состояниях машины. Часть (B) показывает полный DFA.

Мы можем достичь состояния q ₄ , только если мы прочитали шаблон abac , поэтому q ₄ — единственное требуемое состояние приема.Следующим шагом будет заполнение оставшихся переходов на других символах алфавита. Полный DFA показан на рис. 5B. Обратите внимание, как на рисунке есть несколько ребер с более чем одной меткой. Это просто означает, что соответствующий переход может применяться при чтении любого из символов, обозначающих переход.

Теперь мы объясним, как были добавлены дополнительные переходы, исследуя состояние q ₃ . Следующая методика может быть применена аналогичным образом к другим штатам.Из состояния q ₃ при чтении « c » мы переходим в состояние принятия, указывая, что шаблон действительно был найден; поэтому состояние q ₄ является состоянием приема. Из состояния q ₃ при чтении « a » мы переходим обратно в состояние q ₁ . Это потому, что « a » может быть началом шаблона abac . То есть мы можем использовать этот « a ». Если мы читаем « b » из состояния q ₃ , то нам нужно полностью перейти обратно в состояние q ₀ .« b » сводит на нет весь достигнутый нами прогресс, и теперь мы должны начать все сначала.

Комплексное описание DFA для распознавания строк, содержащих шаблон x , равно abac по алфавиту { a, b, c }: ({ q ₀ , q _1, q ₂ , q ₃ , q ₄ }, { a , b , c }, δ q ₀ , { q ₄ }), где δ показано в таблице II.Стоит отметить один момент: как только шаблон найден (то есть при первом входе в принимающее состояние), текстовый редактор может уведомить пользователя о местонахождении шаблона, а не продолжать обработку оставшейся части файла. Обычно так поступают текстовые редакторы.

Таблица II. Таблица переходов для DFA, описанная в примере 2 и показанная на рис.5

Теория автоматов | NFA | DFA | Машина Тьюринга | Конечные автоматы | Автомат | Выталкивающие автоматы

Теория автоматов — это интересная, увлекательная теоретическая область информатики, которая занимается проектированием абстрактных самоходных вычислительных устройств, которые автоматически выполняют заданную последовательность операций.Слово автоматы (множественное число от автомата) происходит от греческого слова αὐτόματα, что означает «самодействующий».

Теория автоматов зародилась в 20 веке, когда математики начали создавать машины, которые имитировали определенные черты человека, выполняя вычисления более быстро и надежно. Теория автоматов — это комбинационное исследование теоретической информатики и дискретной математики.

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

Основная цель теории автоматов — разработать методы для компьютерных ученых, которые могут описывать и анализировать динамическое поведение дискретных систем. В таких системах периодически производится выборка сигналов. Поведение системы определяется хранилищем и комбинационными элементами, с помощью которых она создается. Характеристики таких машин включают:

• Входы: последовательностей символов, выбранных из конечного набора входных сигналов.Где I — это набор {x ₁ , x, ₂ , x ₃ … x _k }, где k — количество входов.
• Выходы: последовательностей символов, выбранных из конечного набора Z. где Z — это набор {y ₁ , y ₂ , y ₃ … y _m }, где m — число выходов.
• Состояния: конечное множество Q , определение которого зависит от типа автомата.

Автомат с конечным числом состояний называется конечным автоматом (FA) или конечным автоматом.

Формальное определение конечных автоматов

Автомат можно представить в виде набора из пяти (Q, ∑, δ, q0, F), где

• Q — конечный набор состояний.
• ∑ — конечный набор символов, называемый алфавитом автомата.
• δ — переходная функция.
• q0 — начальное состояние, из которого обрабатывается любой ввод (q0 ∈ Q).
• F — это набор конечных состояний / состояний Q (F ⊆ Q).

Конечный автомат можно разделить на два типа —

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

Формальное определение DFA

DFA состоит из 5 кортежей {Q, ∑, q, F, δ}.

• Q набор всех состояний.
• ∑ набор входных символов. (Обозначения, которые машина принимает в качестве входных данных)
• q Исходное состояние. (Пусковое состояние машины)
• F набор конечного состояния.
• δ Функция перехода, определяемая как δ: Q X ∑ -> Q.

Пример DFA

Предположим, что DFA Q = {a, b, c}, ∑ = {0, 1}, q ₀ = {a}, F = {c} и

Переходная функция δ, как показано ниже

Тогда мы можем представить это графически как

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

Формальное определение NFA:

NFA | NDFA может быть представлен кортежем из 5 (Q, ∑, δ, q0, F), где

• Q — конечный набор состояний.
• ∑ — это конечный набор символов, называемых алфавитами.
• δ — функция перехода, где δ: Q × ∑ → 2Q (здесь набор мощности Q (2Q) представляет любую комбинацию состояний Q)
• q0 — начальное состояние, из которого обрабатывается любой ввод (q0 ∈ Q).
• F — это набор конечных состояний / состояний Q (F ⊆ Q).

NFA представлена ​​орграфами, называемыми диаграммой состояний.

Пример NFA:

Допустим, NFA Q = {a, b, c}, ∑ = {0, 1}, q ₀ = {a}, F = {c}

Переходная функция δ, как показано ниже

Тогда мы можем представить это графически как

Автомат выталкивания используется для реализации контекстно-свободной грамматики так же, как мы разрабатываем DFA для обычной грамматики.DFA может запоминать конечный объем информации, в то время как КПК может запоминать бесконечное количество информации.

У выталкивающего автомата три компонента — входная лента, блок управления и стопка бесконечного размера. Заголовок стека считывает верхний элемент стека.

Стек выполняет две операции — Push (для добавления элемента наверху стека), Pop (для удаления верхнего элемента стека).

КПК считывает верх стека при каждом переходе.

Формальное определение КПК

КПК можно формально описать как набор из семи (Q, ∑, S, δ, q0, I, F)

• Q — конечное число состояний
• ∑ — входной алфавит
• S — символы стека
• δ — функция перехода: Q × (∑ ∪ {ε}) × S × Q × S *
• q0 — начальное состояние (q0 ∈ Q)
• I — начальный символ вершины стека (I ∈ S)
• F — набор принимающих состояний (F ∈ Q)

Машина Тьюринга была изобретена Аланом Тьюрингом в 1936 году.Это принимающее устройство, которое принимает рекурсивно перечисляемый набор языков, созданный грамматиками типа 0.

Машину Тьюринга можно представить как конечный автомат или блок управления, снабженный бесконечной памятью. Его «память» состоит из бесконечного числа одномерных массивов ячеек. Машина Тьюринга — это, по сути, абстрактная модель современного компьютерного исполнения и хранения. Он был разработан для того, чтобы дать точное математическое определение алгоритма или механической процедуры.

Формальное определение машины Тьюринга

Машина Тьюринга формально определяется множеством [Q, Σ, Γ, δ, q0, B, F], где

• Q конечный набор состояний, из которых одно состояние q0 является начальным состоянием
• Σ подмножество Γ, не включая B, это набор входных символов
• Γ Конечное множество допустимых обозначений ленты
• δ функция следующего перемещения, функция отображения из Q x Γ в Q x Γ x {L, R}, где L и R обозначают направления влево и вправо соответственно
• q0 в наборе Q в качестве начального состояния
• B символ Γ, как пробел
• F ⊆ Q набор конечных состояний

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

Должен поделиться своими взглядами в комментариях ниже. Не забудьте заглянуть в технические блоги, чтобы найти более информативные блоги, связанные с технологиями https://msatechnosoft.in/blog/category/tech-blogs/

(PDF) Характеристические полугруппы управляемых автоматов

418 Татьяна Петкович, Мирослав

´

Цириц и Стоян Богданович

новая концепция характеристических полугрупп нерегулярных автоматов, т.е.е., ди-

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

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

, соответствующие автоматам, принадлежащим некоторым важным подклассам

класса управляемых автоматов. В [14], [15] авторы привели

двух видов соответствий между разновидностями автоматов и полугрупп.

В качестве инструмента они использовали переходные полугруппы автоматов, поэтому полученные результаты

охватывают только регулярные разновидности автоматов.Здесь с помощью характеристических полугрупп

устанавливается соответствие между иррегулярными разновидностями автоматов

и разновидностями полугрупп.

Сначала мы дадим некоторые определения, касающиеся полугрупп. Элемент z полугруппы

S является правым (левым) нулем группы S, если sz = z (zs = z) для каждого s ∈ S,

и нулем, если он одновременно является левым и правым нулем группы S Полугруппа, у которой каждый элемент

является правым нулем, является полосой правого нуля. Для идеала T полугруппы S отношение конгруэнции



T

на S, называемое конгруэнцией Риса на S, определяемое посредством T,

определяется следующим образом: для s, t ∈ S мы говорим, что (s, t) ∈ 

T

тогда и только тогда, когда либо s = t, либо

s, t ∈ T.Полугруппа факторов S / 

T

, обычно обозначаемая S / T, представляет собой коэффициент Рееса

для S, определяемый T. Полугруппа S является идеальным расширением полугруппы T

с помощью полугруппы Q с нулем, если T идеал в S и фактор Риса S / T

изоморфен Q. Если, кроме того, Q — нильпотентная полугруппа , т. е. если Q

k

= {0} для

некоторого k ∈ N, где 0 — ноль Q, то S является нильпотентным расширением T. Обратите внимание на

, что на протяжении всей статьи N обозначает множество положительных натуральных чисел.

Далее мы приводим некоторые понятия и обозначения из теории автоматов. Автоматы

, рассматриваемые в этой статье, будут автоматами без выходов в смысле

определения из [7]. Набор состояний и набор входов автомата

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

с входным алфавитом X, называемые X-автоматами, могут рассматриваться как унарные алгебры

типа, индексируемые X, и они также известны как X-алгебры.Следовательно, понятия

, такие как сравнение, гомоморфизм, порождающее множество, прямое произведение,

подпрямое произведение и т. Д., Будут иметь свой обычный алгебраический смысл (см. [4]). В порядке

для упрощения записи автомат с набором состояний A также обозначается той же буквой A

. Для алфавита X свободный моноид над X обозначается X

∗

,

его нейтральный элемент. обозначается e, а свободная полугруппа над X обозначается

через X

+

.X-автомат A переходит из состояния a в состояние, обозначенное au,

или au

A

, если необходимо выделить автомат A, под действием входного слова

u ∈ X

∗

.

Для алфавита X через X

∗

@

мы обозначаем X-автомат, набор состояний которого равен

X

∗

, а переходы определяются как (u, x)  → ux.ByX

+

@

обозначается субавтомат

X

∗

@

с набором состояний X

+

.Для сравнения θ из X

+

, сравнение

θ

∗

, определенное на X

∗

с помощью θ

∗

= θ ∪ {(e, e)}, является конгруэнцией на автомате X

∗

@

и автомате Майхилла сравнения θ, в обозначении M (θ), множитель

автомата X

∗

@

относительно сравнения θ

∗

, то есть M (θ) = X

∗

@

/ θ

∗

.

Для данного слова u ∈ X

∗

автомат A u-направляемый, если au = bu для всех

a, b ∈ A, а u — направляющее слово A. Кроме того, A является управляемый автомат

, если A u-направляемый для некоторого слова u ∈ X

∗

.ByDW (A) множество всех направляемых

11.3.2 Недетерминированные конечные автоматы

11.3.2 Недетерминированные конечные автоматы

11.3.2 Недетерминированные конечные автоматы

Интересная связь между идеями этой главы и
теория конечных автоматов, которая является частью теории
вычисление (см. [462,891]).В разделе 2.1,
было упомянуто, что определение того, существует ли какая-то строка
который принимается DFA,
эквивалентно дискретно выполнимой задаче планирования. Если
непредсказуемость вводится в модель, затем
Получен недетерминированный конечный автомат (NFA), как показано
на рисунке 11.8. Это один из простейших примеров.
недетерминизма в теоретической информатике. Такой
недетерминированные модели служат мощным инструментом для определения моделей
вычислений и связанных с ними классов сложности.Оказывается
что эти модели дают интересные примеры информации
пробелы.

NFA обычно описывается с помощью ориентированного графа, как показано на
Рис. 11.8b, и рассматривается как особый вид конечных
Государственный аппарат. Каждая вершина графа представляет состояние, а ребра
представляют возможные переходы.Входная строка конечных
длина считывается машиной. Обычно входная строка представляет собой
двоичная последовательность нулей и нулей. Начальное состояние обозначено
направленная внутрь стрелка, не имеющая исходной вершины, как показано на рисунке, указывающая на
состояние на рисунке 11.8b. Машина запускается в этом состоянии
и читает первый символ входной строки. Исходя из его стоимости,
он делает соответствующие переходы. Для DFA следующее состояние должно быть
указывается для каждого из двух входов 0 и из каждого состояния.
Из состояния в NFA может быть любое количество исходящих ребер.
(включая ноль), которые представляют ответ на один символ.Для
Например, есть два исходящих ребра, если 0 считывается из состояния
(стрелка от до фактически соответствует двум направленным ребрам,
один для 0, а другой для). Также есть края, обозначенные
со специальным символом. Если у государства есть исходящий
, состояние может сразу перейти по краю
без прочтения другого символа. Это может быть повторено любое количество
раз, для любых исходящих ребер, которые могут встретиться,
без чтения следующего символа ввода. Недетерминизм возникает из
тот факт, что есть несколько вариантов возможных следующих состояний
к нескольким краям для одного и того же входа и переходов.Нет датчика, показывающего, какое состояние фактически выбрано.

Интерпретация, часто приводимая в теории вычислений, заключается в том, что
когда есть несколько вариантов, машина клонирует себя и один
копия запускает каждый выбор. Это похоже на наличие нескольких вселенных, в которых
каждое различное возможное действие природы происходит одновременно.
Если нет исходящих ребер для определенной комбинации состояния и
input, то клон умирает. Любые состояния, обозначенные значком
двойная граница, такая как состояние на Рисунке 11.8, называются
принимает состояния . Когда входная строка заканчивается, NFA называется
принять входную строку, если существует хотя бы один альтернативный
Вселенная, в которой конечным состоянием машины является состояние принятия.

Состав, обычно используемый для НЖК, кажется очень близким к составу.
2.1 для дискретного выполнимого планирования. Вот типичный NFA
формулировка [891], которая формализует идеи, изображенные в
Рисунок 11.8:

Теперь рассмотрим переформулировку NFA и ее принятие строк как
своего рода проблема планирования.Входную строку можно рассматривать как план
без обратной связи; это фиксированная последовательность действий. В
выполнимая задача планирования состоит в том, чтобы определить, существует ли какая-либо строка
что принято NFA. Поскольку нет обратной связи, нет
сенсорная модель. Начальное состояние известно, но последующие состояния
невозможно измерить. I-состояние истории на этапе сокращает
к
, история действий.
Недетерминизм можно объяснить определением действий природы
которые мешают переходам между состояниями.Это приводит к
следующий состав, который описан в терминах состава
11.2.

История I-space
определяется с использованием

для каждого
и взяв объединение, как определено в
(11.19). Предположим, что начальное состояние NFA равно
всегда фиксированный; следовательно, он не фигурирует в определении

.

Для выражения задачи планирования лучше всего использовать
недетерминированное I-пространство
из раздела
11.2.2. Таким образом, каждое недетерминированное I-состояние,
, — это подмножество, которое соответствует возможному
текущее состояние машины.Начальное условие может быть любым
подмножество, потому что переходы могут происходить из.
Последующие недетерминированные I-состояния следуют непосредственно из. В
задача — вычислить план вида

что приводит к
с

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

Проблема, приведенная в формулировке 11.3, не совсем точная
специализация Формулировки 11.1 в связи с состоянием
функция перехода. Для удобства было прямо определено,
вместо того, чтобы явно требовать, чтобы это определялось с точки зрения природы
действия,
, которые в этом контексте зависят как от
для NFA. Есть еще одна небольшая проблема, связанная с этим.
формулировка. В задачах планирования, рассматриваемых в этой книге,
всегда предполагал, что есть текущее состояние. Для NFA это было
уже упоминалось, что если нет исходящих ребер для определенного
input, то клон машины умирает.Это означает, что потенциал
текущие государства перестают существовать. Возможно даже, что каждый клон
умирает, что не оставляет машине текущего состояния. Это может быть
легко активируется прямым определением; однако проблемы с планированием
всегда должен иметь текущее состояние. Чтобы решить эту проблему, мы могли
дополнить формулировку 11.3, чтобы включить дополнительное состояние мертвых , что означает смерть клона, когда нет
исходящие края. Мертвое состояние никогда не может лежать в
происходит переход в мертвое состояние, состояние остается мертвым для всех
время.В этом разделе пространство состояний не будет расширено.
способ; однако важно отметить, что состав NFA может
легко привести в соответствие с формулой 11.3.

Модель планирования теперь можно сравнить со стандартным использованием NFA в
теория вычислений. Язык NFA определен для
быть набором всех входных строк, которые он принимает. Проблема планирования
сформулированная здесь, определяет, существует ли строка (которая является
план, который заканчивается действиями по прекращению), который принимается NFA.Точно так же алгоритм планирования определяет, будет ли язык
NFA пуста. Построение набора всех успешных планов — это
эквивалентно определению языка NFA.

Основная теорема теории конечных автоматов утверждает, что для
набор строк, принимаемых NFA, существует DFA (детерминированный)
который принимает тот же набор [891]. Это доказано
построение ДКА непосредственно из недетерминированного I-пространства. Каждый
недетерминированное I-состояние можно рассматривать как состояние DFA.Таким образом,
DFA имеет состояния, если исходный NFA имеет состояния. В
переходы состояний DFA выводятся непосредственно из переходов
между недетерминированными I-состояниями. Когда ввод (или действие)
задано, то происходит переход от одного подмножества к другому. А
переход осуществляется между двумя соответствующими состояниями в DFA.
Эта конструкция является интересным примером того, как I-пространство является
новое пространство состояний, которое возникает, когда состояния исходного состояния
космос неизвестны. Хотя I-пространство обычно больше, чем
исходное пространство состояний, его состояния всегда известны.Следовательно
поведение выглядит так же, как и в случае информации о совершенном состоянии.
Эта идея является очень общей и может быть применена ко многим задачам, выходящим за рамки
DFA и NFA; см. Раздел 12.1.2