Лабораторная работа
7 лабораторных работ по предмету "Теория формальных языков, грамматик и автоматов". Вариант 3
в среде программирования Visual C# .NET 2015 (Вижл Си Шарп)
Программа и описание

Среда программирования: Visual C# .NET 2015
Название работы: 7 лабораторных работ по предмету "Теория формальных языков, грамматик и автоматов". Вариант 3
Вид работы: Лабораторная работа
Тематика работы: Алгоритмы, Работа с текстом, Структуры
Объем программы: 5 (по десятибалльной шкале)
Уровень сложности: 5 (по десятибалльной шкале)
Разработчик (автор): Программист сайта kursovik.com (письмо автору)
Ключевые слова: Распознавание типов, формальные языки, грамматика, классификация Хомского, конечный автомат, регулярная грамматика, детерминированный автомат, результирующий граф, недостижимые состояния, конечные состояния, эквивалентные преобразования, контекстно-свободные грамматики, КС-грамматики, бесполезные символы, недостижимые символы, цепные правила, левая факторизация правил, прямая левая рекурсия, магазинная память, МП-автомат, LL(k)–грамматика, LL(1)-грамматика, распознаватель для грамматик, простое предшествование, сдвиг-свертка, контекстно-свободная грамматика, матрица простого предшествования
Функции программы:
Цель: закрепить понятия «алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»; сформировать умения и навыки распознавания типов формальных языков и грамматик по классификации Хомского, построения эквивалентных грамматик.
Задание:
При выполнении лабораторной работы следует реализовать следующие действия:
1) составить грамматику, порождающую формальный язык, заданный в соответствии с вариантом;
2) определить тип формальной грамматики и языка по классификации Хомского;
3) разработать программное средство, распознающее тип введенной пользователем грамматики по классификации Хомского.
Вариант 3.
L(G)={0n(10)m | n, m-0}
Лабораторная работа №2.
Тема: «Построение конечного автомата по регулярной грамматике»
Цель: закрепить понятия «регулярная грамматика», «недетерминированный и детерминированный конечный автомат»; сформировать умения и навыки построения конечного автомата по регулярной грамматике и преобразования недетерминированного конечного автомата к детерминированному конечному автомату.
Постановка задачи
Вариант 3
Дана регулярная грамматика
G = ({K, L, M, N}, {a, b, +, -, -}, P, K), где P:
1) K-aL | bM; 2) L--N | -M; 3) M-+N; 4) N-aL | bM | -.
Разработать программное средство, реализующее следующие функции:
1) ввод произвольной формальной грамматики с клавиатуры и проверка ее на принадлежность к классу регулярных грамматик;
2) построение по заданной регулярной грамматике конечного автомата;
3) преобразование недетерминированного конечного автомата к детерминированному конечному автомату;
4) вывод графа результирующего конечного автомата на экран.
Лабораторная работа №3.
Тема: «Минимизация конечных автоматов»
Цель: закрепить понятия «недостижимые состояния автомата», «эквивалентные состояния автомата», «минимальный конечный автомат»; сформировать умения и навыки минимизации детерминированного конечного автомата.
Постановка задачи
Вариант 3
Индивидуальное задание
Разработать программное средство, реализующее следующие функции:
1) ввод исходного конечного автомата и вывод на экран его графа;
2) устранение недостижимых состояний конечного автомата;
3) исключение эквивалентных состояний конечного автомата;
4) вывод на экран графа минимального конечного автомата.
Разработать серию контрольных примеров для тестирования реализованных алгоритмов.
Лабораторная работа №4.
Тема: «Эквивалентные преобразования контекстно-свободных грамматик»
Цель: закрепить понятия «эквивалентные грамматики», «приведенная КС-грамматика»; сформировать умения и навыки эквивалентных преобразований контекстно-свободных грамматик.
Постановка задачи
Вариант 3
Индивидуальное задание:
G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
Разработать программное средство, автоматизирующее процесс эквивалентного преобразования КС-грамматик. Программное средство должно выполнять следующие функции:
1) организация ввода грамматики и проверка ее на принадлежность к классу КС-грамматик;
2) проверка существования языка КС-грамматики;
3) реализация эквивалентных преобразований грамматики, направленных на удаление:
а) бесполезных символов;
б) недостижимых символов;
в) e-правил;
г) цепных правил;
д) левой факторизации правил;
е) прямой левой рекурсии.
Лабораторная работа №5.
Тема: «Построение автомата с магазинной памятью по контекстно-свободной грамматике»
Цель: закрепить понятия «автомат с магазинной памятью (МП-автомат)», «расширенный МП-автомат», «конфигурация МП-автомата»; «строка и язык, допускаемые МП-автоматом»; сформировать умения и навыки построения МП-автомата и расширенного МП-автомата по КС-грамматике, разбора входной строки с помощью МП-автомата.
Постановка задачи
Вариант 3
Индивидуальное задание:
Контекстно-свободная грамматика
G = ({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
Разработать программное средство, реализующее следующие функции:
а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;
б) построение МП-автомата по КС-грамматике;
в) построение расширенного МП-автомата по КС-грамматике.
Продемонстрировать разбор некоторой входной строки с помощью построенных автоматов для случая:
а) входная строка принадлежит языку исходной КС-грамматики и допускается МП-автоматом;
б) входная строка не принадлежит языку исходной КС-грамматики и не принимается МП-автоматом.
Лабораторная работа №6.
Тема: «Моделирование функционирования распознавателя для LL(1)-грамматик»
Цель: закрепить понятие «LL(k) –грамматика», необходимые и достаточные условия LL(k) –грамматики; сформировать умения и навыки построения множеств FIRST(k, α) и FOLLOW(k, α), распознавателя для LL(1)-грамматик.
Постановка задачи
Вариант 3
Индивидуальное задание:
Контекстно-свободная грамматика
G = ({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
Разработать программное средство, реализующее следующие функции:
Разработать программное средство, автоматизирующее процесс разбора цепочек для LL(1)-грамматик. Программное средство должно выполнять следующие функции:
1) реализация ввода произвольной КС-грамматики;
2) построение множеств FIRST(1, A) и FOLLOW(1, A) для каждого не-терминального символа грамматики;
3) проверка необходимого и достаточного условия LL(1) для введенной КС-грамматики;
4) моделирование функционирования распознавателя для LL(1)-грамматик.
Составить набор контрольных примеров для случаев:
а) введенная КС-грамматика не является LL(1)-грамматикой;
б) исходная КС-грамматика является LL(1)-грамматикой, но входная строка не принадлежит языку грамматики;
в) заданная КС-грамматика является LL(1)-грамматикой и введенная строка принадлежит языку грамматики.
Разбор цепочек показать с помощью таблицы, строки вывода и дерева вывода.
Лабораторная работа №7.
Тема: «Моделирование функционирования распознавателя для грамматик простого предшествования»
Цель: закрепить понятие «грамматика простого предшествования»; сформировать умения и навыки построения множеств L(A) и R(A), матрицы предшествования символов грамматики и распознавателя для грамматик простого предшествования методом «сдвиг-свертка».
Постановка задачи
Вариант 3
Индивидуальное задание:
Контекстно-свободная грамматика
G = ({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
Разработать программное средство, реализующее следующие функции:
Разработать программное средство, автоматизирующее процесс разбора цепочек для грамматик простого предшествования. Программное средство должно выполнять следующие функции:
1) ввод произвольной грамматики;
2) построение множеств L(A) и R(A) для каждого нетерминального символа грамматики;
3) формирование матрицы простого предшествования для введенной грамматики;
4) проверка условия простого предшествования для данной грамматики;
5) моделирование функционирования распознавателя для грамматик простого предшествования.
Составить набор контрольных примеров для случаев:
а) введенная грамматика не является грамматикой простого предшествования;
б) исходная грамматика является грамматикой простого предшествования, но анализируемая строка не принадлежит языку грамматики;
в) заданная грамматика является грамматикой простого предшествования и входная строка принадлежит языку грамматики.
Разбор цепочек представить в виде таблицы, строки вывода и дерева вывода.
+ 500 руб
+ 1000 руб
+ 1000 руб
+ 1000 руб
+ 1000 руб
+ 1000 руб
+ 1000 руб
+ 18.70 Бел.руб
+ 37.50 Бел.руб
+ 37.50 Бел.руб
+ 37.50 Бел.руб
+ 37.50 Бел.руб
+ 37.50 Бел.руб
+ 37.50 Бел.руб
+ 3150 тенге
+ 6300 тенге
+ 6300 тенге
+ 6300 тенге
+ 6300 тенге
+ 6300 тенге
+ 6300 тенге
Описание (отчет): Есть на 52 страниц, посмотреть оглавление
На данный момент (17 мая 2025) на выполнении находится 40 заказов.
Количество программистов, занятых выполнением текущих заказов: 15.
В текущем месяце (май 2025) нами уже выполнено 29 заказов.
В текущем году (2025) нами уже выполнено 285 заказов.
В прошлом году (2024) нами было выполнено 763 заказа.
В позапрошлом году (2023) нами было выполнено 777 заказов.
Количество активных программистов на сайте: 59.
Загруженность отдела заказами: 49%.
Размер архива 1619 Кб, все фaйлы прoверены aнтивирусом Кaсперского. Скачать





































































































К программе прилагается:
- 1) отчет - 2 стр.
- 2) отчет - 34 стр.
- 3) отчет - 29 стр.
- 4) отчет - 30 стр.
- 5) отчет - 37 стр.
- 6) отчет - 46 стр.
- 7) отчет - 52 стр.
Перед покупкой готовой работы не забудьте проверить её оригинальность. Запросить у администратора проверку текущей оригинальности работы по версии системы Антиплагиат.РУ
ВНИМАНИЕ ! Если данный отчет Вам не подходит, то Вы можете заказать написание нового отчета (согласно Вашему оглавлению) автору данной программы. Чтобы узнать цену, нажмите на эту ссылку.

Лабораторная работа №1 Задание. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 Решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2



Лабораторная работа №2 1 Тема и цель лабораторной работы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 2 Постановка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 3 Формальная модель задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 4 Структурная организация данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 5 Спецификация основных процедур и функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .