Язык допускаемый автоматом это множество + видео обзор

Определение автомата с магазинной памятью (МП-автомата). Язык, допускаемый МП-автоматом. Расширенный МП-автомат

Распознаватели, определяющие КС-языки, моделируются автоматами с магазинной памятью (МПА).

Автомат с магазинной памятью (МПА) – это семерка A=(N,T,V,d, n0, v0,F),

где N – множество состояний автомата;

T – конечный входной алфавит (множество допустимых символов);

V – специальный конечный алфавит магазинных символов автомата (обычно в него входят терминальные и нетерминальные символы грамматики), TÍV ;

d – функция переходов, отображающая множество N´(TÈ)´V на конечное множество подмножеств множества (N´V * );

n0 – начальное состояние автомата: n0ÎN;

v0 – начальный символ магазина: v0ÎV;

K – множество конечных состояний автомата: KÍN, K¹Æ.

В отличие от КА МП-автомат имеет «стек» магазинных символов, который играет роль дополнительной, или внешней памяти.

Переход МПА из одного состояния в другое зависит не только от входного символа, но и от содержимого стека.

МПА в конкретный момент времени характеризуется тремя параметрами: состоянием автомата, текущим символом входной цепочки и содержимым стека.

На каждом такте МПА

· считывает символ входной цепочки,

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

· первый символ цепочки становится вершиной стека.

· состояние автомата изменяется.

Допускаются переходы (l–такты), при которых входной символ игнорируется, тогда он становится входным символом при следующем такте, но состояние и содержимое стека может измениться.

Автомат может проделывать l–такты, когда уже прочел входную цепочку; но, если магазин пуст, следующий такт невозможен.

Язык, определяемый МП-автоматом

МПА допускает цепочку символов w, если, получив эту цепочку на вход, он может перейти в одно из конечных состояний.

После окончания цепочки автомат может проделать некоторое количество –тактов.

Язык, определяемый МП-автоматом P – это множество всех цепочек символов, допускаемых этим автоматом: L(P). Два автомата P1 и P2 эквивалентны, если они определяют один и тот же язык: L(P1)=L(P2).

Говорят, что МПА допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из своих конечных состояний, а стек пуст.

Язык, заданный автоматом P, допускающим цепочки с опустошением стека, обозначается как Ll (P).

Для любого МП-автомата всегда можно построить эквивалентный ему МПА, допускающий цепочки с опустошением стека.

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

Варианты реализации алгоритма работы недетерминированного МПА.

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

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

Первый вариант

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

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

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

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

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

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

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

Если ни одна из копий не достигнет конечной конфигурации, алгоритм завершается с ошибкой и цепочка не принимается.

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

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

Источник

ОСНОВЫ ТЕОРИИ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ В ПРИМЕРАХ И ЗАДАЧАХ. Учебно-методическое пособие

1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский Нижегородский государственный университет им НИ Лобачевского» ЛП Жильцова, ТГ Смирнова ОСНОВЫ ТЕОРИИ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ В ПРИМЕРАХ И ЗАДАЧАХ Учебно-методическое пособие Рекомендовано методической комиссией института информационных технологий, математики и механики для студентов ННГУ, обучающихся по направлениям подготовки 3 «Фундаментальная информатика и информационные технологии», 933 «Прикладная информатика (в информационной сфере)», 934 «Программная инженерия» Нижний Новгород 7

2 УДК ББК В8 Ж-7 Ж 7 Жильцова ЛП, Смирнова ТГ Основы теории автоматов и формальных языков в примерах и задачах: учебно-методическое пособие [электронный ресурс] Нижний Новгород: Нижегородский госуниверситет, 7 64 с Фонд электронных образовательных ресурсов ННГУ Рецензент: к ф-м наук, доцент АЛКалашников В учебно-методическом пособии рассматриваются основные понятия и алгоритмы теории автоматов и формальных языков Особое внимание уделяется разделам, относящимся к теории конечных автоматов и регулярных языков Изучение каждой темы сопровождается необходимым теоретическим материалом и примерами решения типовых задач Предлагаются также задачи для самостоятельного решения Учебно-методическое пособие предназначено для студентов института информационных технологий, математики и механики направлений подготовки «Фундаментальная информатика и информационные технологии», «Прикладная информатика (в информационной сфере)», «Программная инженерия», изучающих курсы «Теория автоматов и формальных языков» и «Дискретная математика» УДК ББК В8 Нижегородский государственный университет им НИ Лобачевского, 7 Жильцова ЛП, Смирнова ТГ

3 Глава Формальные языки и грамматики Языки и основные операции над языками Алфавит это любое множество символов (букв) Будем рассматривать конечные алфавиты Примеры алфавитов: русский алфавит, двоичный алфавит <,>Словом (или цепочкой) в алфавите A называется конечная последовательность символов множества A Например, слово в алфавите <,>Длина слова количество символов в нем Через будем обозначать длину слова, а через число вхождений символа в Например, длина слова равна, тогда, причем 6 и 6 Пустое слово слово, не содержащее ни одного символа Будем обозначать его через Длина пустого слова равна Конкатенация (или сцепление) слов x и y приписывание слова y в конец слова x Например, x, y cd, xy cd Для любого слова x всегда x x x Обращение слова слово, записанное в обратном порядке Например, для слова x cd обращение равно dc Обращение слова x будем обозначать R x Таким образом, x R dc Язык в алфавите A произвольное множество слов в алфавите A Например, L <,, c>конечный язык в алфавите A <,, c>, содержащий три слова, L <. >бесконечный язык в алфавите < >, пустой язык, <> язык, состоящий из одного пустого слова Отметим, что и <> разные языки A множество, содержащее все слова в алфавите A, включая пустое слово Если A,, то алфавите A является подмножеством A = <. >Каждый язык L в A, те L A A множество всех непустых слов в алфавите A Пусть L и L языки в алфавите A, тогда для них определены теоретико-множественные операции: L L = x x L или x L объединение языков L и L ; L L = x x L и x L пересечение языков L и L ; 3

