Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут прикладної математики та фундаментальних наук
Факультет:
ЗІ
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут прикладної математики та фундаментальних наук
Кафедра прикладної математики
Курсова робота
з курсу «Дискретна математика»
на тему «Алгоритми "знизу-вверх" з обмеженими поверненнями.
Неканонічний аналіз.
Аналізатори з двома магазинами.
Відношення передування Колмерауера та їх перевірка»
Зміст
Зміст 2
Анотація 3
Annotation 4
Вступ 5
Основна частина 7
Рис. №1 — Таблиця обмеженого контексту для граматики (7) 12
Рис. №2 — (1, 1) обмежено контекстний розпізнавач 12
LL(k) і LR(k) граматики 15
Теорія LL-мов 16
Приклад 17
Основні поняття алгоритму Ерлі 17
Вхід алгоритму: 18
Вихід алгоритму: 18
Алгоритм 18
Висновок 19
Список використаної літератури 20
Анотація
Всі ми живемо у столітті інноваційних технологій і жоден з нас не може уявити сьогоднішній день без використання будь-яких програм (пошук інформації в інтернеті, покупка речей у магазині і т.д.), тому постає питання: як вирішити проблему зв’язку людини і програми. На сьогоднішній день техніка навчилася розуміти людей настільки, що програми чи вебсайти знають чого вам потрібно. Але як вказати програмі чого саме я хочу? Тобто недостатньо ввести набір слів, а потрібно вказати якийсь зв’язок між словами, щоб між ними був сенс. Так само комп’ютери розуміють слова, які ми ввели, використовуючи різні граматики. Тому в даній роботі буде показано види граматик, пояснення що вони собою являють та алгоритми і приклади роботи граматик.
Annotation
We all live in an age of innovative technologies, and nowadays, not any one of us can imagine life without the use of programs (searching information on the internet, purchases things in shops ect.) that is why there is a question about how to solve the problem of connection between people and programs. Today's technologies have learned to understand people as much as possible so that programs or websites know what you want. But how do I let the program know what I really want? In other words it is not enough just to write a list of words, you have to put them in a proper way, making some connection between them, they should make sense. In the same way computers understand words, which we write, using different grammar. That is why in this paper, work would be shown types of grammar, what they mean, and algorithms and examples of working with them.
Вступ
Існує один клас породжуючих систем, які являються для нас найпершим інтересом — системи, які називаються граматиками.
Спершу поняття граматики було формалізовано лінгвістами при вивченні природніх мов. Вони цікавилися не тільки визначенням, що є чи не є правильним представленням мови, але також шукали способи описання структури тверджень. Однією з цілей була розробка формальної граматики, здатної описанти природню мову. Надіючись, що, заклавши в комп’ютер формальну граматику, наприклад, англійської мови, можна зробити її такою, що “розуміє” цю мову, по словесному формулюванні проблем отримають їх вирішення, втілювати за допомогою комп’ютера переклад з одної мови на іншу.
Як показує практика використання загальнодоступних програм машинного перекладу, по-справжньому доброго вирішення цієї проблеми в нас поки немає. Але цілком задовільні результати досягнуті в описі і реалізації мов.
Зі шкільного досліду відомо, що являє собою граматичний розбір речень. При такому розборі визначається, яке слово є підметом, яке використовується в ролі присудка, які слова відіграють роль означення, додатка, обставини і т.д. При розкладі ми маємо справу з граматичними категоріями: речення, група іменника, група присудка, іменник, дієслово, прислівник і т.д. і користуємося власне кажучи, складовими розкладуваного речення. Накприклад, структура англійського речення: “The little boy ran quickly” можна зобразити у вигляді діаграми:
Граматичний розбір речень означає використання правил деякої граматики. Ми їх будемо представляти в наступній формі:
〈 речення 〉 → 〈 група підмета 〉〈 група присудка 〉
〈 група підмета 〉 → 〈 артикль 〉〈 група іменника 〉
〈 група іменника 〉 → 〈 прикметник 〉〈 група іменника 〉
〈 група іменника 〉 → 〈 іменник 〉
〈 група присудка 〉 → 〈 дієслово 〉〈 прислівник 〉
〈 артикль 〉 → The
〈 прикметник 〉 → little
〈 іменник 〉 → boy
〈 дієслово 〉 → ran
〈 прислівник 〉 → quickly
Тут стрілочка відділяє ліву частину правила від правої, а граматичні терміни взяті в металінгвістичні дужки 〈 і 〉 для того, щоб відрізняти їх від слів, що містяться в аналізованому реченні. За цими правилами можна не тільки перевіряти граматичні правильність речень, але також породжувати правильні граматичні речення. Механізм породження простий. Починаючи з граматичного терміну 〈 речення 〉, яке є головним, кожен граматичний термін, замінюється правою частиною цього правила, яке містить його в лівій частині. Коли в результаті таких замін в поточному ланцюгу не залишиться жодного терміну граматики, ми отримаємо граматично правильне речення мови. Будь-яке речення мови, навіть якщо воно нескінченне, можна вивести таким способом. І хоча більшість породжених речень можуть не мати сенсу, тим не менше, вони вважаються граматично правильними.
Основна частина
Контекстно-вільна граматика (скорочено КВ граматика) — формальна граматика типу 2 в ієрархії Чомскі.
Означення. Контекстно-вільна граматика G це четвірка < N, T, P, S >: (1)
S ∈ N
N та T скінченні множини, що не перетинаються
P скінченна підмножина N×(N ∪ T)*
При цьому, використовують такі назви: N — множина нетермінальних символів, T — множина термінальних символів, P — множина правил виводу S початковий символ. Правила (α, β) ∈ P} записують як α → β.
В лівій частині правила виводу має знаходитись одна змінна (нетермінальний символ). Формально, має виконуватись α ∈ N, β ∈ (N ∪ T)*, де |β| ≥ 1.
Розширенням КВ-граматик є стохастичні КВ граматики. Правилам виведення співставляють ймовірність використання: p: P → R де
23.09.2018 22:09-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора