Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

I. Зачётные задачи по теме "Лексический блок и конечные автоматы" (2015 - весна).

 

 

1◦. Создать конечный автомат и процессор, распознающий и вычисляющий числовые выражения, построенные по следующим правилам:

а) операнды: натуральные константы;
б) унарные операции: + −;

в) бинарные операции: + − ∗ /;

 

г) унарные операции имеют одинаковый приоритет и выполняются строго слева направо, например, 3+5∗2 равно 16 (а не 13), в выражении отсутствуют скобки;

д) допускается употребление унарной операции после бинарной, например: 2∗−3 равно −6. Считать входным алфавитом A = {c+−∗/}, где c – цифра.

 

2◦. Постройте конечный автомат и процессор, распознающий химические формулы и вычисляющий молекулярный вес химических соединений, если формулы:

а) составлены из восьми химических элементов: H, C, Cl, N, O, S, Si, Sn;

 

б) элементы могут появляться в любом порядке и необязательно представляют реально существующие соединения. Например: H2O, OH7, H2SO4, ClNO3.

 

3◦. Постройте конечный автомат, реализующий лексический блок, распознающий текст, составленный из 45 слов: один, два, три, ... , девять, десять, одиннадцать, ... девятнадцать, двадцать, тридцать, ... , девяносто, сто, двести, триста, ... , девятьсот, тысяча, тысячи, тысяч, миллион, миллиона, мил-лионов, миллиард, миллиарда, миллиардов. Слова разделяются одним или несколькими пробелами. На выходе лексического блока каждое слово заменяется символом с ASCII кодом, равным c + N, где c = 96, а N – номер слова в списке (пробелы выбрасываются). Автомат должен быть реализован при помощи динамического списка.

 

4◦. Постройте конечный автомат, имеющий входной алфавит из 45 входных "символов": один, два, три, ... , девять, десять, одиннадцать, ... девятнадцать, двадцать, тридцать, ... , девяносто, сто, двести, триста, ... , девятьсот, тысяча, тысячи, тысяч, миллион, миллиона, миллионов, миллиард, миллиарда, миллиардов. (Практически пусть каждый входной "символ" представлен обычным символом DOS с ASCII кодом, равным c + N, где c = 96, а N – номер слова в списке.) Автомат допускает в качестве входа "словесную" запись натурального числа от 1 до 999 999 999 999 и выдает в качестве выхода эквивалентную числовую запись. Например, "два миллиона восемьсот тридцать семь" переходит в "2000837".

 

5◦. Постройте конечный автомат, распознающий натуральные числа в отрезке от 1 до 3999, записанные римскими цифрами. Соответствующий процессор должен переводить числа в формат integer (или аналогичный), а затем выводить в строку арабскими цифрами.

 

6◦. Построить транслитератор: кириллица − > латиница, а также конечный автомат, осуществ-ляющий обратную транслитерацию: латиница − > кириллица в соответствии с таблицей замены символов : (а - a, б - b, в - v, г - g, д - d, е - je, ё - jo ,ж - zh, з - z, и - i, й - y, к - k, л - l, м - m, н - n, о - o, п - p, р - r, с - s, т - t, у - u, ф - f, х - x, ц - c, ч - ch, ш - sh, щ - wh, ъ - ”, ы - ji, ь - ’, э - e, ю - ju, я - ja). (Считать, что в русском тексте символ одинарной кавычки не используется, а двойные кавычки используютчя только в начале или в конце слова. Пробелы и другие разделительные символы оставлять неизменными.)

 

7◦. Построить автомат, осуществляющий чтение матрицы с целочисленными элементами из текстового файла и преобразующий её во внутренний формат выбранного языка программирования (с последующей распечаткой результатов в текстовый файл). Элементы в строке матрицы отделяются одним или несколькими символами пробела или табуляции, и расположены не обязательно друг под другом. (Запрещается использование функции Val(.) и подобные ей.)

 

8◦. Построить автомат, осуществляющий чтение вектор строки, содержащей числовые константы. Например, такой: (+27,−3,2.1,15,.7E + 12). На выходе автомата должна появиться последовательность элементов типа запись (возможно с вариантами) с полями: ТИП (значения: 0-word, 1-integer, 2-real), ЗНАЧЕНИЕ WORD, ЗНАЧЕНИЕ INTEGER, ЗНАЧЕНИЕ REAL. Предусмотреть распечатку в текстовый файл в следующем виде: (27,word) (-3,integer) (2.1,real) (15,word) (0.7E12,real).

 

 
 
9◦. В различных версиях языка разметки математических текстов ТеХ: AMS-TeX, Plain TeX, обыкновенные дроби задаются различными командами. Например дробь 12/17 задается соответственно командами $ \frac{ 12 , 17 } $ и $ { 12 \over 17 } $. Пусть входной текст состоит из русских букв, знаков препинания (.,;:!?"), и дробей в формате AMS-TeX’а ($ \frac ... $). Построить автомат, который на выходе заменяет формат записи дробей (AMS-TeX − > Plain TeX), оставляя рус-ский текст неизменным. Вложенные и цепные дроби в тексте не допускаются. Например дробь
 
(1/2)/3 $ \frac{\frac{ 1 , 2 } , 3 } $ недопустима.

 

10◦. Используя структуру объект одного из языков программирования (Pascal, C++, ...) моделировать работу конечного автомата, организованного как динамический список. Предусмотреть процедуры: Добавить слово в список, Найти слово в списке, Удалить слово из списка, Очистить список, Распечатать список в текстовый файл.

 

Постройте транслирующий автомат со стеком, преобразующий строки вида:

11. Cn+(Cm)r ® Cn+m. Где Cn – запись натурального числа n в 2-ичной системе счисления. Индекс r означает операцию разворачивания строки в обратную сторону.

 

12. Сn ® (Cn+2)r. (См. обозначения предыдущей задачи.)

 

Требования к выполнению задачи и оформлению отчёта.

 

I. Описание конечного автомата.

 

1. Один или несколько характерных примеров входной цепочек, на основе которых определены:
а) входной алфавит;

б) под символами цепочек из примеров подписаны состояния автомата;
в) словесное описание состояний.

2. Схема переходов (не обязательно) и таблица переходов (обязательно).

 

3. Проверка минимальности автомата и приведение его, если нужно к минимальному виду.

 

4. Таблица переходов процессора (обрабатывающего символ конца строки и завершающего свою работу досрочно в случае ошибки).

5. Ввести имена процедур в таблицу переходов.

 

6. Ввести регистры, необходимые для работы автомата.

 

7. Описание процедур (из п.5), обрабатывающих регистры.

 

8. Выписать проверочный набор входных цепочек, под действием которых каждый переход автомата выполняется хотя бы один раз.

9. Для каждой проверочной входной цепочки построить таблицу переходов, отражающую текущее содержание регистров автомата.

II. Распечатка текста программы на одном из языков программирования (Pascal, C++, ...), реализующей работу конечного автомата.

III. Результаты работы программы (на одном или нескольких примерах): распечатка входного текстового файла и выходного.

IV. Работающая программа.




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.