4 L = x x L x L L L = A L и разность языков = x x A и x L L и L ; дополнение языка L Пусть L язык в алфавите A, L язык в алфавите A, тогда язык L L =xy x L, y L называется конкатенацией (или сцеплением, произведением) языков L и L L < >нулевая степень языка L ; n n L LL, где n, n-ая степень языка L ; L итерация (звездочка или замыкание Клини) языка L n n L Позитивная итерация языка L, обозначаемая L LL L L, и L L < >n L, это язык L n Задачи и упражнения Может ли язык L или При каких условиях L и 3 Верно ли, что L L < >? L быть пустым? L конечны? 4 Для заданных языков L и L найти L L и L L : а) L, L ; j j б) L, j, L, j ; j в) L <,>,, L, j г) L,>,, и если содержит, то и начинается с, < L <,>R ; д) L,, L <, >5 Для заданных языков L и L найти L L : а) L, L ; б) L, L ; ; 4

6 9 В алфавите <,>A заданы языки L. L,, L 3 w w A, w, L 4 w w A, w и L 5 w w A, w Найти: 3 L L L а) L L, L 4, L3 L5, L4 L5; б) L L, L 3, L L4, L L5, L3 L4 ; в) L L ; L 3, L3 L4, L4 L5, L5 L4; г) L, L, L 3, L5 L4 ; д) L L, L 3L4, L 4L3; е) L, L 3, L 4 Иерархия Хомского Грамматики образуют важный класс генераторов языков Грамматикой называется система G VT, VN, P, S, где V T, VN непересекающиеся конечные множества терминальных и нетерминальных символов (терминалов и нетерминалов) соответственно; S V некоторый выделенный символ, называемый аксиомой грамматики, P конечное множество правил Терминальные символы называются также основными, а нетерминальные вспомогательными символами Каждое правило в P представляет собой пару слов,, где VT V N V Правило и содержит хотя бы один нетерминальный символ, и T V N, будем записывать в виде Для слов и из ( VT VN ) будем говорить, что непосредственно выводимо из (и записывать ), если, для некоторых, ( V V ), T N и в грамматике G имеется правило Рефлексивное транзитивное замыкание отношения назовем отношением выводимости и обозначим через Язык, порождаемый грамматикой G, определим как множество всех слов в терминальном алфавите, выводимых из аксиомы грамматики S : L G S, V : T N 6

7 Пример Рассмотрим грамматику G,, S, A, P, S, где P состоит из правил: S A A A A ( пустое слово) Нетерминальными символами являются S и A, терминальными и Покажем, что слово принадлежит L G Для этого построим вывод из аксиомы S : S A A Поэтому S Поясним, что на первом шаге к аксиоме S было применено правило S A и получено слово A ; на втором шаге к подслову A, входящему в слово A, применено правило A A, и на третьем шаге правило A В результате описанного вывода получено слово n n Можно показать, что LG n V, поэтому LG T Для обозначения n правил с одинаковой левой частью применяют сокращенную запись n n Грамматики можно классифицировать по виду их правил Пусть G V, V, P S грамматика T N, Грамматика G называется ) праволинейной, если каждое правило из P имеет вид A xb или A x, где A, B VN, x V T ; ) контекстно-свободной (или бесконтекстной), если каждое правило из P имеет вид A, где, V ; A V N N V T 3) контекстно-зависимой (или неукорачивающей), если каждое правило из P имеет вид, где 4) грамматика, не удовлетворяющая ни одному из указанных ограничений, называется грамматикой общего вида (или без ограничений) Определенные выше четыре класса грамматик и соответствующих им языков называют иерархией Хомского, где P состоит из правил: Пример Грамматика G,, S, P, S S S S, праволинейная Она порождает язык, 7

8 Пример 3 Пусть G. (, ), E, T, F, P, E, где P состоит Язык G из правил E E T T T T F F F E Грамматика G контекстно-свободная Пример вывода в этой грамматике: E E T T T F T T T F F F F L представляет собой множество арифметических выражений, построенных из символов. ( и ) Пример 4 Пусть G,, c, S, B, C, P, S 3, где P состоит из правил S SBC C CB BC B C c cc cc Грамматика G 3 контекстно-зависимая Пример вывода в этой грамматике: S SBC CBC BCC CC cc cc n n n G порождает язык c n правил 3 Пример 5 Пусть G,, S, A, B, C, D, P, S 4, где P состоит из S CD C CA C CB AD D BD D A A A A B B B B C D G 4 грамматика общего вида Пример вывода в этой грамматике: S CD CAD CBAD BAD BD BD D Грамматика 4 G порождает язык, 8

9 Пусть Задачи и упражнения L,, c Построить праволинейные грамматики для языка L, если каждое слово из L : а) начинается на букву c; б) заканчивается на букву c; в) содержит букву c; г) содержит ровно одну букву c; д) содержит не более одной буквы c; е) содержит не менее двух букв c; ж) содержит не более двух букв c; з) содержит ровно две буквы c; и) содержит подслово cc ; к) содержит подслово c; л) начинается с подслова c; м) заканчивается подсловом c Построить контекстно-свободные грамматики для следующих языков: j а) L j; j б) L j; j в) L j; j г) L j; j д) L j 3 Пусть L <,>Построить контекстно-свободную грамматику, порождающую язык L 4 Пусть L, и каждое слово из L содержит одинаковое число букв и Построить контекстно-свободную грамматику, порождающую L 5 Пусть L язык выражений из правильно расставленных скобок Построить контекстно-свободную грамматику, порождающую язык L Пояснение В выражении из правильно расставленных скобок для любого префикса выражения число открывающих скобок должно быть не меньше числа закрывающих скобок, а для выражения в целом число открывающих скобок равно числу закрывающих скобок Например, ( ( ) ( ( ) ( ) ) ) ( ) выражение из правильно расставленных скобок 6 Построить контекстно-зависимую грамматику для языка L m n m n m, n 9

10 7 Пусть L язык идентификаторов, которые могут содержать буквы латинского алфавита, j, k, l, m, n и цифры и, могут быть любой длины, но должны начинаться с буквы Построить порождающую грамматику для L 8 Пусть L язык идентификаторов, которые могут содержать буквы латинского алфавита и цифры и, должны содержать от одного до шести символов и начинаться с букв, j, k, l, m, n Построить порождающую грамматику для языка L 9 Пусть L язык вещественных констант с фиксированной точкой (примеры констант. 8, 3459) Построить порождающую грамматику для языка L Пусть L язык вещественных констант с плавающей точкой (пример константы: 665Е-7) Построить порождающую грамматику для L Описать язык, порождаемый грамматикой с правилами S SS Описать язык, порождаемый грамматикой G,, S, A, P, S P состоит из правил: S S S A A 3 Описать язык, порождаемый грамматикой G,, S, A, P, S P состоит из правил: S S S A A A A 4 Описать язык, порождаемый грамматикой G,, S, A, B, P, S где P состоит из правил: S B A B B A, где, где, 5 Описать язык, порождаемый грамматикой G,, S, A, B, P, S где P состоит из правил: S AB A B B, 6 Описать язык, порождаемый грамматикой G,, S, A, B, P, S где P состоит из правил: S AB A A B B,

11 Глава Конечные автоматы и регулярные языки Конечные автоматы и конечно-автоматные языки Недетерминированный конечный автомат это система M Q, A, q,, F, где Q конечное множество состояний автомата, A конечный алфавит, q Q начальное состояние автомата, Q : Q A функция переходов конечного автомата, F Q множество заключительных («хороших») состояний автомата Автомат M называется детерминированным, если множество ( q, ) содержит не более одного состояния для любых q Q и A Если ( q, ) всегда содержит точно одно состояние, то автомат M называется полностью определенным Конфигурация автомата M это пара ( q, w) Q A Конфигурация ( q, w) называется начальной, а пара ( q, ), где q F, называется заключительной (или допускающей) Определим на множестве всех конфигураций конечного автомата M бинарное отношение (такт работы автомата M ) следующим образом Если ( q, ) содержит q, тогда ( q, w) ( q, w) для всех w A Запись C C означает, что C C, а C k C k (для k ) что существуют такие конфигурации C,, C k, что C C для всех k Бинарное отношение определяется как рефлексивное и транзитивное замыкание отношения, те C C означает, что C C для некоторого k Будем говорить, что автомат M распознает (или допускает) слово w, если ( q, w) ( q, ) для некоторого q F Язык, определяемый (или распознаваемый, или допускаемый) автоматом M (обозначается L (M )), это множество входных цепочек, допускаемых конечным автоматом M, те L( M ) w w A и ( q, w) ( q, ) для некоторого q F k

12 Язык L называется конечно-автоматным, если для него можно построить распознающий конечный автомат Пример Недерминированный конечный автомат M, допускающий те и только те слова из и, которые заканчиваются на, может быть фор- q, q, q. q, q, где функция переходов мально задан как, определяется соотношениями: ( q, ) q, ( q,) q, q ( q, q, q, ) ( q, ) (,) ) ( q, Для слова имеем следующую последовательность возможных конфигураций: ( q, ) ( q, ) ( q,) ( q,) ( q, ) Так как ( q,) ( q, ), заключаем, что слово L(M ) Для описания конечных автоматов существуют два основных способа задания: таблица переходов и диаграмма переходов Таблица переходов недетерминированного конечного автомата представляет собой обычное табличное представление функции переходов, которая двум своим аргументам q Q и A ставит в соответствие значение ( q, ) Строки таблицы соответствуют состояниям, а столбцы входным символам На пересечении строки, соответствующей состоянию q Q, и столбца, соответствующего входному символу A, находится подмножество ( q, ) Если ( q, ), то будем говорить, что ( q, ) не определено Заметим, что в случае детерминированного конечного автомата ( q, ) представляет собой всегда одноэлементное подмножество, поэтому договоримся в этом случае вместо ( q, ) < p>писать просто ( q, ) p (без фигурных скобок) Диаграмма переходов конечного автомата есть ориентированный граф, каждая вершина которого соответствует некоторому состоянию q Q, причем вершины, соответствующие заключительным состояниям (состояниям из F ), выделяются двойным кружком Пусть q, ) < p,, p >для некоторого ( k состояния q из Q и входного символа из A, тогда диаграмма переходов должна содержать дуги, помеченные символом, из вершины q в каждую из вершин p,, p k Пример Опишем недерминированный конечный автомат M, расмотренный в примере, с помощью таблицы переходов и диаграммы переходов В таблице представлена таблица переходов этого конечного автомата, заметим, что звездочкой здесь отмечено заключительное состояние q F, а на рис изображена диаграмма переходов автомата M

13 Таблица переходов автомата M из примера Таблица Вход Состояния q q > q, > < < q < q q >q, q q q Рис Диаграмма переходов автомата из примера L,, при условии, что слово принадлежит языку L тогда и только тогда, когда в этом слове содержится подслово Для того, чтобы решить, содержит ли входная последовательность подслово, автомат M должен уметь распознавать следующие важные моменты относительно прочитанных им входных данных ) Последовательность была прочитана, тогда с этого момента автомат будет находиться только в заключительных состояниях ) Последовательность еще не была считана, и на предыдущем шаге на вход либо ничего не подавалось, либо был считан символ В этом случае автомат M не перейдет в заключительное состояние до тех пор, пока им не будут считаны символы, а затем сразу 3) Последовательность еще не была считана, но на предыдущем шаге был считан символ Значит, если на данном шаге читается символ, тогда подслово будет прочитано, и с этого момента автомат будет находиться только в заключительных состояниях Каждое из этих условий может быть представлено как некоторое состояние Условию ) соответствует начальное состояние q, условию 3) состояние q, а условию ) заключительное состояние q Пример 3 Построить конечный автомат, распознающий 3

14 Детерминированный конечный автомат M, распознающий этот язык, мо- q, q, q. q, q, где жет быть формально задан как система, функция переходов может быть задана либо таблицей переходов, либо диаграммой переходов В таблице представлена таблица переходов конечного автомата M, диаграмма переходов изображена на рис Таблица переходов автомата M из примера 3 Таблица Состояния Вход q q q q q q q q q, q q q Рис Диаграмма переходов автомата M из примера 3 Задачи и упражнения В задачах 8 требуется построить конечный автомат, распо- A,, c знающий язык L в алфавите Слово принадлежит языку L тогда и только тогда, когда в этом слове не встречается буква Слово принадлежит языку L тогда и только тогда, когда в этом слове встречается хотя бы одна буква 3 Слово принадлежит языку L тогда и только тогда, когда в этом слове буква встречается ровно два раза 4 Слово принадлежит языку L тогда и только тогда, когда в этом слове буква встречается не менее двух раз 4

15 5 Слово принадлежит языку L тогда и только тогда, когда в этом слове буква встречается четное число раз 6 Слово принадлежит языку L тогда и только тогда, когда в этом слове буква встречается нечетное число раз 7 Слово принадлежит языку L тогда и только тогда, когда в этом слове буква не встречается дважды подряд 8 Слово принадлежит языку L тогда и только тогда, когда в нем содержится подслово c 9 Слово принадлежит языку L тогда и только тогда, когда в нем содержится подслово Слово принадлежит языку L тогда и только тогда, когда в нем содержится подслово cc Слово принадлежит языку L тогда и только тогда, когда в нем подслово c встречается не более двух раз Слово принадлежит языку L тогда и только тогда, когда в этом слове первая буква совпадает с последней 3 Слово принадлежит языку L тогда и только тогда, когда в этом слове не содержится подслово c 4 Слово принадлежит языку L тогда и только тогда, когда оно содержит четное число букв 5 Слово принадлежит языку L тогда и только тогда, когда если оно содержит букву, то содержит и букву 6 Слово принадлежит языку L тогда и только тогда, когда каждая буква алфавита встречается в нем четное число раз 7 Слово принадлежит языку L тогда и только тогда, когда в этом слове буква встречается четное число раз, а буква нечетное число раз 8 Слово принадлежит языку L тогда и только тогда, когда оно заканчивается на букву, ранее встречавшуюся в слове, причем 9 Построить конечный автомат, распознающий множество слов в алфа- A,, длина которых кратна 3 вите Построить конечный автомат, распознающий множество слов в алфа- A,, длина которых кратна 4 вите 5

16 Построить конечный автомат, распознающий множество слов в алфа- A,, длина которых кратна 5 вите Построить конечный автомат, распознающий множество слов в алфа- A,, длина которых кратна 6 вите 3 Построить конечный автомат, распознающий числа, кратные 4 4 Построить конечный автомат, распознающий числа, кратные 5 5 Построить конечный автомат, распознающий числа, кратные 6 6 Построить конечный автомат, распознающий числа, кратные 7 7 Построить конечный автомат, распознающий числа, кратные 8 8 Построить конечный автомат, распознающий числа, кратные 9 Построить конечный автомат, распознающий числа, кратные 5 3 Построить конечный автомат, распознающий числа, кратные 5 3 Построить конечный автомат, распознающий числа, кратные 3 Построить конечный автомат, распознающий числа, кратные 5 Переход от недетерминированного конечного автомата к детерминированному Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недерминированными конечными автоматами, совпадает с классом языков, определяемых полностью определенными детерминированными конечными автоматами Для многих языков построить допускающий недерминированный конечный автомат гораздо легче, чем детерминированный Рассмотрим алгоритм детерминизации конечного автомата Пусть M Q, A, q,, F недетерминированный конечный автомат, распознающий язык L (M ) Требуется построить детерминированный конечный автомат M Q, A, q,, F, такой, что L( M ) L( M ) Положим Q Q, те состояниями автомата M являются подмножества состояний автомата M, q < q >, ( S, ) ( p, ) для каждого множества S Q и каждой входной буквы ps A Таким образом, чтобы найти ( S, ), мы рас- 6

17 сматриваем все состояния p в S, затем ищем те состояния Q, в которые можно попасть из состояния p по букве, после чего берем объединение множеств найденных состояний по всем состояниям p Множество заключительных состояний детерминированного конечного автомата F < S Q : S F >, те состоит из всех подмножеств состояний Q, содержащих хотя бы одно «хорошее» состояние из F Два автомата называются эквивалентными, если они распознают один и тот же язык Теорема Для любого недерминированного конечного автомата с n состояниями всегда можно построить эквивалентный ему детерминированный конечный автомат, имеющий не более чем n состояний Пример Рассмотрим недерминированный конечный автомат M, допускающий те и только те слова из и, которые заканчиваются на Этот автомат был построен в примере, диаграмма переходов этого автомата изображена на рис Построим эквивалентный ему детерминированный конечный автомат M Недетерминированный конечный автомат M имеет три состояния, поэтому детерминированный автомат M имеет не более 3 8 состояний, представляющих собой различные подмножества, составленные из элементов множества Q < q, q, q>С помощью алгоритма детерминизации построим полную таблицу переходов автомата M (см табл ) Таблица переходов автомата M из примера Вход Состояния < q >q > q, > < < q < q < q >> < q >q, > q > q, q, > < q <, q> <, q > <, q, q> < < q < q, q < q < q, q, q q q >> < q >q q > > < Таблица 7

18 < < q < q Просматривая строки этой таблицы, несложно понять, что из начального состояния < q >автомата M за конечное число шагов можно попасть только в три из восьми состояний: q >, q, > и q, q, > Остальные пять состояний из начального недостижимы, поэтому их можно исключить из таблицы Переобозначим полученные состояния: < q >обозначим за q, < q, q>за q, < q, q, q>за q Состояние q является начальным, состояние q заключительным В таблице представлена таблица переходов детерминированного автомата M с учетом лишь достижимых состояний Таблица переходов автомата M из примера Таблица Состояния Вход q q q q q q q q q На рис изображена диаграмма переходов полученного детерминированного конечного автомата, распознающего двоичные слова, которые заканчиваются на Заметим, что он имеет всего три состояния Это число случайно оказалось равным числу состояний недетерминированного автомата M, изображенного на рис, по которому строился этот детерминированный автомат M Но детерминированный конечный автомат на рис имеет шесть переходов, а автомат на рис лишь четыре q q q Рис Диаграмма переходов детерминированного автомата из примера Замечание В дальнейшем детерминированный полностью определенный конечный автомат будем называть просто конечным автоматом 8

20 4 Преобразовать недетерминированный автомат M (см табл 6) в эквивалентный ему детерминированный автомат Таблица 6 Таблица переходов автомата M из задачи 4 Вход Состояния c q < q >q q > q > q, > < < < q < q q q >q > > < 5 По недетерминированному конечному автомату, который распознает все слова в алфавите A <,, c>, заканчивающиеся на букву c, построить эквивалентный ему детерминированный автомат 6 По недетерминированному конечному автомату, распознающему все слова в алфавите A <, >, которые начинаются и заканчиваются на одну букву, построить эквивалентный ему детерминированный автомат 7 По недетерминированному конечному автомату, распознающему все слова в алфавите A <, >, заканчивающиеся на букву, которая уже встречалась ранее, построить эквивалентный ему полностью определенный детерминированный автомат 8 По недетерминированному конечному автомату, распознающему множество чисел в десятичной системе счисления, делящихся на 5, построить эквивалентный ему детерминированный конечный автомат 9 По недетерминированному конечному автомату, распознающему множество чисел в десятичной системе счисления, делящихся на 5, построить эквивалентный ему детерминированный конечный автомат < 3 Замкнутость конечно-автоматных языков относительно теоретико-множественных операций Теорема 3 Пустой язык, универсальный язык, любой конечный язык в произвольном фиксированном алфавите A,, >являются конечноавтоматными языками < n Теорема 3 Класс конечно-автоматных языков замкнут относительно основных теоретико-множественных операций объединения, пересечения и дополнения

21 Рассмотрим алгоритмы построения соответствующих автоматов Пусть L и L конечно-автоматные языки, распознаваемые конечными автоматами Q, A, q,, F соответственно M Q, A, q,, F и ) Операция объединения Автомат M Q, A, q,, F, распознающий язык L L M, строим следующим образом Полагаем Q Q Q, те каждое состояние автомата M содержит две компоненты, левую и правую Начальным состоянием нового автомата считаем q, q, а функцию пе- реходов определяем следующим образом: q, q, q,, q, j k Входное слово принадлежит объединению языков L и L тогда и только тогда, когда после его обработки автомат M окажется в состоянии, у которого либо первая компонента принадлежит совокупности F, либо вторая компонента принадлежит совокупности F Все компоненты автомата k j k F Таким образом, следует положить: F Q Q F ) Операция пересечения Автомат M Q, A, q,, F, распознающий язык L L M только последней своей компонентой Здесь получаем, что, отличается от F F M определены, его построение закончено F Пример 3 Для конечных автоматов (рис 3), распознающих языки L и L, построить конечные автоматы, распознающие объединение этих языков и их пересечение На рис 3 и 33 изображены конечные автоматы, распознающие языки L L и L L соответственно q q q q q Рис 3 Диаграммы конечных автоматов, распознающих L и L

22 q q q q q q q q q q q q Рис 3 Диаграмма конечного автомата, распознающего L UL q q q q q q q q q q q q Рис 33 Диаграмма конечного автомата, распознающего L L 3) Операция дополнения Пусть M Q, A, q,, F конечный автомат, распознающий язык L Произвольное слово A принадлежит языку L A L тогда и только тогда, когда после его обработки автомат M оказывается в состоянии, не принадлежащем F Тогда L L(N ), где N Q, A, q,, Q F, те для того, чтобы получить конечный автомат, распознающий дополнение регулярного языка, надо в автомате, распознающем исходный язык, поменять местами «хорошие» и «плохие» состояния Пример 3 Язык L распознается конечным автоматом, диаграмма переходов которого представлена на рис 34 Построить конечный автомат, распознающий его дополнение

23 q q q Рис 34 Диаграмма конечного автомата, распознающего язык L На рис 35 представлен конечный автомат, распознающий дополнение языка L q q q Отметим, что класс конечно-автоматных языков замкнут также относительно операции разности, так как L L L L Рассмотрим теперь алгоритм построения недетерминированного конечного автомата, распознающего объединение двух конечно-автоматных языков Этот алгоритм можно применять вне зависимости от того, являются ли детерминированными автоматы, определяющие исходные языки Пусть L и L конечно-автоматные языки, распознаваемые конечными автоматами M Q, A, q,, F и M Q, A, q,, F соответ- ственно Для построения M добавим в диаграмму новое состояние q По каждой букве x A из состояния q проводим две дуги с надписанной буквой x: q, q, x и q, q, x Начальным состоянием M является состояние q, а множеством заключительных состояний F автомата является множество q F Рис 35 Диаграмма конечного автомата, распознающего язык L F F В случае, если либо q F, либо q F, тогда 3

24 Пример 33 Построить конечный автомат, распознающий числа, каждое из которых кратно или 5, над алфавитом A <,,3,5>На рис 36 представлена диаграмма переходов детерминированного конечного автомата M, распознающего числа, кратные, а на рис 37 диаграмма автомата M, распознающего числа, кратные 5 3, 5,, 3, 5 q, 3, 5 q q, 5, 3 q Рис 36 Диаграмма переходов M Рис 37 Диаграмма переходов M 3, 5, q 3, 5, q, 3, 5 q, 3, 3, 5, 5 q, 5, 3 q Рис 38 Диаграмма автомата, распознающего числа, кратные или 5 На рис 38 построена диаграмма переходов недетермированного конечного автомата, распознающего множество десятичных чисел над алфавитом A <,,3,5>, каждое из которых кратно или 5 Задачи и упражнения 3 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 39 Построить конечные автоматы, распознающие языки L L, L L, L L и L L 4

25 q q q q q Рис 39 Диаграммы переходов автоматов к задаче 3 3 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 3 Построить конечные автоматы, распознающие языки L L, L L, L L и L L q q q q q q Рис 3 Диаграммы переходов автоматов к задаче 3 q q q q q Рис 3 Диаграммы переходов автоматов к задаче 33 5

26 33 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 3 Построить конечные автоматы, распознающие языки L L, L L, L L и L L 34 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 3 Построить конечные автоматы, распознающие языки L L, L L, L L и L L q q q q q q Рис 3 Диаграммы переходов автоматов к задаче 34 4 Замкнутость конечно-автоматных языков относительно конкатенации, возведения в степень и итерации Теорема 4 Класс конечно-автоматных языков замкнут относительно операции конкатенации Пусть L и L конечно-автоматные языки, распознаваемые конечными автоматами M Q, A, q,, F и Q, A, q,, F соответственно При построении конечного автомата M M Q, A, q,, F, распознающего конкатенацию языков L L, возможны следующие случаи F Случай q, те пустое слово не входит в язык L Через W обозначим совокупность всех дуг (вместе с надписанными над ними буквами) в диаграмме переходов автомата M, которые своими концами имеют вершины подмножества F, те все дуги вида q q, где q j F Для каждой при-, j 6

27 надлежащей множеству W дуги q, q j с надписанной над ней буквой x входного алфавита строим дугу-дубликат q,q с той же надписанной буквой Так реализуется «сцепка» диаграмм переходов конечных автоматов M и M, результатом которой является диаграмма переходов конструируемого недетерминированного конечного автомата M, положим теперь q q, F F Согласно выполненному построению, до перехода по некоторой дугедубликату в состояние q конечный автомат M функционирует как автомат M, после перехода в q q и до завершения работы как M Случай q F, F, те в язык L входит пустое слово, а в язык L не входит Для этого случая «сцепка» диаграмм переходов конечных ав- томатов M и M, результатом которой является диаграмма переходов конструируемого недетерминированного конечного автомата M, реализуется в два шага шаг Проводятся все дуги-дубликаты, как для случая шаг Для каждой дуги q q, с надписанной над ней буквой x входного алфавита проводится дополнительная дуга q, q с той же надписанной над ней буквой x Как и в случае, q и q q F F Случай 3 q F, F, те пустое слово входит и в язык L, и в язык L, значит, пустое слово принадлежит и конкатенации языков L L Алгоритм построения недетерминированного автомата M в этом случае реализуется в два шага, как и в случае Однако, здесь q и F F q q Пример 4 Языки L и L распознаются конечными автоматами, диаграммы которых представлены на рис 4 Построить конечный автомат, распознающий конкатенацию этих языков q q q q q Рис 4 Диаграммы переходов конечных автоматов, распознающих L и L 7

28 q q q q q Рис 4 Диаграмма переходов конечного автомата, распознающего L L F Так как q, имеем случай На рис 4 представлена диаграмма переходов недетерминированного конечного автомата, распознающего конкатенацию языков L L Пример 4 Для конечных автоматов (рис 43), распознающих языки L и L, построить конечный автомат, распознающий конкатенацию этих языков q q q q q Рис 43 Диаграммы переходов конечных автоматов, распознающих L и L Так как q F, q F, имеем случай На рис 44 представлена диаграмма переходов недетерминированного конечного автомата, распознающего конкатенацию языков L L q q q q q Рис 44 Диаграмма переходов конечного автомата, распознающего L L 8

29 Пример 43 Для конечных автоматов (рис 45), распознающих языки L и L, построить конечный автомат, распознающий конкатенацию этих языков q q q q q Рис 45 Диаграммы переходов конечных автоматов, распознающих L и L F, q F Так как q, имеем случай 3 На рис 46 представлена диаграмма переходов недетерминированного конечного автомата, распознающего конкатенацию языков L L q q q q q Рис 46 Диаграмма переходов конечного автомата, распознающего L L Теорема 4 Класс конечно-автоматных языков замкнут относительно операции возведения в любую целую неотрицательную степень Построение конечного автомата, реализующего язык L, осуществляется по алгоритму построения конечного автомата, распознающего конкатенацию LL, соответственно построение конечного автомата, распознающего язык L при любом n 3, осуществляется по алгоритму построения конечного автомата, распознающего конкатенацию L n L Пример 44 По диаграмме конечного автомата (рис 47), распознающего язык L, построить конечный автомат, распознающий язык L 3 3 Построение конечного автомата, распознающего язык L, произведем в два этапа n 9

30 q q Рис47 Диаграмма автомата к задаче 44 Сначала построим диаграмму переходов конечного автомата, распознающего язык L (рис 48) На рис 49 представлена диаграмма переходов конечного автомата, распознающего язык L 3 q q q q Рис48 Диаграмма переходов автомата, распознающего L q 3 q q q q 3 q Рис 49 Диаграмма переходов автомата, распознающего L 3 Теорема 43 Класс конечно-автоматных языков замкнут относительно операции итерации Пусть L конечно-автоматный язык и M Q, A, q,, F конечный автомат, распознающий L 3

31 Рассмотрим алгоритм построения конечного автомата (вообще говоря, недетерминированного), распознающего язык L Возможны два случая Случай Начальное состояние q автомата M невозвратное, те отсутствуют дуги, входящие в q Через W обозначим совокупность всех дуг (вместе с надписанными над ними буквами) в диаграмме переходов автомата M, которые своими концами имеют вершины подмножества F, те все дуги вида q,, где q j F Для каждой принадлежащей множеству W дуги q j q, q j с надписанной над ней буквой x входного алфавита строим дугудубликат q, q с той же надписанной буквой Начальным состоянием автомата M L ) считаем q, это же состояние считаем единственным «хорошим» ( ( состоянием в M L ) Следует заметить, что, если в качестве «хороших» состояний автомата M L ) считать множество F исходного автомата M, тогда ( получаемый автомат распознает язык L Случай Начальное состояние q автомата M не является невозвратным Построение автомата, распознающего язык L, производим следующим образом Шаг Для начального состояния q автомата M вводим дублирующее состояние q Все дуги (с надписанными над ними буквами), которые в диа- грамме исходного автомата входят в вершину q, переориентируем в q, при этом каждая петля q, q преобразуется в дугу q, q Для каждой имеющейся дуги q, q j, где q j Q, с надписанной над ней буквой, проводим дугу q, q j с той же надписанной буквой, при этом для каждой ранее имевшей- ся петли q, q проводится, с той же надписанной буквой, петля q, q Множество «хороших» состояний построенного автомата M считаем совпадающим с множеством «хороших» состояний исходного автомата M, причем, если q F, тогда и q F Шаг Далее следует применить алгоритм, описанный для случая невозвратного начального состояния конечного автомата Замечание Если начальное состояние q не является невозвратным и q F, то при построении конечного автомата, распознающего итерацию языка, можно сразу переходить к шагу 3

32 L,, c язык, состоящий из слов, которые начинаются на букву c и в каждом из которых буква c встречается ровно два раза Построить конечный автомат, распознающий язык L Пример 45 Пусть. c c c c q q q q q q c, Рис 4 Автомат, распознающий L Рис 4 Автомат, распознающий L На рис 4 приведена диаграмма переходов конечного автомата, распознающего язык L Так как состояние q исходного автомата является невозвратным, имеем случай На рис 4 приведена диаграмма переходов конечного автомата, распознающего язык L Непустое слово принимается ав- томатом, распознающим итерацию языка L, тогда и только тогда, когда буква c встречается в нем любое четное, отличное от нуля, число раз Пример 46 Язык L распознается конечным автоматом, диаграмма которого представлена на рис 47 Построить конечный автомат, распознающий язык L Так как состояние q исходного автомата не является невозвратным, имеем случай На рис 4 приведена диаграмма переходов конечного автома- q q q q q q Рис 4 Диаграмма после шага Рис 43 Автомат, распознающий L 3

33 та, распознающего язык L, после выполнения шага, а на рис 43 изображена диаграмма переходов конечного автомата, распознающего язык L Задачи и упражнения 4 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 44 Построить конечный автомат, распознающий язык L L Рассмотреть следующие варианты задания совокупностей заключительных состояний исходных автоматов: а) F q, q, q б) F q, q, q в) F q, q,q F ; F ; F q q q q q q Рис 44 Диаграммы автоматов, распознающих L и L к задаче 4 4 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 45 Построить конечный автомат, распознающий язык L L Рассмотреть следующие варианты задания совокупностей заключительных состояний исходных автоматов: а) F q, q, F q3; б) F q, q, q,q F ; 3 33

34 в) F q, q, q, q,q F 3, q, q q q q q 3 q Рис 45 Диаграммы автоматов, распознающих L и L к задаче 4 43 Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 46 Построить конечный автомат, распознающий язык L L Рассмотреть следующие варианты задания совокупностей заключительных состояний исходных автоматов: а) F q, q3, F q ; б) F q, q, q в) F q,q, F q F ; q q q q 3 q q Рис 46 Диаграммы автоматов, распознающих L и L к задаче Языки L и L распознаются конечными автоматами, диаграммы переходов которых изображены на рис 47 Построить конечный автомат, распо- 34

35 знающий язык L L Рассмотреть следующие варианты задания совокупностей заключительных состояний исходных автоматов: а) F q, q3, F q; б) F q, q, F q ; в) F q,q, q,q F q q q q 3 q q q Рис 47 Диаграммы автоматов, распознающих L и L к задаче Язык L распознается конечным автоматом, диаграмма переходов которого изображена на рис 48 Построить конечный автомат, распознающий язык 3 L, если множество заключительных состояний автомата: F ; а) q б) F q, q q q q q c q q Рис 48 Диаграмма к задаче 45 Рис 49 Диаграмма к задаче 46 35

36 46 Язык L распознается конечным автоматом, диаграмма переходов которого изображена на рис 49 Построить конечный автомат, распознающий язык 3 L, если множество заключительных состояний автомата: F q,q ; а) б) F q 47 Язык L распознается конечным автоматом, диаграмма переходов которого изображена на рис 4 Построить конечный автомат, распознающий итерацию этого языка, если множество заключительных состояний автомата: а) F q,q 4 ; б) F q, q ; в) F q, q 3 q q q 4 c c q q 3 c c Рис 4 Диаграмма переходов автомата к задаче 47 q q q q 3 Рис 4 Диаграмма переходов автомата к задаче 48 36

37 48 Язык L распознается конечным автоматом, диаграмма переходов которого изображена на рис 4 Построить конечный автомат, распознающий итерацию этого языка, если множество заключительных состояний автомата: а) F q, q 3 ; б) F q, q ; в) F q, q 3 5 Лемма о разрастании для конечно-автоматных языков Теорема 5 Пусть L конечно-автоматный язык Существует такая константа p, что если w L и w p, то слово w можно записать в виде xyz, где y p и xy z L для всех Лемма о разрастании полезна для доказательства того, что некоторые языки не являются конечно-автоматными n n Пример 5 Используя лемму, докажем, что язык L n является конечно-автоматным Доказательство проведем методом от противного Предположим, что L p p конечно-автоматный язык Рассмотрим слово w, где p константа из леммы Очевидно, w p Поэтому w можно представить в виде w xyz, где y Для y возможны следующие два случая: а) k y для некоторого k, для определенности предположим, что y входит в левую часть слова w По лемме о разрастании слово не w xy z также принадлежит языку L Но в слове w число вхождений буквы слева больше числа вхождений справа, следовательно, w L б) y содержит букву По лемме слово w xz должно принадлежать L Но в w нет буквы, поэтому w L В обоих случаях получили противоречие с предположением о том, что L конечно-автоматный язык Следовательно, язык L не является конечноавтоматным Задачи и упражнения В задачах 5 54 доказать, что язык L не является конечно-автоматным: 37

