Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СКІНЧЕННІ АВТОМАТИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Лiнгвiстичне забезпечення САПР
Група:
КН-413
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Звіт
до
Лабораторної роботи №2
на тему:
СКІНЧЕННІ АВТОМАТИ
з курсу:
«Лінгвістичне забезпечення САПР»
1. МЕТА РОБОТИ
Навчитися моделювати роботу розпізнавача за допомогою скінченного автомата.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
В основі побудові компіляторів лежить теорія автоматів. Автомат – це нереально існуючий пристрій, а деяка математична модель, властивості і поведінку якої можна вивчити і яку можна імітувати на реальній ЕОМ.
Скінченний автомат – це найпростіша з моделей теорії автоматів.
Скінченним називається автомат, у якому множина внутрішніх станів і множина вхідних значень є скінченними множинами.
Скінченний розпізнавач – це модель пристрою із скінченним числом станів, які відрізняють правильно утворенні ланцюжки символів від неправильних (недопустимих).
Вхідна стрічка – це послідовність комірок, кожна комірка містить тільки один символ із скінченного вхідного алфавіту. Крайню ліву і крайню праву комірки можуть займати кінцеві маркери.
Вхідна головка у кожний момент часу читає одну вхідну комірку.
Пам'ять розпізнавача – це будь-яке сховище інформації або даних. Оскільки алфавіт скінченний, то об’єм пам’яті скінченний.
Керуючий пристрій є ядром розпізнавача. Це програма, яка керує роботою (поведінкою) розпізнавача. Керуючий пристрій – це скінченна множина станів разом з відображенням, яке описує як змінюється стани відповідно до поточного вхідного символу та інформацією, добутою із пам’яті.
Роботу розпізнавача можна відобразити в термінах його конфігурації:
1. Стан керуючого пристрою;
2. Вміст вхідної стрічки і положення вхідної головки;
3. Вміст пам’яті;
Конфігурація є початковою, якщо керуючий пристрій знаходиться у заданому початковому стані, вхідна головка може читати крайній лівий символ у стрічці і пам'ять має наперед установленний вміст.
Конфігурація є кінцевою, якщо керуючий пристрій знаходиться в одному з наперед визначених множиною кінцевих станів, а вхідна головка може читати правий кінцевий маркер, або вразі його відсутності, вона зійшла з правого кінця вхідної стрічки.
Формально скінченний розпізнавач визначається за п’ятьма характеристиками:
1. Скінченною множиною станів ;
2. Скінченним вхідним алфавітом ;
3. Множиною переходів , які відображають поведінку керуючого пристрою;
4. Початковим станом ;
5. Множиною кінцевих станів .
Тобто скінченний автомат описується як .
ПРИКЛАД ПОБУДОВИ СКІНЧЕННОГО АВТОМАТА
Прикладом скінченного автомата може контролер непарності «1» в ланцюжку символів, що складається з нулів і одиниць. Скінченний автомат буде допускати усі ланцюжки, які містять непарну кількість «1» і відкидати ті з них, які містять парну кількість «1».
Вхідним алфавітом такого автомата буде множина {0, 1}.
Множина станів буде складатись із двох станів ПАР і НЕПАР.
Початковим станом буде стан ПАР.
При читанні наступного вхідного символу стан автомата змінюється. Новий його стан залежить від вхідного символу і поточного символу.
Функція переходів буде мати такий вигляд:
(ПАР, 0)=ПАР
(ПАР, 1)=НЕПАР
(НЕПАР, 0)=НЕПАР
(НЕПАР, 1)=ПАР
Кінцевий (допускаючим) станом є НЕПАР.
Ланцюжок 1101 допускається автоматом, оскільки останнім є допускаючий стан НЕПАР. Іншою є ситуація при обробці ланцюжка 101, він відкидається, оскільки його кінцевим станом є недопустимий стан ПАР.
Один із зручних методів подання скінченного автомата є таблиця переходів.
Правила побудови таблиці такі:
1. Стовпці помічено символами вхідного алфавіту.
2. Рядки помічено символами станів.
3. Елементи таблиці є символами нових станів, які визначаються вхідним символом і попереднім станом.
4. Перший рядок помічено символом початкового стану.
5. Рядки, які відповідають допускаючим станам, помічені справа одиницями: рядки, які відкидаються автоматом, помічаються справа нулями.
Для нашого автомата таблиця переходів показана на рис. 1.
Крім табличного подання, скінченний автомат можна подати діаграмою (або графом) переходів.
0
1
ПАР
ПАР
НЕПАР
0
НЕПАР
НЕПАР
ПАР
1
Рис. 1 Таблиця переходів скінченного автомата, який допускає ланцюжки 0, 1, що містять непарну кількість одиниць
Графом переходів називається неупорядкований позначений граф, вершини якого відповідають іменам станів, а дуги відображають функцію переходів.
НЕДЕТЕРМІНОВАНІ СКІНЧЕННІ АВТОМАТИ
Скінченний автомат, приклад якого наведено у попередньому розділі, належить до детермінованих скінченних автоматів.
Детермінованим називається скінченний автомат, у якого для кожної конфігурації існує тільки один наступний крок.
Недетермінованим називається скінченний автомат, у якого для кожної конфігурації існує скінченна множина можливих подальших кроків. Недетермінований скінченний автомат можна описати такою залежністю:
Наведемо приклад недетермінованого скінченного автомата, який буде допускати ланцюжки символів, що починаються з одиниці і не містять двох і більше нулів:
1. Множина станів ;
2. Вхідний алфавіт ;
3. Початковий стан ;
4. Функція переходів (порожня множина);
5. Допускаючий стан B.
Таблиця переходів такого недетермінованого скінченного автомата показана на рис. 2.
0
1
A
0
{B}
0
B
(А,В)
{B}
1
Рис. 2 Таблиця переходів недетермінованого автомата
Стрічка 01001 не буде сприйнятою, оскільки при читанні «0» не здійснюється перехід із стану А. Для недетермінованих автоматів необхідно при аналізі рядка перебрати усі можливі послідовності переходів.
СПОСОБИ ПОДАННЯ СКІНЧЕННИХ АВТОМАТІВ НА ЕОМ
Розглянемо деякі проблеми, що пов’язані з реалізацією скінченного автомата як програми або підпрограми для обчислювальної машини.
Найчастіше за допомогою скінченних автоматів вирішують задачі розпізнавання скінченної множини слів. Такі задачі називають проблемою «ідентифікації», оскільки дія компілятора залежить від ідентичності вхідного ланцюжка автомата деякому відповідному слову.
Щоб промоделювати скінченний автомат, необхідно якимось чином закодувати його вхідну множину символів. Крім того, необхідно запам’ятати стани модельованого автомата і таблицю переходів.
Скінченні автомати можна подати на ЕОМ у вигляді матриці переходів, або у вигляді зв’язаної спискової структури.
Скінченний автомат із станами і алфавітом вхідних символів можна подати за допомогою матриці В розмірністю m×n елементів такої, що елемент містить число К–номер стану де
Стан вважається початковим, а список кінцевих станів подається вектором
…
…
…
…………………………………………….
…………………………………………….
…
Для подання скінченного автомата у вигляді спискової структури використовуються динамічні об’єкти типу однонаправленого списку, одне поле якого є вхідним символом, а інше – вказівником на список переходів до наступного стану. Перехід полягає в простій заміні вказівника списку переходів для поточного станів на одержаний з таблиці вказівник списку переходів для наступного стану. Списки можуть бути лінійними і впорядкованими.
3. ВИКОНАННЯ РОБОТИ
Варіант №17
Побудувати не детермінований скінченний автомат, який буде розпізнавати усі ланцюжки в яких: Між кожним входженням одиниці є непарна кількість нулів.
ТЕКСТ ПРОГРАМИ НА ПАСКАЛІ.
1000001 – Dopustumo
100001 – Nedopustumo
#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int M[6][2]=
{{0, 1},
{2, 0},
{3, 5},
{2, 0},
{0, 5},
{5, 5} ,
} ;
int S=0;
char *str;
printf("--- Vvestu ryadok ---\n\n");
gets(str);
for(int i=0; str[i]!=0; i++)
{
S=M[S][str[i]-48];
//printf("S=%d",S);
}
if(S==5) printf("\n dopusk");
else printf("ne Dopusk");
getch();
}
4. ВИСНОВОК
На цій лабораторній роботі, я вивчив і закріпив навики моделювати роботи розпізнавача за допомогою скінченного автомата. Написав управляючу програму, для розпізнавання множини ланцюжків з нулів і одиниць, в яких. між кожним входженням одиниці є три нулі. Переконався, що вона працює і виводить коректний результат.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора