Отчёт по Контрольной Работе 1

МИНИСТРЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОУ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИМ. Р.Е. АЛЕКСЕЕВА

ИНСТИТУТ ЭКОНОМИКИ И УПРАВЛЕНИЯ

КАФЕДРА " Прикладная математика и информатика"

Дисциплина "Формальные языки и алгоритмы"

Отчет

по контрольной работе №1

Выполнил: Наймушин Сергей Михайлович

студент группы: 20-САИ

Проверил: Ковригин Дмитрий Анатольевич

Нижний Новгород

2021

Задача: Исключить левую рекурсию в грамматике.

S -> A 1

| B 0

| E 1

A -> S 1

B -> C 1

| D 1

C -> 0

D -> B 1

E -> E 0

| 1

Устраним левую рекурсию из следующих правил.

S -> A 1 | B 0 | E 1

A -> B 0 1 A' | E 1 1 A'

B -> C 1| D 1

C -> 0

D -> 0 1 1 D'

E -> 1 E'

A' -> 1 1 A' | ϵ

D' -> 1 1 D' | ϵ

E' -> 0 E' | ϵ

И получаем итоговую грамматику после устранения рекурсии.