ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 12
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Вопрос 1. На вход автомата поступает последовательность непустых строк, содержащих группы букв и цифр, при этом цифры есть обязательно. Каждая строка завершается символом «#». Автомат должен распознавать и допускать строки, в которых встречается только четное количество цифр в группах, например, допустимы строки:
а) fhgfhfjf56787979tuytuyyu45cvbcv#
б) 56плорл354356#
в) 6789#
Нарисуйте синтаксическую диаграмму и постройте таблицу конечного автомата.
Решение:
| | б | ц | # | Другие символы |
| 1 | 2 | 3 | Е | E |
| 2 | 2 | 3 | Е | E |
| 3 | Е | 4 | Е | E |
| 4 | 5 | 3 | К | E |
| 5 | 5 | 3 | К | E |
Автомат не минимален, так как есть совпадающие строки. Удаляем 2-ю и 5-ю строки и заменяем состояния: 2 – на 1, 5 – на 4.
| | б | ц | # | Другие символы |
| 1 | 1 | 3 | Е | E |
| 3 | Е | 4 | Е | E |
| 4 | 4 | 3 | К | E |
Вопрос 2. Дана грамматика, описывающая упрощенный вариант сложных выражений С++:
<Сложное выражение>::= <Сложное выражение>, <Выражение> |
<Сложное выражение>+<Выражение> |
<Сложное выражение>-<Выражение> |
<Выражение>
<Выражение>::= <Ид>
Приведите последовательность выполнения грамматического разбора для сентенциальной формы:
<Ид>+<Ид> - <Ид>,<Ид>-<Ид>, <Ид>-<Ид>
левосторонним восходящим методом.
Определите, к какому типу по Хомскому принадлежит грамматика. Почему?
Решение:
Вводим обозначения:
С – сложное выражение;
В – выражение;
Ид – идентификатор.
Тогда правила будут выглядеть так:
а) С ::= С, В | С+В | С-В | В
б) В ::= Ид
Грамматика принадлежит к 3-му типу по Хомскому, так как:
- правила в левой части содержат единственный символ – нетерминал, соответственно это не грамматики 0 и 1 типов;
- в правой части правил отсутствует вложенная рекурсия, соответственно это не грамматика 2 типа.
Основу в сентенциальной форме ищем слева направо, правила подбираем по правой части снизу-вверх и слева-направо (основу отмечаем красным):
1) ид + ид - ид, ид - ид, ид – ид
2) в + ид - ид, ид - ид, ид – ид
3) с + ид - ид, ид - ид, ид – ид
4) с + в - ид, ид - ид, ид – ид
5) с - ид, ид - ид, ид – ид
6) с - в, ид - ид, ид – ид
7) с, ид - ид, ид – ид
8) с, в - ид, ид – ид
8) с - ид, ид – ид
9) с - в, ид – ид
10) с, ид – ид
11) с, в – ид
12) с – ид
13) с – в
14) с Аксиома, конец разбора
....
В РК4 достаточно привести первые 20 строк :-)...
Можно использовать таблицу, как сделано в лекции.
| № | Строка разбора | Основа | Действие |
| 1 | ид + ид - ид, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 2 | в + ид - ид, ид - ид, ид - ид | в | Свертка по правилу а4 |
| 3 | с + ид - ид, ид - ид, ид - ид | с | Нет правила, след.основа |
| 4 | с + ид - ид, ид - ид, ид - ид | с+ | Нет правила, след.основа |
| 5 | с + ид - ид, ид - ид, ид - ид | с + ид | Нет правила, след.основа |
| 6 | с + ид - ид, ид - ид, ид - ид | + | Нет правила, след.основа |
| 7 | с + ид - ид, ид - ид, ид - ид | + ид | Нет правила, след.основа |
| 8 | с + ид - ид, ид - ид, ид - ид | + ид - | Нет правила, след.основа |
| 9 | с + ид - ид, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 10 | с + в - ид, ид - ид, ид - ид | с | Нет правила, след.основа |
| 11 | с + в - ид, ид - ид, ид - ид | с+ | Нет правила, след.основа |
| 12 | с + в - ид, ид - ид, ид - ид | с + в | Свертка по правилу а2 |
| 13 | с - ид, ид - ид, ид - ид | с | Нет правила, след.основа |
| 14 | с - ид, ид - ид, ид - ид | с- | Нет правила, след.основа |
| 15 | с - ид, ид - ид, ид - ид | с - ид | Нет правила, след.основа |
| 16 | с - ид, ид - ид, ид - ид | - | Нет правила, след.основа |
| 17 | с - ид, ид - ид, ид - ид | - ид | Нет правила, след.основа |
| 18 | с - ид, ид - ид, ид - ид | - ид, | Нет правила, след.основа |
| 19 | с - ид, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 20 | с - в, ид - ид, ид - ид | с | Нет правила, след.основа |
| 21 | с - в, ид - ид, ид - ид | с - | Нет правила, след.основа |
| 22 | с - в, ид - ид, ид - ид | с - в | Свертка по правилу а3 |
| 23 | с, ид - ид, ид - ид | с | Нет правила, след.основа |
| 24 | с, ид - ид, ид - ид | с, | Нет правила, след.основа |
| 25 | с, ид - ид, ид - ид | с, ид | Нет правила, след.основа |
| 26 | с, ид - ид, ид - ид | , | Нет правила, след.основа |
| 27 | с, ид - ид, ид - ид | , ид | Нет правила, след.основа |
| 28 | с, ид - ид, ид - ид | , ид - | Нет правила, след.основа |
| 29 | с, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 30 | с, в - ид, ид - ид | с | Нет правила, след.основа |
| 31 | с, в - ид, ид - ид | с, | Нет правила, след.основа |
| 32 | с, в - ид, ид - ид | с, в | Свертка по правилу а1 |
| 33 | с - ид, ид - ид | с | Нет правила, след.основа |
| 34 | с - ид, ид - ид | с - | Нет правила, след.основа |
| 35 | с - ид, ид - ид | с - ид | Нет правила, след.основа |
| 36 | с - ид, ид - ид | - | Нет правила, след.основа |
| 37 | с - ид, ид - ид | - ид | Нет правила, след.основа |
| 38 | с - ид, ид - ид | - ид, | Нет правила, след.основа |
| 39 | с - ид, ид - ид | ид | Свертка по правилу б1 |
| 40 | с - в, ид - ид | с | Нет правила, след.основа |
| 41 | с - в, ид - ид | с - | Нет правила, след.основа |
| 42 | с - в, ид - ид | с - в | Свертка по правилу а3 |
| 43 | с, ид - ид | с | Нет правила, след.основа |
| 44 | с, ид - ид | с, | Нет правила, след.основа |
| 45 | с, ид - ид | с, ид | Нет правила, след.основа |
| 46 | с, ид - ид | , | Нет правила, след.основа |
| 47 | с, ид - ид | , ид | Нет правила, след.основа |
| 48 | с, ид - ид | , ид - | Нет правила, след.основа |
| 49 | с, ид - ид | ид | Свертка по правилу б1 |
| 50 | с, в - ид | с | Нет правила, след.основа |
| 51 | с, в - ид | с, | Нет правила, след.основа |
| 52 | с, в - ид | с, в | Свертка по правилу а1 |
| 53 | с - ид | с | Нет правила, след.основа |
| 54 | с - ид | с - | Нет правила, след.основа |
| 55 | с - ид | с - ид | Нет правила, след.основа |
| 56 | с - ид | - | Нет правила, след.основа |
| 57 | с - ид | - ид | Нет правила, след.основа |
| 58 | с - ид | ид | Свертка по правилу б1 |
| 59 | с - в | с | Нет правила, след.основа |
| 60 | с - в | с - | Нет правила, след.основа |
| 61 | с - в | с - в | Свертка по правилу а3 |
| 62 | с | Конец | |