Міністерство освіти і науки, молоді та спорту України Національний університет «Львівська Політехніка» Факультет прикладної математики Курсова робота З курсу дискретна математика На тему: «Класи граматик, що породжують детерміновані мови. ДМП - автомати в нормальній формі та канонічні граматики. Граматики та детерміновані мови. Граматики розширеного передування та детерміновані мови » Анотація В даній курсовій роботі розглядаються класи граматик, які породжують детерміновані мови, ДМП – автомати в нормальній формі та канонічні граматики, а також граматики розширеного передування. Зміст  Вступ………………………………………………………………………………4  Розділ 1. Класи граматик, що породжують детерміновані мови. ДМП – автомати в нормальній формі та канонічні граматики……………………6  Розділ 2. Граматики та детерміновані мови……………………………...…12   2.1. Прості ССП - граматики і детерміновані мови………………………12 2.2. ОПК - граматики, LR - граматики і детерміновані мови…………...14 Розділ 3. Граматики розширеного передування та детерміновані мови..16 Висновок…………………………………………………………………………19 Програмна реалізація синтезу ДМП – автомата…………………………...20 Література……………………………………………………………………….24   Вступ Автомат з магазинною пам'яттю (МП автомат) — в теорії автоматів це скінченний автомат, що використовує стек для зберігання станів. Автомат з магазинної пам'яттю може розпізнати будь-яку контекстно-вільну мову. У чистому вигляді автомати з магазинною пам'яттю використовуються вкрай рідко. Зазвичай ця модель використовується для наочного подання відмінності звичайних скінченних автоматів від синтаксичних граматик. Реалізація автоматів з магазинною пам'яттю відрізняється від кінцевих автоматів тим, що поточний стан автомата сильно залежить від будь-якого попереднього. Існують детерміновані та недетерміновані автомати з магазинною пам'яттю. МП - автомат