ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
Московский Государственный Университет Приборостроения и Информатики
Факультет «Информатики»
Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»
Отчет по практической работе
По дисциплине «Дискретная математика»
На тему «Разработка синтаксических анализаторов для регулярных языков»
Выполнил студент 1 курса
Группы ИТ-6 1002
Очной-заочной формы обучения
Ахальцев Иоанн Сергеевич
Москва 2011
Цель работы
Написание, отладка и проверка работоспособности синтаксического анализатора на основе графа детерминированного конечного автомата, соответствующего заданному регулярному выражению, порождающему конкретный язык.
Исходные данные варианта задания.
1. Вариант №23. (1100)* (1000)* (1011)*
Алгоритм решения задачи
2. Рассмотрим регулярное выражение (1100)* (1000)* (1011)*. Это выражение порождает предложения языка:
L = {(1100)m (1000)n (1011)p: m, n, p > 0}.
| Вход/состояние
| S
| A
| B
| C
| D
| E
| F
| K
| R
| M
| N
| T
| W
|
|
| A
| B
| Æ
| Æ
| E
| Æ
| T
| Æ
| M
| Æ
| T
| R
| T
|
|
| Æ
| W
| C
| S
| Æ
| F
| K
| D
| Æ
| N
| Æ
| Æ
| T
|
|
|
|
Множество переходов d может быть эквивалентно представлено таблицей переходов:
Здесь Æ — пустое множество. (1100)* (1000)* (1011)*
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
