Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Мови. Формальні породжувальні граматики.
Мета: ознайомити з поняттям мови, її складовими;
сформувати поняття формальної породжувальної
граматики;навчити будувати дерева виведення;
обчислювати функцію за даним алгоритмом.
План
1.Поняття мови, основні складові
2.Формальні породжувальня граматики
3.Дерева виведення
4. Нормальні алгоритми Маркова.
Ланцюжки (string) над алфавітом V- це впорядковані сукупності букв алфавіту V , отже, вони виглядають як елементи . Букви є ланцюжком у разі n=1. Будемо допускати випадок, коли ланцюжок не містить букв (порожній ланцюжок ), і позначатимемо такий ланцюжок через . Зазначимо, що не є символом, тобто для будь-якого алфавіту V.
За аналогією з лінгвістикою ланцюжки іноді називають словами . Множину всіх ланцюжків над алфавітом V називають замиканням V і називають
, так що
де
Головну операцію над ланцюжками називають конкатенцією.
Нехай та -ланцюжки над алфавітом V.
Конкатенцією та називають ланцюжок .
Якщо ланцюжок складається з символів, що повторюються , то використовуючи скорочені позначення: для a є V і цілого невід’ємного n записують:
Множину ланцюжків (або речень ) називають мовою.
Формально мова над алфавітом V-це множина ланцюжків у ,тому .
Правила, які визначають множину речень , утворюють синтаксис мови, опис множини смислів і відповідності між реченнями і смислами – семантику мови .
Семантика мови залежить від характеру об’єктів , які описує мова, і засоби її вивчення для різних типів мов різні . Семантика мови математики –формальні теорії . Дослідження семантики мов програмування стало самостійно частиною теоретичного програмування .
Спроби точного опису семантики природних мов стосується, передусім , робіт з машинного перекладу .
Найбільших успіхів математична лінгвістика досягла у вивчені синтаксису , де за останні 50 років розвинувся спеціальний математичний апарат-теорія формальних породжувальних граматик.
Ця теорія дуже важлива теоретично й ефективна у застосуваннях ( мови програмування , штучний інтелект , машинний переклад ).
Ми розглянемо головні поняття теорії формальних граматик і пов'язаний зв'язок між граматиками й автоматами.
Означення:
Формальна породжувальна граматика G(грамматика G)-це формальна система, визначена четвіркою об’єктів G=(V,T,S,P),де V-скінченна не порожня множина , яку називають алфавітом (або словником ) ; Т-її підмножина елементи множини Т називають термінальним( основними) символами;
S-початковий символ (SєV), Р-скінченна множинна продукцій (або правил перетворення ) вигляду та ланцюжок в алфавіті V.
Множину V\T позначають N , її елементи називають не термінальними (допоміжними )символами.
Символи термінального алфавіту прийнято позначати малими латинськими буквами або цифрами, символи не термінального алфавіту-великими латинськими буквами , ланцюжок в алфавіті V-грецькими буквами. Довжину ланцюжка позначають або.
Нехай G=(V,T,S,P)- граматика, і нехай (конкатеція ) , та -ланцюжок над V.
Якщо є продукцією граматики G, то кажуть, щобезпосередньо виводиться з , і дописують .
Якщо -ланцюжки над V такі, що
то кажуть , що породжує , та використовують запис
Послідовність кроків для отримання з називають виведенням .
Приклад 1.
Розглянемо граматику G=(V,T,S,P). Нехай S- початковий символ, . Ланцюжок AaBa виводиться з ABa , оскільки є продукцією граматики . Ланцюжок породжується ланцюжком , оскільки
за допомогою послідовного використання продукцій
Нехай G=(V,T,S,P)- граматика.
Означення:
Мовою, яка породжується G , називають множину всіх ланцюжків терміналів , які виводяться з початкового символу S.
Мовою , що порядкується граматикою G , позначають L(G).
Отже L(G)= , де –множина всіх ланцюжків терміналів,включно з порожнім ланцюжком.
Приклад 2.
Нехай G- граматика з алфавітом , множиною терміналів Т= ,початковим символом S і множиною продукцій Р= . Знайдемо мову L(G), яка порядкується цією граматикою.
Розв'язання:
Із початкового символу S можна вивести ланцюжок А, використовуючи продукцію ; або застосовуючи продукцію щоб вивести . З скориставшись продукцією, можна вивести ланцюжок. Ніяких інших ланцюжків вивести не можна. Отже L(G)= .
.
3.Виведення в мовах , породжених контекстно вільними граматиками, можна зображати графічно з використанням кореневих дерев.
У такому разі ці дерева називають деревами виведення , або деревами синтактичного розбору.
Кореню дерева виведення відповідає початковий символ,внутрішнім вершинам – не термінальні символи , що зустрічаються у виведення, листками –термінальні символи . Нехай ланцюжок і продукція,використана у виведенні. Тоді вершина, яка відповідає не термінальному символу А, має синами вершини , які відповідають кожному
символу ланцюжка у порядку зліва направо
C
C
A
S
b
a
B
b
(мал.1)
Приклад 3.
Визначимо , чи належить ланцюжок мові, породженій граматикою G=(V,T,S,P), де S-початковий символ , а множина продукцій
Розв’язати цю задачу можна двома способами:
1.Розбір зверху вниз .
Оскільки є лише одна продукція з початковим символом S у лівій частині, то виведення починаємо з. Далі використаємо продукцію. Отже, маємо.
Оскільки починається з символів , то використовується продукцію , це дасть .
Завершуємо виведення використанням продукції :
Отже, ланцюжок належить мові L(G).
2. Розбір знизу верх .
Починаємо з ланцюжка ,який потрібно вивести: .Можна використати продукцію ,отже, .
Далі застосуємо продукцію, тоді матимемо .
З використанням продукції , отримаємо. Нарешті використаємо продукцію.
Дерево виведення для рядка у граматиці G зображено (мал.1).
Нормальні алгоритми Маркова є ще однією формалізацією інтуїтивного поняття алгоритму. Теорія нормальних алгоритмів була створена наприкінці 40-х-початку 50-х років ХХ століття російським математиком Андрієм Марковим ( 1903-1979), який назвав їх нормальними алгоритмами.
Підстановки Маркова
Підстановка Маркова – це операція над словами в даному алфавіті
V ( пусте слово позначається , але операція задається за допомогою впорядкованої пари слів ( Р, Q) і полягає в тому , що в заданому слові R знаходять перші входження слова Р, і не змінюючи інших частин слова R, замінюють це входження словом Q. Отримане слово називається результатом застосування підстановки Маркова (Р, Q) до слова R.
Якщо ж першого входження слова Р в мові R немає, то вважається, що підстановка Маркова ( Р, Q) не застосовується до слова R. Підстановку Маркова, що задається за допомогою пари слів ( Р, Q), позначають Р.
У зв’язку з можливістю розгляду пустих слів виникає питання, що означає підстановка Марковатобто, що означає в дане слово w підставити слово v замість першого входження в w пустого слова Згідно означення, випливає, що результатом даної підстановки є слово v w
Приклад 1
Нехай для слів в алфавіті V={a,b,c,d} задані наступні підстановки Маркова:
а)ab г) ac ж) к)
б) д) з) л)
в) е) і)
Застосувати кожну з них до слова abcddacba.
Розв’язання:
Для застосування підстановки Маркова Р до деякого слова, потрібно знайти в слові перше входження підслова Р і замінити його словом Q. В даному випадку для підстановок а)–і) підслово Р входить в дане слово тільки один раз. Це входження легко замінити на підслово Q.Наприклад, для підстановки б) отримаємо . Але для підстановки г) перше входження слова в даному випадку є , а не . Тому отримаємо . Підстановка з) дасть В підстановках к) і л) кожне з перших слів входить в дане слово неодноразово, важливіше є перше входження. Для цих підстановок отримаємо .
НОРМАЛЬНІ АЛГОРИТМИ ТА ЇХ ЗАСТОСУВАННЯ
Впорядкована скінченна сукупність підстановок Маркова в алфавіті
V :
визначає наступне правило побудови послідовності слів в алфавіті V, виходячи із даного слова W в цьому алфавіті, що має назву нормального алгоритму ( Маркова) в алфавіті V. Крапка в дужках означає, що кожна підстановка може бути завершальною. Якщо ж алгоритм заданий в деякому розширенні алфавіту V, то кажуть, що він є нормальний алгоритм над V.
Приклад 2
Нормальний алгоритм в алфавіті V={a,b,1} задається схемою . Застосуйте його до слова
Розв’язання:
Робота алгоритму завершена.
НОРМАЛЬНО ОБЧИСЛЮВАЛЬНІ ФУНКЦІЇ
Будемо розглядати числові функції, тобто функції задані на множині натуральних чисел. Натуральні числа кодуються словами в алфавіті V={1}, так, що розглядаються функції, задані словами над цим алфавітом. При цьому, функція f, задана на деякій множині слів алфавіту V, є нормально обчислювальною, якщо знайдеться таке розширення в даного алфавіту ) і такий нормальний алгоритм в В, що кожне слово Р ( в алфавіті V) з області визначення функції f цей алгоритм перетворює в слово f ( Р) ( в алфавіті V).
Також розглянемо функції для обчислення яких будуються нормальні алгоритми в розширених алфавітах. Алфавіт V={0,1,….9}будемо називати основним.
Приклад 3
В алфавіті В=, що є розширенням алфавіту А, розглянемо нормальний алгоритм, що задається схемою ( читається по стовпцях):
Застосувавши його до слова 3000 , показати, що він обчислює функцію f ( х) = х-1
Розв’язання :
Алгоритм працює наступним чином: спочатку застосовується остання підстановка: 3000. Потім підстановки з 2-го стовпчика, поки а не займе крайнє праве положення: Тепер застосуємо підстановку з третього стовпця: Використаємо з першого стовпця: 3000. Знову застосовуємо підстановку до тих пір поки, лівіше букви b не отримується цифра відмінна від 0: . Тепер завершальна підстановка отримаємо
Запитання для самоперевірки.
Література