МАТЕМАТИЧЕСКИЕ МЕТОДЫ СИСТЕМНОГО АНАЛИЗА И УПРАВЛЕНИЯ УДК 519.688 МЕТОД СЛУЧАЙНОЙ ГЕНЕРАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ И ПРОВЕРКА РЕПРЕЗЕНТАТИВНОСТИ СГЕНЕРИРОВАННЫХ СТРУКТУР С. В. <...> Пивнева, О. А. Рогова Тольяттинский государственный университет Поступила в редакцию 03.11.2010 г. Аннотация: В статье рассматривается алгоритм случайной генерации недетерминированного конечного автомата, наиболее подходящего для выбранной предметной области. <...> К сгенерированным структурам применяются конкретные характеристики данной предметной области и проверяется их репрезентативность. <...> Этот шаг обычно «идейно близок» к проверке репрезентативности входных данных, но нередко соответствующие алгоритмы «для проверки адекватности» существенно сложнее. <...> Случайная генерация комбинаторных структур позволяет проверять алгоритмы, основанные на этой структуре, и исследовать поведение этих структур. <...> Сгенерированные объекты адекватны тем потребностям, которые возникают в реальных задачах. <...> Например, при описании контекстно-свободных языков с помощью конечных автоматов. <...> В реальных задачах требуется достаточно большое количество состояний конечного автомата, поэтому необходимо генерировать недетерминированные конечные автоматы с целью применения к ним конкретных характеристик, которые впоследствии применяются, например, в некоторых алгоритмах LR-анализа. <...> МЕТОД СЛУЧАЙНОЙ ГЕНЕРАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ ВЕСТНИК ВГУ, СЕРИЯ: СИСТЕМНЫЙ АНАЛИЗ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, 2010, № 2 © Пивнева С. В., Рогова О. А., 2010 В нашей работе рассматривается случайный метод генерации недетерминированного конечного автомата Ван Зиджла, основанный на случайных битовых потоках [1]. <...> С помощью этого метода с равновероятными битовыми потоками можно успешно сравнивать различные представления регулярных языков. <...> Но структуры, сгенерированные данным методом не соответствуют требованиям выбранной предметной <...>