“Л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