Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт
Предмет:
Лiнгвiстичне забезпечення САПР
Група:
КН-413
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Звіт з виконання
Лабораторної роботи №4
на тему:
ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ
з курсу:
«Лінгвістичне забезпечення САПР»
1. МЕТА РОБОТИ
Ознайомитись з автоматами і лінійними граматиками, проаналізувати їх розв’язок із скінченими автоматами.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
На перших порах наука про мову – лінгвістика зводилась до вивчення природних мов, їх класифікації виявлення різниці та подібності між ними. З виникненням ЕОМ і мов програмування поняття значно розширилось.
Виникла потреба створення формального математичного апарату – формальних граматик як механізму описання мов програмування і проектування.
Сформулюємо деякі визначення.
Неформально визначити можна як підмножину множин всіх речень із слів або символів деякого основного словника.
Алфавіт – це непуста скінчена множина елементів, які називаються символами.
Ланцюжком називається будь-яка скінчена послідовність алфавіту .
Довжина ланцюжка дорівнює кількості символів у ньому: , .
За способом задання правильних ланцюжків формальні граматики поділяються на породжуючі і розпізнаючі.
До породжуючих належать граматики, які встановлюють правила побудови будь-якого правильного ланцюжка і визначають структуру так, що не можна побудувати жодного неправильного ланцюжка.
Розпізнаючі граматики дають змогу встановити, чи є правильним довільно вибраний ланцюжок, якщо він правильний, визначити його будову.
Для побудови трансляторів використовують обидва ці способи: породжуючу граматику для описання синтаксису мови програмування і розпізнаючий пристрій – скінчений автомат як модель алгоритму розпізнавання речень мови.
Породжуючою граматикою називається впорядкована четвірка: .
де - основний термінальний алфавіт;
- скінчений нетермінальний алфавіт;
- початковий нетермінальний символ – аксіома;
- скінчена множина підстановок (продукцій), ліві і праві частини – це ланцюжки та , які містять символи термінального і нетермінального алфавітів.
Символи термінального алфавіту є елементарними одиницями мови. Символи нетермінального алфавіту є метазмінними, які використовують при виведені правильних ланцюжків.
Початковий символ - це метазмінна з якої виводяться всі правильні ланцюжки.
Множина – граматичні правила мови, яку визначають.
Щоб відрізнити термінальні символи від нетермінальних, прийнято не термінальні символи поміщати в кутові дужки.
ФОРМА БЕКУСА-НАУРА
Таке подання граматики є нормальною формою Бекуса (БНФ) і є першою метамовою, яка використовувалась для описання синтаксису алгоритмічної мови «Алгол-60». Основним призначенням форми Безуса – Наура є представлення в стислому і компактному вигляді формальних і однозначних правил написання основних конструкцій мови програмування.
У формі Бекуса описуються два класи об’єктів:
1. основні символи мови (термінальні символи);
2. мета лінгвістичні змінні (не термінальні символи).
Кожна металінгвістика форма описує правила побудови конструкцій мови і складається з двох частин.
Ліворуч мета лінгвістична змінна, яка визначає відповідну конструкцію.
Далі металінгвістична зв’язка , що означає «визначається як».
Праворуч – формули, що означають один або декілька варіантів побудови конструкції. Для побудови відповідної конструкції необхідно вибрати відповідний варіант з правої частини формули і підставити його замість відповідної металінгвістичної змінної. Такий процес називається і позначається символам .
КЛАСИФІКАЦІЯ ФОРМАЛЬНИХ ГРАМАТИК
Вирішальний вплив на властивості мови, складність породження і розпізнавання ланцюжків мають правила підстановки множини , тобто граматичні правила мови. Класифікація мов буда запропонована в 1959 році американським лінгвістом Н. Хомським. Він запропонував класифікувати формальні мови за типом правил породжуючих граматик.
Клас 0. Правила виводу граматики мають таку форму , без будь-яких обмежень на ланцюжки та . Ці мови є моделлю природних мов.
Клас 1. Контекстно-залежні мови або граматика безпосередніх складових (НС - граматики) з граматикою , де - довільні можливо і пусті ланцюжки з алфавіту ; - лівий; - правий контекст; - нетермінальний символ; - непустий ланцюжок з множини .
Клас 2. Контекстно-вільні граматики (КВ - граматики). Мають правила виводи вигляду: , де - нетермінальний символ; - довільний непустий ланцюжок з множини . Мови породжені КВ – граматикою, називаються контекстно-вільними. Вони найчастіше використовуються для описання мов програмування в мов проектування.
Клас 3. Лінійні (ЛН) і автоматні (А) граматика. Лінійні мають продукцію , де або : , . Автоматні , де , .
Лінійні і автоматні мови мають скінчену кількість станів і можуть представлятися скінченими автоматами. Алгоритми розпізнавання лінійних і автоматних мов досить прості і використовуються для аналізу простих мов, найчастіше на етапі лексичного аналізу.
ЗВ'ЯЗОК РЕГУЛЯРНИХ МОВ ІЗ СКІНЧЕННИМИ АВТОМАТОМ
Граматики, які мають продукції вигляду або , де , , називаються регулярними і можуть описуватися скінченним автоматом.
Правила переходу від скінченного автомата до формальної граматики:
1. Множиною термінальних символів зробити множину вхідного алфавіту.
2. Множиною нетермінальних символі зробити множину стані.
3. Початковим символом зробити початковий стан автомата.
4. Якщо в автоматі є перехід із стану в стан по входу , то в граматиці це відобразиться правилом: .
5. Якщо - допускаючий стан автомата, то в граматиці вводиться правила: , де - пуста множина.
3. ВИКОНАННЯ РОБОТИ
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Варіант №17
Скласти програму для розпізнавання ланцюжків, які породжуються конкретною формальною граматикою. Для розпізнавання використати скінченний автомат.
SAB
AaA|a
BbB|b
Бінарне дерево
ПОСЛІДОВНІСТЬ КОНФІГУРАЦІЙ
bbb…bbb
aaa…aaa
СКІНЧЕНИЙ АВТОМАТ
b
X
X
A
F
X
B
F
X
F
ТЕКСТ ПРОГРАМИ НА МОВІ ПРОГРАМУВАННЯ С
using System;
namespace Lab04
{
class endedAutomat
{
private string str;
private char[] sl;
private char[] tableOfStanes;
private char[,] conf;
private byte stan;
public endedAutomat(string str)
{
this.str = str;
sl = new char[3];
sl[0] = 'a'; sl[1] = 'b';
tableOfStanes = new char[5];
tableOfStanes[0] = 'S';
tableOfStanes[1] = 'A';
tableOfStanes[2] = 'B';
tableOfStanes[3] = 'X';
tableOfStanes[4] = 'F';
stan = 0;
conf = new char[5, 2];
conf[0, 0] = tableOfStanes[1]; conf[0, 1] = tableOfStanes[3];
conf[1, 0] = tableOfStanes[2]; conf[1, 1] = tableOfStanes[3];
conf[2, 0] = tableOfStanes[3]; conf[2, 1] = tableOfStanes[4];
}
public char getStan()
{
return tableOfStanes[this.stan];
}
public void getAllowance()
{
byte first_second = 1;
for (int i = 0; i < str.Length; i++)
{
if (stan == 3) { break; }
else
{
switch (stan)
{
case 0:
if (str[i] == sl[0]) { stan = 1; }
else if (str[i] == sl[1]) { stan = 2; }
break;
case 1:
if (str[i] == sl[0]) { stan = 1; }
else if (str[i] == sl[1]) { stan = 3; }
break;
case 2:
if (str[i] == sl[0]) { stan = 3; }
else if (str[i] == sl[1]) { stan = 2; }
break;
}//End switch (stan)
}//End else
}//End for (int i = 0; i < str.Length; i++)
}//End public void getAllowance()
}//End class endedAutomat
class Program
{
static void Main(string[] args)
{
string str;
Console.WriteLine("Enter string:");
str = Console.ReadLine();
endedAutomat gr = new endedAutomat(str);
gr.getAllowance();
if (gr.getStan() == 'A' || gr.getStan() == 'B')
{
Console.WriteLine("Strichka was allowed...");
}
else
{
Console.WriteLine("Strichka was´nt allowed...");
}
}
}
}
Результати виконання програми
Enter string:
aaaaaaaaaa
String was allowed...
Enter string:
aaabbb
String wasn't allowed...
4. Висновок
На цій лабораторній роботі, я ознайомився з автоматами і лінійними граматиками, проаналізував їх розв’язок із скінченими автоматами. Написав програму, яка допускає правильні рядки. Переконався, що вона працює і виводить коректний результат.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора