Другие журналы

Белоусов Алексей Иванович

Теорема Майхилла-Нероуда в теории формальных языков и ее применение
Инженерный вестник # 07, июль 2016
УДК: 519.76+372.851
В статье, носящей научно-методический характер рассматривается один из классических результатов теории формальных языков – теорема Майхилла-Нероуда. Излагается пересмотренное доказательство теоремы с дополнительными акцентами на некоторых подробностях, связанных с алгоритмом минимизации конечных автоматов и с конструкцией конечного автомата при доказательстве достаточности условия теоремы. Рассматриваются также некоторые методы анализа языков на предмет их регулярности/нерегулярности, особенно, когда лемма о разрастании не применима. Продемонстрировано использование теоремы при доказательстве регулярности языка, полученного как частное от деления регулярного языка на произвольный. На базе примеров анализа языков на предмет доказательства их нерегулярности делается некое обобщение: рассматривается специальный класс отношений на множестве натуральных чисел, и на этой основе доказывается одно достаточное условие нерегулярности для весьма широкого класса языков.
О методике изложения некоторых разделов теории формальных языков: леммы о разрастании
Инженерный вестник # 12, декабрь 2015
УДК: 519.76+372.851
В статье подробно изложены доказательства трех теорем: леммы Огдена о КС-языках, леммы о разрастании для линейных языков и утверждения о регулярности любого КС-языка в однобуквенном алфавите. В рамках излагаемой методики рассмотрения всех лемм о разрастании, одного из ключевых разделов теории формальных языков, особый акцент сделан на анализе нетривиальных примеров, обычно не рассматриваемых в известных руководствах. К числу таких примеров принадлежат примеры языков, в которых числа вхождений символов удовлетворяют некоторым неравенствам, языков, удовлетворяющих леммам о разрастании, но не принадлежащих соответствующему классу языков. На одном важном примере обсуждается метод анализа, названный «методом факториальной накачки» и основанный на лемме Огдена. В целом, предлагаемая система изложения позволяет глубже оценить возможности лемм о разрастании в плане анализа языков на предмет их принадлежности или непринадлежности к тому или иному классу языков.
О методике изложения некоторых разделов комбинаторики: теория Пойа
Инженерный вестник # 02, февраль 2015
УДК: 519.101+372.851
Рассматривается методика изложения одного из разделов перечислительной комбинаторики, известной как теория Пойа. Предлагаются пересмотренные, существенно упрощенные и в то же время максимально детализированные доказательства леммы Бернсайда и теоремы Пойа о структурном перечне классов эквивалентности функций разметки. В отличие от известных руководств, в которых доказательство основных положений весьма сложно и малодоступно студентам технических вузов, предлагаемая методика позволяет прозрачно и не жертвуя строгостью изложить основные определения и теоремы. Особое внимание уделяется специальному классу функций разметки, называемых ступенчатыми, подробный анализ которых и лежит в основе нового доказательства теоремы Пойа.
О методике изложения некоторых разделов комбинаторики: линейные рекуррентные соотношения
Инженерный вестник # 11, ноябрь 2014
УДК: 519.101+372.851
Предлагается последовательность изложения теории линейных рекуррентных соотношений, читаемой в курсе дискретной математики для студентов программистских специальностей, при которой систематически прослеживается структурное соответствие между методами решения линейных рекуррентных соотношений с постоянными коэффициентами и методами решения обыкновенных линейных дифференциальных уравнений. В отличие от известных руководств по комбинаторному анализу подробно обсуждаются некоторые вопросы, затрагиваемые лишь бегло или вовсе не затрагиваемые (например, соотношения с тригонометрической неоднородностью). Рассматриваемая методика изложения, при строгости и доходчивости изложения, позволяет выявить для студентов связи между различными разделами курса математики. Предлагается два уровня изложения: базовый и повышенной трудности, в котором подробно рассматриваются доказательства утверждений, лишь формулируемых в базовом курсе. Для некоторых утверждений даны новые доказательства.
Ладейные полиномы в многомерных пространствах
Инженерное образование # 10, октябрь 2012
DOI: 10.7463/1012.0463238
В статье рассматривается обобщение известной из комбинаторики конструкции ладейных полиномов на случай  досок произвольной размерности. Получены основные формулы и приведены примеры их применения на практике. Разработан алгоритм вычисления ладейных полиномов.
Мультиграфовое представление автоматов с магазинной памятью
Инженерное образование # 09, сентябрь 2012
DOI: 10.7463/0912.0460973
В статье рассматривается представление автоматов с магазинной памятью (МП-автоматов) в виде ориентированных мультиграфов. Дано определение языка МП-автомата, представленного своим мультиграфом,  и доказана равносильность этого определения с известным. В терминах мультиграфового представления рассмотрены также некоторые свойства МП-автоматов, в частности, доказана регулярность множества всех магазинных цепочек.
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)