38 n n 5 L n n m 5 L n, m, n m n m 53 L n, m, n m n m 54 L n, m, n m n m k 55 L c n, m, k, n m n m k 56 L c n, m, k, n m, n k, m k n m k 57 L c n, m, k, n m k 58 L <, и содержит одинаковое число нулей и единиц>59 <, >L R 5 <, >L n 5 L n 3 n 5 L n p 53 L < p простое число>n 54 L < n, k. >k 6 Минимизация конечного автомата Пусть M Q, A, q,, F конечный автомат Конечный автомат M называется минимальным, если не существует эквивалентного ему автомата с меньшим числом состояний Состояние q конечного автомата M называется недостижимым, если не существует слова, переводящего автомат из начального состояния в состояние q Слово A различает состояния q и q, если q, q 3. 4, q принадлежит F, а другое q q и одно из состояний q 3 и 4 нет Будем говорить, что состояния q и q k неразличимы (и писать k q q ), если не существует слова A, различающего q и q, для ко- 38

39 торого k Будем говорить, что состояния q и q неразличимы (и писать q ), если они k неразличимы для любого k q Автомат M называется приведенным, если в Q нет недостижимых состояний и нет двух неразличимых состояний Теорема 6 Приведенный автомат является минимальным Алгоритм построения минимального конечного автомата включает следующие этапы: Поиск и удаление недостижимых состояний Построение классов эквивалентности по отношению 3 Построение минимального автомата, состояниями которого являются классы эквивалентности Пример 6 Рассмотрим конечный автомат Q q, q, q, q, q, q q, A,, 3 4 5, определена таблицей 6 6 Таблица переходов автомата M из примера 6 M Q, A, q,, F, где F q,q 4 и функция переходов Состояния Вход q q q 3 q q q q q 3 q 4 q 3 q 3 q 4 q q 4 q q 5 q q 6 q q 6 q 5 4 Таблица 6 ) Состояния множества < q 5, q 6 >недостижимы из q, так как в них можно попасть только из того же множества < q 5, q 6 >После удаления состояний q 5 и q 6 получим таблицу 6 В общем случае недостижимые состояния могут быть найдены методом поиска в ширину ) Найдем классы эквивалентности отношения Для этого последовательно будем строить классы эквивалентности отношения до тех пор, пока не выполнится условие k k k для k. 39

40 Таблица переходов без недостижимых состояний Состояния Вход q q q 3 q q q q q 3 q 4 q 3 q 3 q 4 q q 4 q Таблица 6 При k всегда имеем два класса: F (класс ) и Q F (класс ) При k построим таблицу 63, в которой для каждой буквы A и каждого состояния q Q в столбце указан номер класса, которому принадлежит состояние ( q, ) A Определение классов эквивалентности при k= q q 4 q q q 3 Таблица 63 По содержимому столбцов определяем, что класс распадается на два новых класса эквивалентности Поэтому для k получаем следующие классы эквивалентности: q,q 4 (класс ), < q >(класс ), q,q 3 (класс 3) Для k построим таблицу 64 Таблица 64 Определение классов эквивалентности при k= A 3 q q 4 q q q По таблице 64 устанавливаем, что новых классов эквивалентности не появилось, поэтому 3) В минимальном автомате три состояния p, q и r, соответствующих классам эквивалентности: < >q, q, q,q 3,q 4 Начальное состояние 4

41 Таблица переходов минимально- < >q го автомата представлена в таблице 65 q, заключительное состояние,q 4 Таблица переходов минимального автомата Вход Состояния p q q q q r r q r Таблица 65 На рис6 изображена диаграмма построенного минимального автомата p, q r Рис6 Диаграмма переходов минимального автомата Задачи и упражнения 6 L множество десятичных чисел над алфавитом <,,3>, кратных 6 В предположении, что пустое слово принадлежит L, построить минимальный автомат, допускающий L 6 L множество десятичных чисел над алфавитом <,,3>, кратных 6 В предположении, что L, построить минимальный автомат, допускающий L 63 L множество десятичных чисел над алфавитом <. 3,4>, кратных 8 В предположении, что пустое слово принадлежит L, построить минимальный автомат, допускающий L 64 L множество десятичных чисел над алфавитом <,>, кратных В предположении, что пустое слово принадлежит L, построить минимальный автомат, допускающий L 65 L множество десятичных чисел над алфавитом <,,3>, сумма цифр которых кратна 6 В предположении, что пустое слово принадлежит L, построить минимальный автомат, допускающий L 4

44 дит за класс конечно-автоматных языков; алгоритмы синтеза конечных автоматов, распознающих получаемые посредством выполнения перечисленных операций языки, уже построены Задачи и упражнения В задачах 7 7 требуется решить задачу синтеза конечного автомата по заданному регулярному выражению R R c 7 7 R c R c c c R c c 75 R c 76 R c R c c c 77 R c c c R c c 7 R c c 7 R c c 7 R c cс c c 73 R с c c c 74 R c cd c c 75 R c c c 76 c c c R 77 R c c 78 R c c c c 44

Источник

Видео

Введение в теорию автоматов и вычислений. 1.8 пример автомата. язык автомата

Введение в теорию автоматов и вычислений. 1.8 пример автомата. язык автомата

Формальные языки и трансляции 1. Слова и языки. Конечные автоматы

Формальные языки и трансляции 1. Слова и языки. Конечные автоматы

Как управлять миром, изучив всего одну простую модель!

Как управлять миром, изучив всего одну простую модель!

Формальные языки 1. Конечные автоматы

Формальные языки 1. Конечные автоматы

Введение в теорию автоматов и вычислений. 1.9 пример автомата. язык автомата

Введение в теорию автоматов и вычислений. 1.9 пример автомата. язык автомата

ТА Лекция 2 Конечный детерминированный автомат

ТА Лекция 2 Конечный детерминированный автомат

Почему липнут электроды и как с этим бороться!? / УОНИ 13/55

Почему липнут электроды и как с этим бороться!? / УОНИ 13/55

ЛР №11, конечные автоматы

ЛР №11, конечные автоматы

Формальные языки и трансляции 6. Автомат с магазинной памятью

Формальные языки и трансляции 6. Автомат с магазинной памятью

Какой уровень языка ПРОГРАММИРОВАНИЯ должен быть у АВТОМАТИЗАТОРА

Какой уровень языка ПРОГРАММИРОВАНИЯ должен быть у АВТОМАТИЗАТОРА
Поделиться или сохранить к себе:
Добавить комментарий

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