Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Записати граматику, по якiй генеруються довiльнi рядки (включаючи порожнi) по алфавiту {0,1}
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2000
Тип роботи:
Задача
Предмет:
Лiнгвiстичне забезпечення САПР
Частина тексту файла (без зображень, графіків і формул):
“Лiнгвiстичне забезпечення САПР”
1.(184) Записати граматику, по якiй генеруються довiльнi рядки (включаючи порожнi) по алфавiту {0,1}.
Граматика описується наступною четівркою Vn - множина нетермінальних символів, Vt - множина термінальних символів,S - початковий символ,P - множина правил підстановки.
Множина термінальних символів Vn={0, 1, e}, де е - пустий ланцюжок
Множина нетермінальних символів Vt={A, S}, де S - початковий символ
Множина правил підстановки Р:
S ->A; A->e; A->0A; A->A0; A->1A; A->A1;
або
S->A; A-> e | 0A | A0 | 1A | A1
Граматика яка описується такою четвіркою генерує довільні рядки по алфавіту {0, 1}
2. (185) Побудувати автомат для розпiзнавання ланцюжкiв, якi можуть знаходитися пiсля слова INTEGER в операторах специфiкацiї формату.
Ролі, які зустрічаються в наступній задачі можуть бути описані так:
2 - ім'я змінної, описаної як INTEGER
3 - ліва дужка
4 - ціла стала, яка визначає розмірність
5 - кома, яка розділяє розмірності
6 - змінна, яка визначає змінну розмірність
7 - права дужка
8 - кома, яка розділяє об'єкти, описані як цілі
Після того, коли всі ролі позначені автомат може бути побудований по такому алгоритму:
Крок 1 Ввести початковий стан і стан помилки
Крок 2 Ввести стан для кожної ролі
Крок 3 Помістити в таблицю переходи з одного стану в інший, якщо відповідні ролі можуть поступати одна за одною
Крок 4 Поповнити таблицю переходами в стан помилки
Крок 5 Вибрати в якості допускаючих ті стани, ролі яких з'являються в кінці допускаючих ланцюжків
Початковий стан - 1, Стан помилки - Е
* - Допускаючі стани - 2 і 7
3.(186) Описати автомат i написати ланцюжки, якi допускає i якi вiдкидає розпiзнавальний автомат, зображений на рисунку:
Скінченний автомат описується наступним чином:
EMBED Equation.3 , де Q - скінченна множина станів, S - початковий стан, EMBED Equation.3 - множина переходів, EMBED Equation.3 - скінченний вхідний алфавіт, F - множина заключних станів
У даному випадку: Q={1, 2, E}, S=1, EMBED Equation.3 ={A,B}, F={1}
Множина переходів
EMBED Equation.3 (1,A)=1 EMBED Equation.3 (1,B)=2; EMBED Equation.3 (2,A)=E; EMBED Equation.3 (2,B)=1; EMBED Equation.3 (E,A)=E; EMBED Equation.3 (E,B)=E
A,B
A
B
B
A
1
2
E
Можливі наступні варіанти ланцюжків, які допускає даний автомат: Аn, АnВВ , після кожної послідовності символів А повинно йти два символи В або ланцюжок має закінчитись.
4. (187) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - кiлькiсть одиниць парна, а кiлькiсть нулiв непарна
Введемо наступні стани:
А - кількість нулів парна, кількість одиниць парна;
В - кількість нулів непарна, кількість одиниць парна;
С - кількість нулів парна, кількість одиниць непарна;
D - кількість нулів непарна, кількість одиниць непарна;
Допускаючим станом є стан В.
Таблиця переходів виглядає наступним чином:
5. (188) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - мiж одиницями в ланцюжку парна кiлькiсть нулiв
Множина станів для такого розпізнавача: S={S1,S2}, множина магазиннних символів: {С,Z}. Вхідний алфавіт: {0, 1, -| }. Множина переходів описується наступними таблицями:
Для стану S1:
Для стану S2:
6. (189) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - пiсля кожної пари одиниць знаходиться нуль
Множина станів для такого розпізнавача: S={S1,S2}, множина магазиннних символів: {С,Z}. Вхідний алфавіт: {0, 1, -| }. Множина переходів описується наступними таблицями:
Для стану S1:
Для стану S2:
7. (190) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - кожний третiй символ - одиниця
Множина станів для такого розпізнавача S={A,B,C,E} де Е - стан помилки. Початковим станом є стан А. При аналізі кожного третього символа автомат знаходиться в стані С. При наявності на вході в цьому стані 0 автомат переходить в стан помилки, при наявності 1 - в стан А. Всі стани крім стану помилки Е є допускаючими.
8. (191) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше - знаходиться в ланцюжку хоча б одна одиниця.
Множина станів для такого розпізнавача S={A,B }. В стані А автомат перебуває до тих пір, поки у вхідному ланцюжчу не зустрічалась одиниця. При поступленні одиниці автомат переходить в стан В, який є допускаючим.
9. (192) Опишить словами множину ланцюгiв, якi розпiзнаються автоматом з такою таблицею станiв (переходiв):
Автомат переходить зі стану А в стан В при поступленні 0. При поступленні 1 автомат залишається в стані А. Отже після надходження де-якої кількості одиниць для переходу в стан В на вхід повинна поступити одиниця. Допускаючим станом є стан С. При поступленні нуля в стані В автомат залишається в цьому ж стані, а при поступленні одиниці автомат переходить в стан С. В стані С автомат залишається до закінчення ланцюжка. Отже ланцюжки, які допускає даний автомат можна описати наступним чином EMBED Equation.3 де n EMBED Equation.3 0, m>0 А - довільний ланцюжок алфавіту {0,1}.
10. (193) Опишить словами множину ланцюгiв, якi розпiзнаються автоматом з такою таблицею станiв (переходiв):
Очевидно, що першим символом в допускаючому ланцюжку повинен бути 0. Після поступлення 0 автомат переходить в стан В, який є допускаючим станом. При поступленні 0 в стані В автомат переходить в стан помилки. При поступленні 1 в стані В автомат залишається в цьому ж стані.
Отже монжину допускаючих ланцюжків для заданого автомата можна описати наступним чином:
EMBED Equation.3 , де n EMBED Equation.3 0
11. (194)Опишить словами множину ланцюгiв, якi розпiзнаються автоматом з такою таблицею станiв (переходiв):
При поступленні 0 в стані А автомат переходить в стан В, в якому для того щоб ланцюжок був допускаючим на вхід повинні поступати лише одиниці. При поступленні 1 в стані В автомат переходить в стан С, в якому для того щоб ланцюжок був допускаючим на вхід повинні поступати лише нулі.
Можливі ланцюжки, які допускає даний автомат: 01n n>=0, 10m, m>=0
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора