В сегодняшнюю технологическую эпоху области как аппаратного, так и программного обеспечения пережили огромное развитие. Одно из основных направлений развития было замечено в методах проектирования аппаратного обеспечения. С технология выращивания удалось реализовать концепцию совместного проектирования оборудования и программного обеспечения. Разработаны различные методы, с помощью которых, используя программное обеспечение можно полностью проектировать и моделировать аппаратные системы. Одним из таких методов является теория автоматов. Теория автоматов - это раздел Информатика который имеет дело с проектированием абстрактной модели вычислительных устройств, которые автоматически следуют заранее определенной последовательности шагов. В этой статье обсуждается краткая информация об учебнике по автоматам.
Что такое теория автоматов?
Слово автоматы происходит от греческого языка, что означает «самодействующий». Автомат - это математическая модель машины. Автомат состоит из состояний и переходов. Когда ввод передается автомату, он переходит в следующее состояние в зависимости от функции перехода. Входные данные для функции перехода - это текущее состояние и недавние символы. Если автомат имеет конечное число состояний, он известен как конечный автомат или Конечный автомат . Конечные автоматы представлены 5-кратным набором (Q, ∑, δ, qo, F)
Где,
Q = Конечный набор состояний.
∑ = конечный набор символов, также называемый алфавитом автоматов.
δ = переходная функция.
qo = начальное состояние входа.
F = набор конечных состояний Q.
Основные терминологии теории автоматов
Некоторые из основных терминов теории автоматов:
1 . Алфавит : Любой конечный набор символов в теории автоматов известен как алфавит. Представленный буквой набор {a, b, c, d, e,} называется алфавитным набором, тогда как буквы набора 'a', 'b', 'c', 'd', 'e' называются символы.
два . Нить : В автоматах строка - это конечная последовательность символов, взятых из алфавитного набора ∑. Например, строка S = ‘adeaddadc’ действительна на алфавитном наборе = {a, b, c, d, e,}.
3 . Длина строки : Количество символов, присутствующих в строке, называется длиной строки. Для строки S = ‘adaada’ длина строки составляет | S | = 6. Если длина строки равна 0, она называется пустой строкой.
4 . Клин Стар : Это унарный оператор на множестве символов Σ, который дает бесконечное множество всех возможных строк, включая λ, всех возможных длин на множестве Σ. Он представлен. Например, для множества Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen Closure : Это бесконечное множество всех возможных строк алфавита, исключая λ. Обозначается он. Для множества Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Язык : Язык - это подмножество звездного набора Клини * для некоторого набора алфавита Σ. Язык может быть конечным или бесконечным. Например, если язык принимает все возможные строки длины 2 на множестве Σ = {a, d}, тогда L = {aa, ad, da, dd}.
Формальные языки и автоматы
В теории автоматов формальный язык - это набор строк, где каждая строка состоит из символов принадлежащий конечному набору алфавита Σ. Давайте рассмотрим кошачий язык, который может содержать любые строки из бесконечного множества ниже…
мяу!
уууу!
ууууу !! ……
Алфавит для кошачьего языка Σ = {m, e, w,!}. Пусть этот набор используется для модели конечных автоматов-m. Тогда формальный язык, характеризуемый моделью m, обозначается через
L (м)
L (m) = {‘мяуууууууууууууууууууууууууууууууууууууу’, ……}
Автомат полезен для определения языка, потому что он может выражать бесконечное множество в замкнутой форме. Формальные языки не совпадают с естественными языками, на которых мы говорим в повседневной жизни. Формальный язык может обозначать различные состояния машины, в отличие от наших обычных языков. Формальный язык используется для моделирования части естественного языка, такой как синтаксис и т. Д. Формальные языки определяются конечными автоматами. Есть две основные точки зрения автоматов с конечным состоянием: акцепторы, которые могут определить, находится ли строка на языке, и вторая - это генератор, который производит только строки на языке.
Детерминированные конечные автоматы
В автоматах детерминированного типа при вводе данных мы всегда можем определить, в какое состояние будет переход. Поскольку это конечный автомат, он называется детерминированными конечными автоматами.
Графическое представление
Диаграмма состояний - это орграфы, используемые для графического представления детерминированных конечных автоматов. Давайте разберемся на примере. Пусть детерминированные конечные автоматы будут…
Q = {a, b, c, d}.
Σ = {0, 1}
= {а}
F = {d} а функция перехода будет
Табличная форма графического представления
Диаграмма состояния
Диаграмма состояний детерминированных конечных автоматов
Из диаграммы состояний
- Состояния представлены вершинами.
- Переходы представлены дугой, помеченной входным алфавитом.
- Пустая одиночная входящая дуга представляет начальное состояние.
- Состояние с двойными кружками - это конечное состояние.
Недетерминированные конечные автоматы
Автоматы, в которых состояние выхода для данного входа не может быть определено, называются недетерминированными автоматами. Его также называют недетерминированными конечными автоматами, так как он имеет конечное число состояний. Недетерминированные конечные автоматы представлены в виде набора из 5, где (Q, ∑, δ, qo, F)
Q = конечный набор состояний.
∑ = Набор алфавита.
δ = функция перехода
куда : 
qo = Начальное состояние.
Графическое представление
Недетерминированные конечные автоматы представлены с помощью диаграммы состояний. Пусть недетерминированные конечные автоматы -
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Переходы
Табличная форма графического представления
Диаграмма состояния
Диаграмма состояний недетерминированных конечных автоматов
Приложения теории автоматов
Приложения теория автоматов включая следующее.
- Теория автоматов очень полезна в областях теории вычислений, производства компиляторов, искусственного интеллекта и т. Д.
- Конечные автоматы играют важную роль в компиляторах обработки текста и аппаратном обеспечении.
- Для приложений в AI и в языки программирования , Контекстно-свободная грамматика очень полезна.
- В области биологии полезны клеточные автоматы.
- В теории конечных полей также можно найти применение автоматов.
В этой статье мы узнали краткое введение в языки теории автоматов и вычисления. Автоматы существуют с доисторических времен. С изобретением новых технологий в этой области наблюдается много новых разработок. С какими типами автоматов вы сталкивались?
